首页 > 代码库 > HDU 5892 Resident Evil
HDU 5892 Resident Evil
题目链接：传送门
题目大意：有50种动物，给你n*n的矩阵，m次操作，P代表加入操作，在左上角 x1,y1 到右下角 x2,y2,的矩形范围内加入
种类为x，数量为y的动物。
Q代表询问操作，在左上角 x1,y1 到右下角 x2,y2，对于1~50种动物，如果数量之和为偶数，输出1，否则输出2。
题目思路：树状数组 区间异或，区间查询。
/*--------------------------------------------------分割线-------------------------------------------------------------*/
以下均考虑树状数组维护异或值
我们首先要知道树状数组都是向后更新，向前查询的。
首先考虑简单的问题
如果要求一维空间，单点修改，区间查询，那这个就直接像普通树状数组那样，修改和查询时把+改成^就行了。
如果要求一维空间，区间修改，区间查询，这时候就不能像普通树状数组那么改了。不信可以试试。:)
如果异或更新 [x,y] ^v
我们知道这样一个性质，假如对于位置 x，那么x+1，x+3，x+7...这些位置上的值是不会被V影响的。
因为更新时这些位置上的数异或V偶数次，值不会受影响。只有与 x 奇偶性相同的位置 x+2，x+4...才会被更新。
因此，我们可以开个二维数组tree[2][maxn]，只修改 x奇偶性对应的那一维，比如可以写成 x&1，偶数修改0，奇数修改1
查询时对应奇偶性查询。
本题要求二维空间，区间修改，区间查询，那么扩展一下，开4个数组即可。
然后我们把对应的50种动物状态压缩 1<<50，开LL tree[4][3001][3001],这样不会爆空间。
然后对于加入的动物数量，首先不用去管面积，直接用给的数量值（因为 偶*奇==偶，偶*偶==偶）
所以只要加入偶数数量就不用管，因为数量永远是偶数，而初始值0也是偶数，也就是对答案没影响。
对于加入奇数的情况，就必须老老实实加入（奇*奇==奇，奇*偶==偶），面积会对奇数情况有影响。
之后只需按上诉方法异或即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 #include <stack> 8 #include <cctype> 9 #include <queue>10 #include <string>11 #include <vector>12 #include <set>13 #include <map>14 #include <climits>15 #define lson rt<<1,l,mid16 #define rson rt<<1|1,mid+1,r17 #define fi first18 #define se second19 #define ping(x,y) ((x-y)*(x-y))20 #define mst(x,y) memset(x,y,sizeof(x))21 #define mcp(x,y) memcpy(x,y,sizeof(y))22 using namespace std;23 #define gamma 0.577215664901532860606512024 #define mod 100000000725 #define inf 0x3f3f3f3f26 #define N 100505027 #define maxn 300128 typedef pair<int,int> PII;29 typedef long long LL;30 31 int n,m,k,x,y,v;32 LL tree[2][2][3001][3001];33 int x1,y1,x2,y2;34 LL mon[50];35 void add(int x,int y,LL v){36 for(int i=x;i<=n;i+=(i&-i))37 for(int j=y;j<=n;j+=(j&-j))38 tree[x&1][y&1][i][j]^=v;39 }40 LL query(int x,int y){41 LL res=0;42 for(int i=x;i;i-=(i&-i))43 for(int j=y;j;j-=(j&-j))44 res^=tree[x&1][y&1][i][j];45 return res;46 }47 int main(){48 //freopen("in.txt","r",stdin);49 int i,j,group;50 char ch;51 while(scanf("%d%d",&n,&m)!=EOF){52 mst(tree,0);53 while(m--){54 scanf(" %c%d%d%d%d",&ch,&x1,&y1,&x2,&y2);55 if(ch==‘P‘){56 mst(mon,0);57 scanf("%d",&k);58 while(k--){59 scanf("%d%d",&x,&y);60 --x;61 mon[x]+=y;62 }63 LL temp=0;64 for(i=0; i<50; ++i){65 if(mon[i]&1)66 temp|=(1ll<<i);67 }68 ++x2;++y2;69 add(x1,y1,temp);70 add(x2,y2,temp);71 add(x1,y2,temp);72 add(x2,y1,temp);73 }74 else{75 --x1,--y1;76 LL temp=query(x1,y1)^query(x2,y2)^query(x1,y2)^query(x2,y1);77 for(i=0;i<50;++i)78 if(temp&(1ll<<i))printf("2 ");79 else printf("1 ");80 printf("\n");81 }82 }83 }84 return 0;85 }
HDU 5892 Resident Evil