sbw巨佬的卡空间方法,把线段树的叶节点只记到长度为16的区间,然后在叶节点上暴力修改查询,这样点数是$\frac{N}{8}$的,可以过...

orz

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=(<<),maxp=(<<)+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} ll sum[maxp],v[maxn],laz[maxp];
int N,M; inline void update(int p,int l,int r){
if(r-l+<=){
sum[p]=;
for(int i=l;i<=r;i++){
sum[p]+=v[i];
}
}else{
sum[p]=sum[p<<]+sum[p<<|];
}
}
inline void deal(int p,int l,int r,ll z){
if(r-l+<=){
for(int i=l;i<=r;i++){
v[i]+=z,sum[p]+=z;
}
}else sum[p]+=z*(r-l+);
} inline void pushdown(int p,int l,int r){
if(!laz[p]||r-l+<=) return;
int a=p<<,b=p<<|,m=l+r>>;
deal(a,l,m,laz[p]),deal(b,m+,r,laz[p]);
laz[a]+=laz[p],laz[b]+=laz[p];
laz[p]=;
} void build(int p,int l,int r){
if(r-l+<=) update(p,l,r);
else{
int m=l+r>>;
build(p<<,l,m);
build(p<<|,m+,r);
// printf("!%d %d %d\n",p,l,r);
update(p,l,r);
}
} ll query(int p,int l,int r,int x,int y){
// printf("~~%d %d %d %d %d\n",p,l,r,x,y);
pushdown(p,l,r);
if(x<=l&&r<=y) return sum[p];
if(r-l+<=){
ll re=;
for(int i=x;i<=y;i++) re+=v[i];
return re;
}
int m=l+r>>;ll re=;
if(x<=m) re=query(p<<,l,m,x,min(m,y));
if(y>=m+) re+=query(p<<|,m+,r,max(x,m+),y);
return re;
} void add(int p,int l,int r,int x,int y,ll z){
// printf("!!%d %d %d %d %d\n",p,l,r,x,y);
pushdown(p,l,r);
if(r-l+<=){
for(int i=x;i<=y;i++)
v[i]+=z,sum[p]+=z;
}else if(x<=l&&r<=y){
deal(p,l,r,z);
laz[p]+=z;
}else{
int m=l+r>>;
if(x<=m) add(p<<,l,m,x,min(m,y),z);
if(y>=m+) add(p<<|,m+,r,max(m+,x),y,z);
update(p,l,r);
}
} int main(){
//freopen("","r",stdin);
int i;
N=rd(),M=rd();
for(i=;i<=N;i++)
v[i]=rd();
N=<<((int)log2(N)+);
build(,,N);
for(i=;i<=M;i++){
char s[];
scanf("%s",s);
int l=rd(),r=rd();
if(s[]=='d'){
int d=rd();
add(,,N,l,r,d);
}else printf("%lld\n",query(,,N,l,r));
}
return ;
}
05-06 16:55