用三叉树，稳过
by ssytxy2024 @ 2022-10-22 21:45:11
一个细节，现在63：
```cpp
#include<bits/stdc++.h>
using namespace std;
char c[1];
int n,m,sum[5000010],add[5000010];
void push_up(int rt){
sum[rt]=sum[rt<<2]+sum[rt<<2|1]+sum[rt<<2|2]+sum[rt<<2|3];
}
void push_down(int rt,int m1,int m2){
if(add[rt]){
add[rt<<2]+=add[rt];
add[rt<<2|1]+=add[rt];
add[rt<<2|2]+=add[rt];
add[rt<<2|3]+=add[rt];
sum[rt<<2]+=add[rt]*(m1-(m1>>1))*(m2-(m2>>1));
sum[rt<<2|1]+=add[rt]*(m1-(m1>>1))*(m2>>1);
sum[rt<<2|2]+=add[rt]*(m1>>1)*(m2-(m2>>1));
sum[rt<<2|3]+=add[rt]*(m1>>1)*(m2>>1);
add[rt]=0;
}
return;
}
void update(int l1,int l2,int r1,int r2,int rt,int a,int b,int c,int d,int e){
if(a<=l1&&c>=r1&&b<=l2&&d>=r2){
sum[rt]+=e*(r1-l1+1)*(r2-l2+1);
add[rt]+=e;
return;
}
push_down(rt,r1-l1+1,r2-l2+1);
int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;
if(a<=mid1&&b<=mid2) update(l1,l2,mid1,mid2,rt<<2,a,b,c,d,e);
if(a<=mid1&&d>mid2) update(l1,mid2+1,mid1,r2,rt<<2|1,a,b,c,d,e);
if(c>mid1&&b<=mid2) update(mid1+1,l2,r1,mid2,rt<<2|2,a,b,c,d,e);
if(c>mid1&&d>mid2) update(mid1+1,mid2+1,r1,r2,rt<<2|3,a,b,c,d,e);
push_up(rt);
return;
}
int query(int l1,int l2,int r1,int r2,int rt,int a,int b,int c,int d){
if(a<=l1&&c>=r1&&b<=l2&&d>=r2) return sum[rt];
push_down(rt,r1-l1+1,r2-l2+1);
int ans=0;
int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;
if(a<=mid1&&b<=mid2) ans+=query(l1,l2,mid1,mid2,rt<<2,a,b,c,d);
if(a<=mid1&&d>mid2) ans+=query(l1,mid2+1,mid1,r2,rt<<2|1,a,b,c,d);
if(c>mid1&&b<=mid2) ans+=query(mid1+1,l2,r1,mid2,rt<<2|2,a,b,c,d);
if(c>mid1&&d>mid2) ans+=query(mid1+1,mid2+1,r1,r2,rt<<2|3,a,b,c,d);
return ans;
}
int main(){
scanf("%s%d%d",c,&n,&m);
while(~scanf("%s",c)){
if(c[0]=='L'){
int a,b,c,d,delta;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&delta);
update(1,1,n,m,1,a,b,c,d,delta);
}else{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\n",query(1,1,n,m,1,a,b,c,d));
}
}
return 0;
}
```
by STUDENT00 @ 2022-10-22 21:46:51
@[qlzx74lyc41](/user/575453) 三叉树？怎么搞，不是必须要四分吗？
by STUDENT00 @ 2022-10-22 21:47:14
@[YuRuochen](/user/658786) 四分树复杂度错的过啥过。。。
by FunnyCreatress @ 2022-10-22 21:52:42