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, 如果opt=1或opt=2, 后面緊跟一個數, 意義如上所述; 如果opt=3, 后面緊跟四個數, 意義如上所述。

輸出

對于每個操作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-y1+1) + (col[y2] - col[y1-1])*(x2-x1+1) - 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 = 1e6+7; 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-y1+1) + ans2*(x2-x1+1) - 2*ans1*ans2;printf("%d\n",ans);}}return 0; }

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的2017西安交大ACM小学期数据结构 [又是树状数组、异或]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。