树状数组求调
查看原帖
树状数组求调
1023658
wxyz13755162073楼主2025/6/30 19:54

90pts不知道错哪了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],b[100005],c1[100005],c2[100005],n,m,q;
int lowbit(int x){
	return x&(-x);
}
void add1(int x,int v){
	while(x<=n){
		c1[x]+=v;
		x+=lowbit(x);
	}
}
int query1(int x){
	int sum=0;
	while(x){
		sum+=c1[x];
		x-=lowbit(x);
	}
	return sum;
}
void add2(int x,int v){
	while(x<=n){
		c2[x]+=v;
		x+=lowbit(x);
	}
}
int query2(int x){
	int sum=0;
	while(x){
		sum+=c2[x];
		x-=lowbit(x);
	}
	return sum;
}
signed main(){
	cin>>n>>m>>q;
	while(q--){
		int opt,x,y,x1,y1_;
		cin>>opt;
		if(opt==1){
			cin>>x>>y;
			if(a[x]==1)add1(x,-1);
			else add1(x,1);
			if(b[y]==1)add2(y,-1);
			else add2(y,1);
			b[y]^=1,a[x]^=1;
		}
		else{
			cin>>x>>y>>x1>>y1_;
			cout<<(x1-x+1)*(query2(y1_)-query2(y-1))+(y1_-y+1)*(query1(x1)-query1(x-1))-(query2(y1_)-query2(y-1))*(query1(x1)-query1(x-1))*2<<'\n';
		}
	}
	return 0;
}
2025/6/30 19:54
加载中...