四分树样例都没过。。。
查看原帖
四分树样例都没过。。。
658786
STUDENT00楼主2022/10/22 21:44

求调代码!

#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*(c-a+1)*(d-b+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;
}
2022/10/22 21:44
加载中...