html5韩国网站模板,最美情侣免费观看视频在线,建网站找那家好,市场营销互联网营销Problem F 发布时间: 2017年6月28日 10:31 最后更新: 2017年6月29日 21:35 时间限制: 2000ms 内存限制: 64M 描述 给定一个nm的矩形, 初始时所有元素都为0给出q个操作, 操作有三种 对于形如1x的操作, 将第x行的所有元素异或1对于形如2y的操作, 将第y列的所有元素异或1对于… Problem F 发布时间: 2017年6月28日 10:31 最后更新: 2017年6月29日 21:35 时间限制: 2000ms 内存限制: 64M 描述 给定一个n×m的矩形, 初始时所有元素都为0 给出q个操作, 操作有三种 对于形如1 x的操作, 将第x行的所有元素异或1 对于形如2 y的操作, 将第y列的所有元素异或1 对于形如3 x1 y1 x2 y2的操作, 输出(x1,y1)-(x2,y2)这段矩形区域内1的个数 9×105≤n≤106, 9×105≤m≤106, 9×105≤q≤106 输入 第一行三个整数n, m, q, 意义如上所述。 接下来q行, 每行第一个数为opt, 如果opt1或opt2, 后面紧跟一个数, 意义如上所述; 如果opt3, 后面紧跟四个数, 意义如上所述。 输出 对于每个操作3, 输出答案, 一行一个。 样例输入1 复制 4 4 5
3 1 1 4 4
1 4
3 1 1 4 4
2 4
3 1 1 4 4 样例输出1 0
4
6 大水题一道我们知道异或的特性如果有1个数他本身进行偶数次异或那么就是0
这道题我们这样想对于一行来说异或奇数次是一样的异或偶数次也是一样的。
那么这个问题就可以简化我们按行建一个树状数组里面保存有多少行的 异或次数为奇数次。
我们再按照列建一个树状数组里面保存有多少列的异或次数为奇数次。
那么要求矩阵x1,x2,y1,y2里的1的个数1的个数就等于(row[x2]-row[x1-1])*(y2-y11) (col[y2] - col[y1-1])*(x2-x11) - 2*(row[x2]-row[x1-1])*(row[x2]-row[x1-1])
其中row[i]与col[i]都可以log(n)时间内用树状数组求出来 代码 #include iostream
#include algorithm
#include cstdio
using namespace std;
const int MAX 1e67;
int row[MAX];
int mark_row[MAX];
int mark_col[MAX];
int col[MAX];
int n,m,q;
inline int lowbit(int x){return x (-x);
}
void add(int in[],int pos,int val){while(pos MAX){in[pos] val;pos lowbit(pos);}
}
int getsum(int in[],int pos){int res 0;while(pos){res in[pos];pos - lowbit(pos);}return res;
}
int main(){scanf(%d%d%d,n,m,q);while(q--){int opt;scanf(%d,opt);if(opt 1){int x;scanf(%d,x);if(mark_row[x]){add(row,x,-1);mark_row[x] 0;}else{add(row,x,1);mark_row[x] 1;}}else if(opt 2){int x;scanf(%d,x);if(mark_col[x]){add(col,x,-1);mark_col[x] 0;}else{add(col,x,1);mark_col[x] 1;}}else{int x1,x2,y1,y2;scanf(%d%d%d%d,x1,y1,x2,y2);int ans1 getsum(row,x2) - getsum(row,x1-1);int ans2 getsum(col,y2) - getsum(col,y1-1);int ans ans1*(y2-y11) ans2*(x2-x11) - 2*ans1*ans2;printf(%d\n,ans);}}return 0;
}
