样例过了,提交全 WA
查看原帖
样例过了,提交全 WA
635555
Pol_Pot楼主2023/10/11 13:29

机房同学已经调晕了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
int n,m,q;
struct Node{
	int left,right,num;
} tree1[MAXN*4],tree2[MAXN*4];
int left_son(int pos){
	return pos<<1;
}
int right_son(int pos){
	return pos<<1|1;
}
void build1(int pos,int left,int right){
	tree1[pos].left=left;
	tree1[pos].right=right;
	tree1[pos].num=0;
	if (left==right){
		return ;
	}
	int mid=(left+right)/2;
	build1(left_son(pos),left,mid);
	build1(right_son(pos),mid+1,right);
}
void build2(int pos,int left,int right){
	tree2[pos].left=left;
	tree2[pos].right=right;
	tree2[pos].num=0;
	if (left==right){
		return ;
	}
	int mid=(left+right)/2;
	build2(left_son(pos),left,mid);
	build2(right_son(pos),mid+1,right);
}
void update1(int pos,int num){
	if (tree1[pos].left==tree1[pos].right){
		tree1[pos].num=tree1[pos].num^1;
//		tree1[pos].num=(tree1[pos].num+1)%2;
		return ;
	} 
	int mid=(tree1[pos].left+tree1[pos].right)/2;
	if (num<=mid){
		update1(left_son(pos),num);
	}
	else {
		update1(right_son(pos),num);
	}
	tree1[pos].num=tree1[left_son(pos)].num+tree1[right_son(pos)].num;
}
void update2(int pos,int num){
	if (tree2[pos].left==tree2[pos].right){
		tree2[pos].num=tree2[pos].num^1;
//		tree2[pos].num=(tree2[pos].num+1)%2;
		return ;
	} 
	int mid=(tree2[pos].left+tree2[pos].right)/2;
	if (num<=mid){
		update2(left_son(pos),num);
	}
	else {
		update2(right_son(pos),num);
	}
	tree2[pos].num=tree2[left_son(pos)].num+tree2[right_son(pos)].num;
}
int query1(int pos,int left,int right){
	if (tree1[pos].left>=left and tree1[pos].right<=right){
		return tree1[pos].num;
	}
	int mid=(tree1[pos].left+tree1[pos].right)/2;
	int cnt=0;
	if (right<=mid){
		cnt+=query1(left_son(pos),left,right);
	}
	if (left>mid){
		cnt+=query1(right_son(pos),left,right);
	}
	return cnt;
}
int query2(int pos,int left,int right){
	if (tree2[pos].left>=left and tree2[pos].right<=right){
		return tree2[pos].num;
	}
	int mid=(tree2[pos].left+tree2[pos].right)/2;
	int cnt=0;
	if (left<=mid){
		cnt+=query2(left_son(pos),left,right);
	}
	if (right>mid){
		cnt+=query2(right_son(pos),left,right);
	}
	return cnt;
}
signed main(){
	cin>>n>>m>>q;
	build1(1,1,n);
	build2(1,1,m);
	for (int i=1;i<=q;i++){
		int op;
		cin>>op;
		if (op==1){
			int x,y;
			cin>>x>>y;
			update1(1,x);
			update2(1,y);
		}
		if (op==2){
			int ax,ay,bx,by;
			cin>>ax>>ay>>bx>>by;
			int ans1=query1(1,ax,bx);
			int ans2=query2(1,ay,by);
//			cout<<ans1<<" "<<ans2<<"\n"; 
			cout<<ans1*(by-ay+1)+ans2*(bx-ax+1)-2*ans1*ans2<<endl;
		}
	}
	return 0;
} 

马蜂丑陋见谅

2023/10/11 13:29
加载中...