二维树状数组 + 叉分
区间修改转化为单点修改
单点查询本来就可视为区间查询
于是本题可解
PS: 不知道为什么函数传参数, 传的是变量就会出现奇奇怪怪的问题?
所以读入单独写了, 还有就是循环的初始化硬是多定义了一组变量, 头大啊!
暂且把这种写法视为标准写法吧!
- #include <set>
- #include <map>
- #include <cmath>
- #include <queue>
- #include <vector>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int MAXN=1001;
- int t[MAXN][MAXN],n;
- int lb(int i){return i&-i;}
- void init(){memset(t,0,sizeof(t));}
- void add(int x,int y,int v){
- for(int i=x;i<=n;i+=lb(i))for(int j=y;j<=n;j+=lb(j))t[i][j]+=v;
- }
- int sum(int x,int y){
- int ans=0;for(int i=x;i;i-=lb(i))for(int j=y;j;j-=lb(j))ans+=t[i][j];return ans;
- }
- int a,b,c,d,x,T;char s[5];
- void C(){cin>>a>>b>>c>>d;add(a,b,1),add(c+1,b,1),add(a,d+1,1),add(c+1,d+1,1);}
- void Q(){cin>>a>>b;cout<<sum(a,b)%2<<endl;}
- int main(){
- for(scanf("%d",&x);x--;x?puts(""):0){
- scanf("%d%d",&n,&T),init();
- while(T--)scanf("%s",s),s[0]=='C'?C():Q();
- }
- }
来源: http://www.bubuko.com/infodetail-3414610.html