題意：
? ? ?給一個(gè)n*n的01矩陣，然后有兩種操作（m次）C x1 y1 x2 y2是把這個(gè)小矩形內(nèi)所有數(shù)字異或一遍，Q x y 是詢問(wèn)當(dāng)前這個(gè)點(diǎn)的值是多少？n<=1000 m<=50000.


思路：
? ? ?做的有點(diǎn)蛋疼，昨天自己用了將近5個(gè)小時(shí)自己研究了兩個(gè)二維線段樹(shù)的算法，都失敗了，其實(shí)我想到的第二個(gè)算法和網(wǎng)上那個(gè)差不多（后來(lái)看網(wǎng)上的思路才發(fā)現(xiàn)），但是我考慮的是段更新的PushDown的問(wèn)題，其實(shí)這個(gè)題目是段更新，*點(diǎn)詢問(wèn)*，根據(jù)這個(gè)可以簡(jiǎn)化問(wèn)題，思路很容易想到可以是線段樹(shù)的線段樹(shù)，就是線段樹(shù)跑X確定區(qū)間后再線段樹(shù)去更新y,但是有幾點(diǎn)需要注意
1. 可以不用Pushup，Pushdown(因?yàn)槭屈c(diǎn)詢問(wèn)，一開(kāi)始我就考慮段詢問(wèn)，各種自己設(shè)想，研究而且還寫(xiě)了個(gè)上下左右更新，就是把線段映射成平面，最后悲劇了..你懂的)
2.*當(dāng)更新大矩形的時(shí)候那么他里面的小矩形也相當(dāng)于更新了，就是假如現(xiàn)在更新

（1,1）（5,5）（1,5），（5,1）這個(gè)矩形的時(shí)候我們是找到位置直接就return了，其實(shí)（1,1）（2,2），（1,2），（2,1）也更新了，但是我們沒(méi)有繼續(xù)往下走，所以當(dāng)我們尋找答案的時(shí)候要一路加過(guò)來(lái)，這個(gè)是重點(diǎn)，這么說(shuō)可能不懂，但是可以看幾遍代碼，我當(dāng)時(shí)看了下代碼馬上就懂了，可能是我昨天想的要比正解難很多，想到頭疼，而且思路相近，所以一看就懂了，但是不管是誰(shuí)，只要考慮過(guò)，應(yīng)該很容易懂，很可惜下面的代碼的思路并不是我自己想出來(lái)的。

#include<stdio.h> #include<string.h>#define xlson xl ,xmid ,xt << 1 #define xrson xmid+1 ,xr ,xt << 1 | 1 #define ylson yl ,ymid ,yt << 1 #define yrson ymid+1 ,yr ,yt << 1 | 1 #define N 1005int cnt[N<<2][N<<2] ,n ,ans; void UpdateY(int yl ,int yr ,int yt ,int c ,int d ,int xt) {if(c <= yl && d >= yr){cnt[xt][yt] ++;return ;}int ymid = (yl + yr) >> 1;if(c <= ymid) UpdateY(ylson ,c ,d ,xt);if(d > ymid) UpdateY(yrson ,c ,d ,xt);return ; }void UpdateX(int xl ,int xr ,int xt ,int a ,int b ,int c ,int d) {if(a <= xl && b >= xr){UpdateY(1 ,n ,1 ,c ,d ,xt);return ;}int xmid = (xl + xr) >> 1;if(a <= xmid) UpdateX(xlson ,a ,b ,c ,d);if(b > xmid) UpdateX(xrson ,a ,b ,c ,d);return ; }void QueryY(int yl ,int yr ,int yt ,int b ,int xt) {ans += cnt[xt][yt];if(yl == yr) return ;int ymid = (yl + yr) >> 1;if(b <= ymid) QueryY(ylson ,b ,xt);else QueryY(yrson ,b ,xt);return ;}void QueryX(int xl ,int xr ,int xt ,int a ,int b) {QueryY(1 ,n ,1 ,b ,xt);if(xl == xr) return ;int xmid = (xl + xr) >> 1;if(a <= xmid) QueryX(xlson ,a ,b);else QueryX(xrson ,a ,b);return ; }int main () {int t ,m ,i ,x1 ,y1 ,x2 ,y2;char str[5];scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);memset(cnt ,0 ,sizeof(cnt));while(m--){scanf("%s" ,str);if(str[0] == 'C'){scanf("%d %d %d %d" ,&x1 ,&y1 ,&x2 ,&y2);UpdateX(1 ,n ,1 ,x1 ,x2 ,y1 ,y2);}else{scanf("%d %d" ,&x1 ,&y1);ans = 0;QueryX(1 ,n ,1 ,x1 ,y1);if(ans % 2)printf("1\n");else printf("0\n");}}if(t) printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ2155二维线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。