分块写炸了,咋调啊
查看原帖
分块写炸了,咋调啊
399936
辰云楼主2021/9/30 22:30
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct jjy{
    int sum,add,set,max,min;
}tag[21][10005];
int v[21][1000005],blo,bl[1000005];
int r,c,m;

inline void reset(int x,int y){
	
	if(tag[x][y].add!=0){
		for(int i=(y-1)*blo+1;i<=min(y*blo,c);i++){
			v[x][i]+=tag[x][y].add;
		}
		tag[x][y].sum+=tag[x][y].add*blo;
		tag[x][y].max+=tag[x][y].add;
		tag[x][y].min+=tag[x][y].add;
	}
	
	if(tag[x][y].set!=-1){
		for(int i=(y-1)*blo+1;i<=min(y*blo,c);i++){
			v[x][i]=tag[x][y].set;
		}
		tag[x][y].sum=tag[x][y].set*blo;
		tag[x][y].set=-1;
		tag[x][y].add=0;
		tag[x][y].max=tag[x][y].min=tag[x][y].set;
	}
	
}

inline void add(int x1,int y1,int x2,int y2,int k){
	for(int i=x1;i<=x2;i++){
		if(tag[i][bl[y1]].add!=0||tag[i][bl[y1]].set!=-1)reset(i,bl[y1]);
		for(int j=y1;j<=min(bl[y1]*blo,y2);j++) {
			v[i][j]+=k;
			tag[i][bl[j]].sum+=k;
		}
		if(tag[i][bl[y1]].add!=0||tag[i][bl[y1]].set!=-1){
			if(tag[i][bl[y2]].set!=-1)reset(i,bl[y2]);
			for(int j=(bl[y2]-1)*blo+1;j<=min(y2,c);j++){
				v[i][j]+=k;
				tag[i][bl[j]].sum+=k;
			}
		}
		for(int j=bl[y1]+1;j<=bl[y2]-1;j++) tag[i][j].add+=k;
	}
}

inline void set(int x1,int y1,int x2,int y2,int k){
	for(int i=x1;i<=x2;i++){
		if(tag[i][bl[y1]].add!=0||tag[i][bl[y1]].set!=-1)reset(i,bl[y1]);
		for(int j=y1;j<=min(bl[y1]*blo,y2);j++) {
			tag[i][bl[j]].sum+=k-v[i][j];
			v[i][j]=k;
		}
		if(bl[y1]!=bl[y2]){
			if(tag[i][bl[y1]].add!=0||tag[i][bl[y1]].set!=-1)reset(i,bl[y2]);
			for(int j=(bl[y2]-1)*blo+1;j<=min(y2,c);j++){
				tag[i][bl[j]].sum+=k-v[i][j];
				v[i][j]=k;
			}
		}
		for(int j=bl[y1]+1;j<=bl[y2]-1;j++) tag[i][j].set=k,tag[i][j].add=0;
	}
}

inline int query_sum(int x1,int y1,int x2,int y2){
	int ans=0;
	for(int i=x1;i<=x2;i++){
		for(int j=y1;j<=min(y2,bl[y1]*blo);j++){
			if(tag[i][bl[j]].set==-1){
				int val=v[i][j]+tag[i][bl[j]].add;
				ans+=val;
			}else {
				ans+=(tag[i][bl[j]].set+tag[i][bl[j]].add)*(min(y2,bl[y1]*blo)-y1+1);
				break;
			}
		}
		if(bl[y1]!=bl[y2])
			for(int j=(bl[y2]-1)*blo+1;j<=y2;j++){
				if(tag[i][bl[j]].set==-1){
					int val=v[i][j]+tag[i][bl[j]].add;
					ans+=val;
				}else {
					ans+=(tag[i][bl[j]].set+tag[i][bl[j]].add)*(min(y2,bl[y1]*blo)-y1+1);
					break;
				}
			}
		for(int j=bl[y1]+1;j<=bl[y2]-1;j++)ans+=tag[i][j].sum;
		return ans;
	}
}

inline int query_min(int x1,int y1,int x2,int y2){
	int ans=999999999;
	for(int i=x1;i<=x2;i++){
		for(int j=y1;j<=min(y2,bl[y1]*blo);j++){
			if(tag[i][bl[j]].set==-1){
				int val=v[i][j]+tag[i][bl[j]].add;
				ans=min(ans,val);
			}else {
				ans=min(ans,tag[i][bl[j]].set+tag[i][bl[j]].add);
				break;
			}
		}
		if(bl[y1]!=bl[y2])
			for(int j=(bl[y2]-1)*blo+1;j<=y2;j++){
				if(tag[i][bl[j]].set==-1){
					int val=v[i][j]+tag[i][bl[j]].add;
					ans=min(ans,val);
				}else {
					ans=min(ans,tag[i][bl[j]].set+tag[i][bl[j]].add);
					break;
				}
			}
		for(int j=bl[y1]+1;j<=bl[y2]-1;j++)ans=min(ans,tag[i][j].set+tag[i][j].add);
		return ans;
	} 
}

inline int query_max(int x1,int y1,int x2,int y2){
	int ans=-999999999;
	for(int i=x1;i<=x2;i++){
		for(int j=y1;j<=min(y2,bl[y1]*blo);j++){
			if(tag[i][bl[j]].set==-1){
				int val=v[i][j]+tag[i][bl[j]].add;
				ans=max(ans,val);
			}else {
				ans=max(ans,tag[i][bl[j]].set+tag[i][bl[j]].add);
				break;
			}
		}
		if(bl[y1]!=bl[y2])
			for(int j=(bl[y2]-1)*blo+1;j<=y2;j++){
				if(tag[i][bl[j]].set==-1){
					int val=v[i][j]+tag[i][bl[j]].add;
					ans=max(ans,val);
				}else {
					ans=max(ans,tag[i][bl[j]].set+tag[i][bl[j]].add);
					break;
				}
			}
		for(int j=bl[y1]+1;j<=bl[y2]-1;j++)ans=max(ans,tag[i][j].set+tag[i][j].add);
	}
	return ans;
}
int main(){
    r=read();c=read();m=read();
	blo=sqrt(c);
	for(int j=1;j<=c;j++) bl[j]=(j-1)/blo+1;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=blo;j++)
			tag[i][j].set=-1;
	while(m--){
		int f=read(),x1=read(),y1=read(),x2=read(),y2=read();
		int k;
		if(f==1)k=read(),add(x1,y1,x2,y2,k);
		if(f==2)k=read(),set(x1,y1,x2,y2,k);
		if(f==3)printf("%d %d %d\n",query_sum(x1,y1,x2,y2),query_max(x1,y1,x2,y2),query_min(x1,y1,x2,y2));
	}
	return 0;
}
2021/9/30 22:30
加载中...