9分四分树求调
查看原帖
9分四分树求调
1275495
cai_cai_cai楼主2024/12/14 15:47

rt,帮我把 WA 的调过就行了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int l,r,l1,r1,sum,Lazy;
}t[20000005];
void build(int l,int r,int l1,int r1,int p){
	if(p<=0)return;
	if(l>r||l1>r1)return;
	t[p].l=l;
	t[p].r=r;
	t[p].l1=l1;
	t[p].r1=r1;
	t[p].Lazy=0;
	int m=(l+r)>>1,m1=(l1+r1)>>1;
	if(l==r&&l1==r1){
		t[p].sum=0;
		return;
	}
	build(l,m,l1,m1,p*4-2);
	build(m+1,r,l1,m1,p*4-1);
	build(l,m,m1+1,r1,p*4);
	build(m+1,r,m1+1,r1,p*4+1);
	t[p].sum=t[p*4-2].sum+t[p*4-1].sum+t[p*4].sum+t[p*4+1].sum;
}
int getsum(int l,int r,int l1,int r1,int p){
	if(p<=0)return 0;
	if(l>r||l1>r1)return 0;
	int L=t[p].l,R=t[p].r,L1=t[p].l1,R1=t[p].r1;
//	cout<<L<<" "<<R<<" "<<L1<<" "<<R1<<":"<<t[p].sum<<"\n";
	if(L>=l&&R<=r&&L1>=l1&&R1<=r1){
		return t[p].sum;
	}
	if((R<l||L>r)||(R1<l1||L1>r1))return 0;
	int m=(L+R)>>1,m1=(L1+R1)>>1;
	if(t[p].Lazy){
		if(t[p*4-2].l&&m>=L&&m1>=L1)t[p*4-2].sum+=t[p].Lazy*(m-L+1)*(m1-L+1);
		if(t[p*4-1].l&&R>=m&&m1>=L1)t[p*4-1].sum+=t[p].Lazy*(R-m)*(m1-L+1);
		if(t[p*4].l&&m>=L&&R1>=m1)t[p*4].sum+=t[p].Lazy*(m-L+1)*(R1-m1);
		if(t[p*4+1].l&&R>=m&&R1>=m1)t[p*4+1].sum+=t[p].Lazy*(R-m)*(R1-m1);
		if(t[p*4-2].l)t[p*4-2].Lazy+=t[p].Lazy;
		if(t[p*4-1].l)t[p*4-1].Lazy+=t[p].Lazy;
		if(t[p*4].l)t[p*4].Lazy+=t[p].Lazy;
		if(t[p*4+1].l)t[p*4+1].Lazy+=t[p].Lazy;
		t[p].Lazy=0;
	}
	return getsum(l,r,l1,r1,p*4-2)+getsum(l,r,l1,r1,p*4-1)+getsum(l,r,l1,r1,p*4)+getsum(l,r,l1,r1,p*4+1);
}
void update(int l,int r,int l1,int r1,int p,int c){
	if(p<=0)return;
	if(l>r||l1>r1)return;
	int L=t[p].l,R=t[p].r,L1=t[p].l1,R1=t[p].r1;
	if(R1<L1||R<L)return;
	if(L>=l&&R<=r&&L1>=l1&&R1<=r1){t[p].sum+=c*(R-L+1)*(R1-L1+1);t[p].Lazy+=c;return;}
	if((R<l||L>r)||(R1<l1||L1>r1))return;
	int m=(L+R)>>1,m1=(L1+R1)>>1;
	if(t[p].Lazy){
		if(t[p*4-2].l&&m>=L&&m1>=L1)t[p*4-2].sum+=t[p].Lazy*(m-L+1)*(m1-L+1);
		if(t[p*4-1].l&&R>=m&&m1>=L1)t[p*4-1].sum+=t[p].Lazy*(R-m)*(m1-L+1);
		if(t[p*4].l&&m>=L&&R1>=m1)t[p*4].sum+=t[p].Lazy*(m-L+1)*(R1-m1);
		if(t[p*4+1].l&&R>=m&&R1>=m1)t[p*4+1].sum+=t[p].Lazy*(R-m)*(R1-m1);
		if(t[p*4-2].l)t[p*4-2].Lazy+=t[p].Lazy;
		if(t[p*4-1].l)t[p*4-1].Lazy+=t[p].Lazy;
		if(t[p*4].l)t[p*4].Lazy+=t[p].Lazy;
		if(t[p*4+1].l)t[p*4+1].Lazy+=t[p].Lazy;
		t[p].Lazy=0;
	}
	update(l,r,l1,r1,p*4-2,c);
	update(l,r,l1,r1,p*4-1,c);
	update(l,r,l1,r1,p*4,c);
	update(l,r,l1,r1,p*4+1,c);
	t[p].sum=t[p*4-2].sum+t[p*4-1].sum+t[p*4].sum+t[p*4+1].sum;
}
int n,m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	char op;
	cin>>op>>n>>m;
	build(1,n,1,m,1);
	while(cin>>op){
		int a,b,c,d,x;
		cin>>a>>b>>c>>d;
		if(op=='L'){
			cin>>x;
			update(a,c,b,d,1,x);
		}else{
			cout<<getsum(a,c,b,d,1)<<"\n";
		}
	}
	return 0;
}
2024/12/14 15:47
加载中...