玄关,感觉线段树写的没问题啊,为什么爆零WA了
查看原帖
玄关,感觉线段树写的没问题啊,为什么爆零WA了
923248
Lian_zy楼主2024/12/20 18:18
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;

struct node{
	ll l,r;
	ll sum;
}h[N<<2],c[N<<2];
ll n,m,q,x,y,z,w,op,H1,L1;
void push_uph(ll x){
	h[x].sum=h[x<<1].sum+h[x<<1|1].sum;
	return;
}
void push_upl(ll x){
	c[x].sum=c[x<<1].sum+c[x<<1|1].sum;
	return;
}
void buildh(ll x,ll l,ll r){
	h[x].l=l;
	h[x].r=r;
	if(l==r)return;
	ll mid=l+r>>1;
	buildh(x<<1,l,mid);
	buildh(x<<1|1,mid+1,r);
	return;
}
void buildl(ll x,ll l,ll r){
	c[x].l=l;
	c[x].r=r;
	if(l==r)return;
	ll mid=l+r>>1;
	buildl(x<<1,l,mid);
	buildl(x<<1|1,mid+1,r);
	return;
}
void updateh(ll x,ll p){
	ll L=h[x].l;
	ll R=h[x].r;
	if(L==R){
		h[x].sum^=1;
		return;
	}
	ll mid=L+R>>1;
	if(p<=mid)updateh(x<<1,p);
	else updateh(x<<1|1,p);
	push_uph(x);
	return;
}
void updatel(ll x,ll p){
	ll L=c[x].l;
	ll R=c[x].r;
	if(L==R){
		c[x].sum^=1;
		return;
	}
	ll mid=L+R>>1;
	if(p<=mid)updatel(x<<1,p);
	else updatel(x<<1|1,p);
	push_upl(x);
	return;
}
ll queryh(ll x,ll l,ll r){
	ll L=h[x].l;
	ll R=h[x].r;
	if(l<=L&&R<=r)return h[x].sum;
	ll ans=0;
	ll mid=L+R>>1;
	if(l<=mid)ans+=queryh(x<<1,l,r);
	if(r>mid)ans+=queryh(x<<1|1,l,r);
	return ans;
}
ll queryl(ll x,ll l,ll r){
	ll L=c[x].l;
	ll R=c[x].r;
	if(l<=L&&R<=r)return c[x].sum;
	ll ans=0;
	ll mid=L+R>>1;
	if(l<=mid)ans+=queryl(x<<1,l,r);
	if(r>mid)ans+=queryl(x<<1|1,l,r);
	return ans;
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&q);
	buildh(1,1,n);
	buildl(1,1,m);
	while(q--){
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld",&x,&y);
			updateh(1,x);
			updatel(1,y);
		}else{
			scanf("%lld%lld%lld%lld",&x,&y,&z,&w);
			H1=queryh(1,x,z);
			L1=queryl(1,y,w);
			printf("%lld\n",1ll*H1*(z-x+1)*L1*(w-y+1)-(H1*L1<<1));
		}
	}
	return 0;
}
2024/12/20 18:18
加载中...