同志们,我为啥M了
查看原帖
同志们,我为啥M了
472950
封禁用户楼主2022/3/3 21:08
#include<bits/stdc++.h>
using namespace std;

struct node{
	int sum,lz,a,b,c,d;
}tr[2048*2048*4];

int n=2048,m=2048,fs;
char cc;

void pushdown(int now){
	int sq=(tr[now].c-tr[now].a+1)*(tr[now].d-tr[now].b+1)/4;
	tr[now*4].sum+=tr[now].lz*sq,tr[now*4+1].sum+=tr[now].lz*sq;
	tr[now*4+2].sum+=tr[now].lz*sq,tr[now*4+3].sum+=tr[now].lz*sq;
	tr[now*4].lz+=tr[now].lz,tr[now*4+1].lz+=tr[now].lz;
	tr[now*4+2].lz+=tr[now].lz,tr[now*4+3].lz+=tr[now].lz;
	tr[now].lz=0;
}

void build(int a,int b,int c,int d,int now){
	tr[now].a=a,tr[now].b=b;
	tr[now].c=c,tr[now].d=d;
	if(a==c&&b==d){
		return;
	}
	int md1=(a+c)/2,md2=(b+d)/2;
	build(a,b,md1,md2,now*4),build(a,md2+1,md1,d,now*4+1);
	build(md1+1,b,c,md2,now*4+2),build(md1+1,md2+1,c,d,now*4+3);
}

void add(int a,int b,int c,int d,int now,int ltt){
	if(a==tr[now].a&&b==tr[now].b&&c==tr[now].c&&d==tr[now].d){
		tr[now].sum+=(c-a+1)*(d-b+1)*ltt;
		tr[now].lz+=ltt;
		return;
	}
	pushdown(now);
	int md1=(tr[now].a+tr[now].c)/2,md2=(tr[now].b+tr[now].d)/2;
	if(a<=md1&&b<=md2)add(a,b,min(c,md1),min(d,md2),now*4,ltt);
	if(a<=md1&&d>md2)add(a,max(b,md2+1),min(c,md1),d,now*4+1,ltt);
	if(c>md1&&b<=md2)add(max(a,md1+1),b,c,min(d,md2),now*4+2,ltt);
	if(c>md1&&d>md2)add(max(a,md1+1),max(b,md2+1),c,d,now*4+3,ltt);
}

int sum(int a,int b,int c,int d,int now){
	if(a==tr[now].a&&b==tr[now].b&&c==tr[now].c&&d==tr[now].d){
		return tr[now].sum;
	}
	pushdown(now);
	int md1=(tr[now].a+tr[now].c)/2,md2=(tr[now].b+tr[now].d)/2,ans=0;
	if(a<=md1&&b<=md2)ans+=sum(a,b,min(c,md1),min(d,md2),now*4);
	if(a<=md1&&d>md2)ans+=sum(a,max(b,md2+1),min(c,md1),d,now*4+1);
	if(c>md1&&b<=md2)ans+=sum(max(a,md1+1),b,c,min(d,md2),now*4+2);
	if(c>md1&&d>md2)ans+=sum(max(a,md1+1),max(b,md2+1),c,d,now*4+3);
	return ans;
}

int main(){
	cin>>cc>>fs>>fs;
	build(1,1,n,m,1);
	while(cin>>cc){
		int a,b,c,d,ltt;
		cin>>a>>b>>c>>d;
		if(cc=='L'){
			cin>>ltt;
			add(a,b,c,d,1,ltt);
		}
		else{
			cout<<sum(a,b,c,d,1)<<endl;
		}
	}
	return 0;
}
2022/3/3 21:08
加载中...