1157: 新年彩燈Ⅱ

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?56??Solved:?17
[Submit][Status][Web Board]

Description

新年將至，YY準備掛一片彩燈，形狀呈矩形，已知彩燈剛掛完的彩燈共有N*N盞（第一排編號為(1,1),(1,2),(1,3),……，第二排編號為(2,1),(2,2),(2,3)……第N排編號為(N,1),(N,2)……(N,N)），并且都是滅的。彩燈的閃爍由一段程序控制。

?

每一秒鐘程序會生成四個正整數a1,b1,a2,b2（1<=a1,b1,a2,b2<=N），然后將編號(x,y)滿足x在a1與a2之間，y在b1與b2之間的燈狀態改變一次，即如果燈(x,y)是滅的，那么經過一次改變，燈(x,y)會亮，如果燈(x,y)是亮的，經過一次改變，燈(x,y)會滅。

當YY看著自己掛的彩燈不斷閃爍的時候，問題來了，YY想知道任意時刻某盞燈的狀態。

?

Input

多組測試數據，每一組第一行是一個整數N（1<=N<=1000）和一個整數M(1<=M<=3000)。

然后是M行數據，包括以下兩種形式：

?????????1 a1 b1 a2 b2?表示將編號(x,y)滿足x在a1與a2之間，y在b1與b2之間的燈狀態改變一次。

?????????0 x y?表示YY想知道此刻編號(x,y)的燈狀態。

Output

對于每組測試數據首先輸出“Case #:”（'#'表示case序數）

對于每次YY想知道結果的時候，輸出燈的狀態，如果是亮的輸出”1”，否則輸出”0”;

Sample Input

3 5

1 1 1 2 2

1 2 2 3 3

0 1 1

0 2 2

0 3 3

2 3

0 1 1

1 1 1 2 2

0 1 1

Sample Output

Case 1:

1

0

1

Case 2:

0

1

二維樹狀數組單點查詢

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int maxn=1010; int n,m,q; int c[maxn][maxn];int lowbit(int x) {return x&-x; } void add(int x,int y,int v) {int yy=y;while(x<=n){y=yy;while(y<=n){c[x][y]+=v;y+=lowbit(y);}x+=lowbit(x);} }int getsum(int x,int y) {int sum=0;int yy=y;while(x>0){y=yy;while(y>0){sum+=c[x][y];y-=lowbit(y);}x-=lowbit(x);}return sum; } int main() {int cas=1;while(~scanf("%d%d",&n,&m)){mem(c,0);printf("Case %d:\n",cas++);while(m--){int q;scanf("%d",&q);if(q==1){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);if(x1>x2){int t=x1;x1=x2;x2=t;}if(y1>y2){int t=y1;y1=y2;y2=t;}add(x1,y1,1);add(x1,y2+1,-1);add(x2+1,y1,-1);add(x2+1,y2+1,1);}else{int x,y;scanf("%d%d",&x,&y);printf("%d\n",getsum(x,y)&1);}}}return 0; }

?

總結

以上是生活随笔為你收集整理的zcmu1157: 新年彩灯Ⅱ（二维树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

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