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

orz

1 #include
     
        2 #define pa pair
      
         3 #define CLR(a,x) memset(a,x,sizeof(a))  4 using namespace std;  5 typedef long long ll;  6 const int maxn=(1<<20),maxp=(1<<18)+10;  7   8 inline ll rd(){  9     ll x=0;char c=getchar();int neg=1; 10     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();} 11     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12     return x*neg; 13 } 14  15 ll sum[maxp],v[maxn],laz[maxp]; 16 int N,M; 17  18 inline void update(int p,int l,int r){ 19     if(r-l+1<=16){     20         sum[p]=0; 21         for(int i=l;i<=r;i++){ 22             sum[p]+=v[i]; 23         } 24     }else{ 25         sum[p]=sum[p<<1]+sum[p<<1|1]; 26     } 27 } 28 inline void deal(int p,int l,int r,ll z){ 29     if(r-l+1<=16){ 30         for(int i=l;i<=r;i++){ 31             v[i]+=z,sum[p]+=z; 32         } 33     }else sum[p]+=z*(r-l+1); 34 } 35  36 inline void pushdown(int p,int l,int r){ 37     if(!laz[p]||r-l+1<=16) return; 38     int a=p<<1,b=p<<1|1,m=l+r>>1; 39     deal(a,l,m,laz[p]),deal(b,m+1,r,laz[p]); 40     laz[a]+=laz[p],laz[b]+=laz[p]; 41     laz[p]=0; 42 } 43  44 void build(int p,int l,int r){ 45     if(r-l+1<=16) update(p,l,r); 46     else{ 47         int m=l+r>>1; 48         build(p<<1,l,m); 49         build(p<<1|1,m+1,r); 50         // printf("!%d %d %d\n",p,l,r); 51         update(p,l,r); 52     } 53 } 54  55 ll query(int p,int l,int r,int x,int y){ 56     // printf("~~%d %d %d %d %d\n",p,l,r,x,y); 57     pushdown(p,l,r); 58     if(x<=l&&r<=y) return sum[p]; 59     if(r-l+1<=16){ 60         ll re=0; 61         for(int i=x;i<=y;i++) re+=v[i]; 62         return re; 63     } 64     int m=l+r>>1;ll re=0; 65     if(x<=m) re=query(p<<1,l,m,x,min(m,y)); 66     if(y>=m+1) re+=query(p<<1|1,m+1,r,max(x,m+1),y); 67     return re; 68 } 69  70 void add(int p,int l,int r,int x,int y,ll z){ 71     // printf("!!%d %d %d %d %d\n",p,l,r,x,y); 72     pushdown(p,l,r); 73     if(r-l+1<=16){ 74         for(int i=x;i<=y;i++) 75             v[i]+=z,sum[p]+=z; 76     }else if(x<=l&&r<=y){ 77         deal(p,l,r,z); 78         laz[p]+=z; 79     }else{ 80         int m=l+r>>1; 81         if(x<=m) add(p<<1,l,m,x,min(m,y),z); 82         if(y>=m+1) add(p<<1|1,m+1,r,max(m+1,x),y,z); 83         update(p,l,r); 84     } 85 } 86  87 int main(){ 88     //freopen("","r",stdin); 89     int i; 90     N=rd(),M=rd(); 91     for(i=1;i<=N;i++) 92         v[i]=rd(); 93     N=1<<((int)log2(N)+1); 94     build(1,1,N); 95     for(i=1;i<=M;i++){ 96         char s[10]; 97         scanf("%s",s); 98         int l=rd(),r=rd(); 99         if(s[1]=='d'){100             int d=rd();101             add(1,1,N,l,r,d);102         }else printf("%lld\n",query(1,1,N,l,r));103     }104     return 0;105 }