NOIP爆炸人求助
查看原帖
NOIP爆炸人求助
171513
Polariserist楼主2020/12/14 19:27

RT,RE求助

#include<bits/stdc++.h>
#define ak cout<<"lmq ak ioi!\n";
using namespace std;
char c;
int n,m,tree[1<<20],txl[1<<20],txr[1<<20],tyl[1<<20],tyr[1<<20],txmid[1<<20],tymid[1<<20],lazy[1<<20];
int read(){
    int x=0;char ch=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x;
}
void replace(int p){
	tree[p]=tree[p*4+1]+tree[p*4+2]+tree[p*4+3]+tree[p*4+4];
}
void spread(int p){
	tree[p*4+1]+=lazy[p]*(txr[p*4+1]-txl[p*4+1]+1)*(tyr[p*4+1]-tyl[p*4+1]+1);
	tree[p*4+2]+=lazy[p]*(txr[p*4+2]-txl[p*4+2]+1)*(tyr[p*4+2]-tyl[p*4+2]+1);
	tree[p*4+3]+=lazy[p]*(txr[p*4+3]-txl[p*4+3]+1)*(tyr[p*4+3]-tyl[p*4+3]+1);
	tree[p*4+4]+=lazy[p]*(txr[p*4+4]-txl[p*4+4]+1)*(tyr[p*4+4]-tyl[p*4+4]+1);
	lazy[p*4+1]+=lazy[p];
	lazy[p*4+2]+=lazy[p];
	lazy[p*4+3]+=lazy[p];
	lazy[p*4+4]+=lazy[p];
	lazy[p]=0;
}
void build(int p,int xl,int yl,int xr,int yr){
	txl[p]=xl;
	txr[p]=xr;
	tyl[p]=yl;
	tyr[p]=yr;
	if(xl==xr&&yl==yr)return;
	int xmid=(xl+xr)/2,ymid=(yl+yr)/2;
	txmid[p]=xmid;
	tymid[p]=ymid;
	build(p*4+1,xl,xmid,yl,ymid);
	build(p*4+2,xl,xmid,ymid+1,yr);
	build(p*4+3,xmid+1,xr,yl,ymid);
	build(p*4+4,xmid+1,xr,ymid+1,yr);
	replace(p);
}
void add(int p,int xl,int yl,int xr,int yr,int d){
	if(xl<=txl[p]&&yl<=tyl[p]&&xr>=txr[p]&&yr>=tyr[p]){
		tree[p]+=d*(txr[p]-txl[p]+1)*(tyr[p]-tyl[p]+1);
		lazy[p]+=d;
		return;
	}
	spread(p);
	if(xl<=txmid[p])add(p*4+1,xl,yl,xr,yr,d);
	if(xr>txmid[p])add(p*4+2,xl,yl,xr,yr,d);
	if(yl<=tymid[p])add(p*4+3,xl,yl,xr,yr,d);
	if(yr>tymid[p])add(p*4+4,xl,yl,xr,yr,d);
	replace(p);
}
int ask(int p,int xl,int xr,int yl,int yr){
	if(xl<=txl[p]&&yl<=tyl[p]&&xr>=txr[p]&&yr>=tyr[p]){
		return tree[p];
	}
	spread(p);
	int ans=0;
	if(xl<=txmid[p])ans+=ask(p*4+1,xl,yl,xr,yr);
	if(xr>txmid[p])ans+=ask(p*4+2,xl,yl,xr,yr);
	if(yl<=tymid[p])ans+=ask(p*4+3,xl,yl,xr,yr);
	if(yr>tymid[p])ans+=ask(p*4+4,xl,yl,xr,yr);
	return ans;
}
int main(){
	cin>>n>>m;
	build(1,1,1,n,m);
	int opt;
	while(opt=getchar(),opt!=EOF){
		if(opt=='L'){
			int a,b,c,d,delta;
			cin>>a>>b>>c>>d>>delta;
			add(1,a,b,c,d,delta);
		}
		if(opt=='k'){
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			ak
			cout<<ask(1,a,b,c,d)<<'\n';
			ak
		}
	}
}
2020/12/14 19:27
加载中...