分块套线段树WA求调
查看原帖
分块套线段树WA求调
989792
lrx___楼主2024/8/9 11:48

只需把 WA 解决即可，不用管 TLE。

record

// #define ___coding

#ifdef ___coding
#define ___coding1 true
#else
#define ___coding1 false
#endif
#include<cmath>
#include<cassert>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<ctime>

// #include<algorithm>
// using std::__gcd;
// using std::lower_bound;
// using std::max;
// using std::min;
// using std::next_permutation;
// using std::reverse;
// using std::sort;
// using std::swap;
// using std::unique;
// using std::upper_bound;

// #include<bitset>
// using std::bitset;

// #include<deque>
// using std::deque;

// #include<fstream>
// using std::ifstream;
// using std::ofstream;

// #include<iomanip>
// using std::fixed;
// using std::setprecision;

// #include<iostream>
// using std::cin;
// using std::cout;
// using std::ios;

// #include<list>
// using std::list;

// #include<map>
// using std::map;

// #include<memory>
// using std::make_shared;
// using std::make_unique;
// using std::shared_ptr;
// using std::unique_ptr;

// #include<queue>
// using std::priority_queue;
// using std::queue;

// #include<stack>
// using std::stack;

// #include<set>
// using std::multiset;
// using std::set;

// #include<sstream>
// using std::stringstream;

// #include<string>
// using std::getline;
// using std::string;
// using std::to_string;

// #include<utility>
// using std::make_pair;
// using std::pair;

// #include<unordered_map>
// using std::unordered_map;

// #include<unordered_set>
// using std::unordered_set;

// #include<vector>
// using std::vector;
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
#define up(i,a,b) for(i=a;i<(b);++i)
#define dn(i,a,b) for(i=a;i>(b);--i)
#define pr make_pair
typedef unsigned char unc;
typedef unsigned short uns;
typedef unsigned uni;
typedef unsigned long unl;
typedef long long ll;
typedef unsigned long long ull;
const int BUF_SIZE(1<<14);
bool ___f;
char ___c,___a[45],*___p,___ibuf[BUF_SIZE+1],*___ib(___ibuf),*___ie(___ibuf),___obuf[BUF_SIZE+1],*___ob(___obuf),*___oe(___obuf+BUF_SIZE);
char& gtch(){if(___ib==___ie)___ie=(___ib=___ibuf)+fread(___ibuf,1,BUF_SIZE,stdin);if(___ib==___ie){return *___ibuf=-1;}return *___ib++;}
void ___flush(){fwrite(___obuf,1,___ob-___obuf,stdout);___ob=___obuf;}
void ptch(char c){if(___ob==___oe)___flush();*___ob=c;++___ob;}
typedef __int128 pll;
typedef unsigned __int128 upll;
void rd(pll &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(upll &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void wt(pll r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(upll r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void rd(bool &r){r=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r|=bool(___c^'0');}}
void rd(char &c){for(c=gtch();c==' '||c=='\r'||c=='\n';c=gtch());}
void rd(short &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(short)(___c^'0');}if(___f){r=~(r-1);}}
void rd(int &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(long &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(ll &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(unc &c){for(c=gtch();c==' '||c=='\r'||c=='\n';c=gtch());}
void rd(uns &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(uns)(___c^'0');}}
void rd(uni &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(unl &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(ull &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(char *s){for(*s=gtch();*s==' '||*s=='\r'||*s=='\n';*s=gtch());for(;~*s&&*s!=' '&&*s!='\r'&&*s!='\n';++s,*s=gtch());*s=0;}
void rd(char *s,char n){for(*s=gtch();*s==' '||*s=='\r'||*s=='\n';*s=gtch());for(;~*s&&*s!=n;++s,*s=gtch());*s=0;}
void wt(bool a){ptch('0'+a);}
void wt(char c){ptch(c);}
void wt(short r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(int r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(long r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(ll r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(unc c){ptch(c);}
void wt(uns r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(uni r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(unl r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(ull r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(char *s){for(;*s;++s){ptch(*s);}}
void wt(const char *s){for(;*s;++s){ptch(*s);}}
template<typename T,typename ...T1>void rd(T &a,T1 &...b){rd(a);rd(b...);}
template<typename T,typename ...T1>void wt(T a,T1 ...b){wt(a);wt(b...);}
template<typename T>void RD(T* a,int n=1){while(n--){rd(*a);++a;}}
ll llabs1(ll a){return a<0?-a:a;}
template<typename T>T ___min(T &a,T &b){return a<b?a:b;}
template<typename T,typename ...T1>T ___min(T &a,T &b,T1 &...c){return ___min(a,b=___min(b,c...));}
template<typename ...T>auto min(T ...a){return ___min(a...);}
template<typename T>T ___max(T &a,T &b){return a>b?a:b;}
template<typename T,typename ...T1>T ___max(T &a,T &b,T1 &...c){return ___max(a,b=___max(b,c...));}
template<typename ...T>auto max(T ...a){return ___max(a...);}
/*

*/
const int N((1<<11)+5),SQRT_N((1<<6)+5);
int n,m;
struct node{
	int sum,lz;
};
struct segment_tree{
	node t[N<<2];
	int ls(int p){return p<<1;}
	int rs(int p){return p<<1|1;}
	void push_u(int p){
		t[p].sum+t[ls(p)].sum+t[rs(p)].sum;
	}
	void build(int* a,int p,int l,int r){
		int mid((l+r)>>1);
		t[p].lz=0;
		if(l==r){
			t[p].sum=a[l];return;
		}
		build(a,ls(p),l,mid);
		build(a,rs(p),mid+1,r);
		push_u(p);
	}
	void tag(int k,int p,int l,int r){
		t[p].sum+=(r-l+1)*k;
		t[p].lz+=k;
	}
	void push_d(int p,int l,int r){
		int mid((l+r)>>1);
		if(t[p].lz){
			tag(t[p].lz,ls(p),l,mid);
			tag(t[p].lz,rs(p),mid+1,r);
			t[p].lz=0;
		}
	}
	void update(int x,int y,int k,int p,int l,int r){
		int mid((l+r)>>1);
		if(x<=l&&r<=y){
			tag(k,p,l,r);return;
		}
		push_d(p,l,r);
		if(x<=mid){
			update(x,y,k,ls(p),l,mid);
		}
		if(mid<y){
			update(x,y,k,rs(p),mid+1,r);
		}
		push_u(p);
	}
	int query(int x,int y,int p,int l,int r){
		int mid((l+r)>>1),res(0);
		if(x<=l&&r<=y){
			return t[p].sum;
		}
		push_d(p,l,r);
		if(x<=mid){
			res+=query(x,y,ls(p),l,mid);
		}
		if(mid<y){
			res+=query(x,y,rs(p),mid+1,r);
		}
		return res;
	}
};
struct Blocking{
	int block,ld[N],rd[N],pos[N];
	segment_tree a[N],sum[SQRT_N],add[SQRT_N];
	void update(int x1,int y1,int x2,int y2,int k){
		int i,num;
		if(pos[x1]==pos[x2]){
			UP(i,x1,x2){
				a[i].update(y1,y2,k,1,1,m);
			}
			sum[pos[x1]].update(y1,y2,k*(x2-x1+1),1,1,m);
		}else{
			num=0;
			while(pos[x1]==pos[x1-1]){
				a[x1].update(y1,y2,k,1,1,m);
				++x1;++num;
			}
			sum[pos[x1]-1].update(y1,y2,num*k,1,1,m);
			num=0;
			while(pos[x2]==pos[x2+1]){
				a[x2].update(y1,y2,k,1,1,m);
				--x2;++num;
			}
			sum[pos[x2]+1].update(y1,y2,num*k,1,1,m);
			x1=pos[x1];x2=pos[x2];
			UP(i,x1,x2){
				add[i].update(y1,y2,k,1,1,m);
			}
		}
	}
	int query(int x1,int y1,int x2,int y2){
		int i,num,res(0);
		if(pos[x1]==pos[x2]){
			UP(i,x1,x2){
				res+=a[i].query(y1,y2,1,1,m);
			}
			res+=add[pos[x1]].query(y1,y2,1,1,m)*(x2-x1+1);
		}else{
			num=0;
			while(pos[x1]==pos[x1-1]){
				res+=a[x1].query(y1,y2,1,1,m);
				++x1;++num;
			}
			res+=add[pos[x1]-1].query(y1,y2,1,1,m)*num;
			num=0;
			while(pos[x2]==pos[x2+1]){
				res+=a[x2].query(y1,y2,1,1,m);
				--x2;++num;
			}
			res+=add[pos[x2]+1].query(y1,y2,1,1,m)*num;
			x1=pos[x1];x2=pos[x2];
			UP(i,x1,x2){
				res+=sum[i].query(y1,y2,1,1,m)+add[i].query(y1,y2,1,1,m)*(rd[i]-ld[i]+1);
			}
		}
		return res;
	}
	void travel(){
		int i,j;
		UP(i,1,n){
			UP(j,1,m){
				printf("%d%c",a[i].query(j,j,1,1,m)+add[pos[i]].query(j,j,1,1,m)," \n"[j==m]);
			}
		}
		printf("\n");
	}
	void init(){
		int i;
		block=sqrt(n);
		UP(i,1,n){
			ld[i]=1e9;
			pos[i]=(i-1)/block+1;
			ld[pos[i]]=min(ld[pos[i]],i);
			rd[pos[i]]=max(rd[pos[i]],i);
		}
	}
}sol;

void main1(){
	char o;
	int x1,y1,x2,y2,k;
	scanf("X %d%d",&n,&m);
	sol.init();
	while(~scanf("\n%c%d%d%d%d",&o,&x1,&y1,&x2,&y2)){
		if(o=='L'){
			scanf("%d",&k);
			sol.update(x1,y1,x2,y2,k);
		}else{
			wt(sol.query(x1,y1,x2,y2),'\n');
		}
		// sol.travel();
	}
}
int main(){if(___coding1)freopen("in.txt","r",stdin);main1();___flush();if(___coding1){freopen("CON","r",stdin);system("pause");}return 0;}
2024/8/9 11:48