分块模板
2024-10-19 22:24:15
发布于：广东
12阅读
0回复
0点赞
void f(int l, int r){
if(r - l < len){//不足一块
for(int i = l; i <= r; i++){
}
return;
}
for(int i = l / len + 1; i < r / len; i++){//整块
}
for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块
}
for(int i = max(r / len * len, l + 1); i <= r; i++){
}
}
例 A21126.守墓人 线段树模板题 但是我还要用宝贵的内存做其他事时就可以用
#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
signed a[200005];
int blocks[505], lazytag[505];
int len, tmp, l, r, val;
void modify(int l, int r, int val){
if(r - l < len){//不足一块
for(int i = l; i <= r; i++){
blocks[i / len] += val;
a[i] += val;
}
return;
}
for(int i = l / len + 1; i < r / len; i++){//整块
blocks[i] += len * val;
lazytag[i] += val;
}
for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块
blocks[i / len] += val;
a[i] += val;
}
for(int i = max(r / len * len, l + 1); i <= r; i++){
blocks[i / len] += val;
a[i] += val;
}
}
int query(int l, int r){
int ct = 0;
if(r - l < len){//不足一块
for(int i = l; i <= r; i++){
ct += a[i] + lazytag[i / len];
}
return ct;
}
for(int i = l / len + 1; i < r / len; i++){//整块
ct += blocks[i];
}
for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块
ct += a[i] + lazytag[i / len];
}
for(int i = max(r / len * len, l + 1); i <= r; i++){
ct += a[i] + lazytag[i / len];
}
return ct;
}
signed main(){
int n, m;
cin >> n >> m;
len = sqrt(n);
for(int i = 1; i <= n; i++){
cin >> a[i];
blocks[i / len] += a[i];
}
while(m--){
cin >> tmp;
if(tmp == 1){
cin >> l >> r >> val;
if(l > r) swap(l, r);
modify(l, r, val);
}else if(tmp == 2 || tmp == 3){
cin >> val;
modify(1, 1, (tmp == 2 ? val : -val));
}else if(tmp == 4){
cin >> l >> r;
if(l > r) swap(l, r);
cout << query(l, r) << endl;
}else{
cout << query(1, 1) << endl;
}
}
return 0;
}
有帮助，赞一个