首页 > 代码库 > POJ 2155 二维线段树 经典的记录所有修改再统一遍历 单点查询

POJ 2155 二维线段树 经典的记录所有修改再统一遍历 单点查询

2024-07-13 17:36:05   210人阅读

本来是想找一个二维线段树涉及懒惰标记的，一看这个题，区间修改，单点查询，以为是懒惰标记，敲到一半发现这二维线段树就不适合懒惰标记，你更新了某段的某列，但其实其他段的相应列也要打标记，但因为区间不一样，又不好打。。。也可能是我这是在套用一维线段树的思想，还有更好的二维线段树懒惰标记方法

反正到现在我还没搞定二维线段树的懒惰标记，因为这道题不用懒惰标记，因为是二进制序列，区间修改仅限于翻转操作，那就只要记录每次操作，最后查询的时候从上往下把所有修改都来上一遍，就可以了。就类似于树状数组的第二种用法，每次区间修改，最后查询的时候把前面的修改都给加起来。

即区间修改的时候，定位到某段某区间列进行标记，单独查询的时候，针对每个行段的该列所在区间都遍历一遍，把所有的修改都遍历到之后就是结果了

#include <iostream>#include <cstdio>#include <cstring>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,rusing namespace std;const int N=1010;int d[N*3][N*3];int flag[N*3][N*3];int n,Q;void buildc(int k,int rt,int l,int r){    d[k][rt]=0;    if (l>=r){        return;    }    int mid=(l+r)>>1;    buildc(k,lson);    buildc(k,rson);}void buildr(int rt,int l,int r){    buildc(rt,1,1,n);    if (l>=r){        return;    }    int mid=(l+r)>>1;    buildr(lson);    buildr(rson);}void fixc(int k,int c1,int c2,int rt,int l,int r){    if (c1<=l && r<=c2){        d[k][rt]^=1;        return;    }    int mid=(l+r)>>1;    if (c1>mid) fixc(k,c1,c2,rson);    else    if (c2<=mid) fixc(k,c1,c2,lson);    else{        fixc(k,c1,c2,lson);        fixc(k,c1,c2,rson);    }}void fixr(int r1,int r2,int c1,int c2,int rt,int l,int r){    if (r1<=l && r<=r2){        fixc(rt,c1,c2,1,1,n);        return;    }    int mid=(l+r)>>1;    if (r1>mid) fixr(r1,r2,c1,c2,rson);    else    if (r2<=mid) fixr(r1,r2,c1,c2,lson);    else{        fixr(r1,r2,c1,c2,lson);        fixr(r1,r2,c1,c2,rson);    }}void queryc(int& ans,int k,int C,int rt,int l,int r){    if (d[k][rt]){        ans^=1;    }    if (l>=r){        return ;    }    int mid=(l+r)>>1;    if (mid>=C)    queryc(ans,k,C,lson);    else    queryc(ans,k,C,rson);}void queryr(int& ans,int R,int C,int rt,int l,int r){    queryc(ans,rt,C,1,1,n);    if (l>=r){        return;    }    int mid=(l+r)>>1;    if (R<=mid)  queryr(ans,R,C,lson);    else    queryr(ans,R,C,rson);}int main(){    char ch[5];    int a,b,c,d;    int t;    scanf("%d",&t);    while (t--)    {       scanf("%d%d",&n,&Q);       buildr(1,1,n);       while (Q--)       {           scanf("%s",ch);           if (ch[0]==‘C‘){               scanf("%d%d%d%d",&a,&b,&c,&d);               fixr(a,c,b,d,1,1,n);           }           else {               scanf("%d%d",&a,&b);               int ans=0;               queryr(ans,a,b,1,1,n);               printf("%d\n",ans);           }       }       if (t) puts("");    }    return 0;}

　　


联系
我们