发一篇不需要O2就能过的分块。
基本思路：
分块的思路，大段维护，小段朴素。
维护几个数组：
- 区块(block[maxn])
- 懒标记(tag[maxn])
- 真实数据(data[maxn])。
更新时
假设我们涉及到的区块的编号区间是([lb,rb])，真实数据范围为([l,r])。
那么，我们在区块的([lb+1,rb-1])区间，给(block[i])加上(Delta k) 并且打上懒标记 (=Delta k)。在真实数据的([l,lb imes N])和([rb imes N-N+1,r])区间的每个(data[i])加上(Delta k)。
查询时
同样的，对于区块区间([lb+1,rb-1])直接累加就好，对于(l b)区间和(rb)区间单独处理即可。
上丑陋无比的代码。注意特判(l)和(r)在一个区块区间的情况。
#include<bits/stdc++.h>
using namespace std;
template< class ccf >inline ccf qr(ccf a) {
char c=getchar();
ccf x=0;
int q=1;
while(c<48||c>57)
q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)
x=x*10+c-48,c=getchar();
return q==-1?-x:x;
}
const int maxn=100055;
typedef long long ll;
ll data[maxn];
ll tag[maxn];
ll blk[maxn];
int n;
int m;
int N;
int adj;
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;t++)
int t1,t2;
ll t3;
int temp;
void add(int l,int r,ll k) {
int lb=(l+N-1)/N;
int rb=(r+N-1)/N;
if(lb!=rb) {
RP(t,l,N*lb)
data[t]+=k,blk[lb]+=k;
RP(t,N*rb-N+1,r)
data[t]+=k,blk[rb]+=k;
RP(t,lb+1,rb-1)
tag[t]+=k,blk[t]+=N*k;
} else
RP(t,l,r)
data[t]+=k,blk[t]+=k;
}
ll sum(int l,int r) {
ll ret=0;
int lb=(l+N-1)/N;
int rb=(r+N-1)/N;
RP(t,lb+1,rb-1)
ret+=blk[t];
if(tag[lb])
RP(t,N*lb-N+1,N*lb)
data[t]+=tag[lb];
tag[lb]=0;
if(tag[rb])
RP(t,N*rb-N+1,min(N*rb,n))
data[t]+=tag[rb];
tag[rb]=0;
if(lb!=rb) {
RP(t,l,N*lb)
ret+=data[t];
RP(t,N*rb-N+1,r)
ret+=data[t];
} else
RP(t,l,r)
ret+=data[t];
return ret;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=qr(1);
m=qr(1);
RP(t,1,n)
data[t]=qr(1ll);
N=sqrt(n);
RP(t,1,n/N)
RP(i,1,N)
blk[t]+=data[(t-1)*N+i];
RP(t,1,n%N)
blk[n/N+1]+=data[(n/N)*N+t];
RP(t,1,m) {
temp=qr(1);
if(temp==1) {
t1=qr(1);
t2=qr(1);
t3=qr(1ll);
add(t1,t2,t3);
} else {
t1=qr(1);
t2=qr(1);
printf("%ld
",sum(t1,t2));
}
}
return 0;
}