首页 > 代码库 > HDU_4819 二维线段树

HDU_4819 二维线段树

2024-07-13 13:14:00   213人阅读

13年长春现场赛的G题，赤裸裸的二维线段树，单点更新，区间查询

不过我是第一次写二维的，一开始写T了，原因是我没有好好利用行段，说白一点，还是相当于枚举行，然后对列进行线段树，那要你写二维线段树干嘛

二维就是在每个行段也建一棵树，来代表这个区间的行里的某些列的值

其他操作倒是不难，因为有一维的功底，只是多写一个，刷刷刷就出来了

就是更新操作的时候有点麻烦，up函数不好写，必须先更新底层，复层是区间值，无法先进行更新，然后底层向父层转移也是有点小技巧，因为每个行段点里面的某些列的列端点号肯定是相同的，比如 我dp[1][rt]和dp[2][rt]，表示的都是同样的列，只是一个是儿子行，一个是父亲行，父亲行是>儿子行的，所以更新到底层的时候，就往上每次对第一维除2来更新父节点的相关区域即可

还有发现这个不好直接复制，本题是维护最小值和最大值，在建树的时候，直接修改不太好，先把所有的点的最大设置为-inf，最小设置为INF，这样以修改的方式去赋初值，包括之后的修改也是这样。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define INF 1<<30using namespace std;const int N = 810;int ds[N*3][N*3];int db[N*3][N*3];int flag[N*3][N*3];int n;int A[N][N];struct node{    int mini,maxn;};void up(int k,int rt){    db[k][rt]=max(db[k][rt<<1],db[k][rt<<1|1]);    ds[k][rt]=min(ds[k][rt<<1],ds[k][rt<<1|1]);    for (int i=(k>>1);i;i>>=1){        db[i][rt]=max(db[i<<1][rt],db[i<<1|1][rt]);        ds[i][rt]=min(ds[i<<1][rt],ds[i<<1|1][rt]);    }}void buildc(int k,int rt,int l,int r){    db[k][rt]=-INF;    ds[k][rt]=INF;    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);}node queryc(int k,int c1,int c2,int rt,int l,int r){    if (c1<=l && r<=c2){        node x;        x.maxn=db[k][rt];        x.mini=ds[k][rt];        return x;    }    int mid=(l+r)>>1;    if (mid<c1){        return queryc(k,c1,c2,rson);    }    else    if (mid>=c2){        return queryc(k,c1,c2,lson);    }    else{        node a=queryc(k,c1,c2,lson);        node b=queryc(k,c1,c2,rson);        node c;        c.mini=min(a.mini,b.mini);        c.maxn=max(a.maxn,b.maxn);        return c;    }}node queryr(int r1,int r2,int c1,int c2,int rt,int l,int r){    if (r1<=l && r<=r2)    {        return queryc(rt,c1,c2,1,1,n);    }    int mid=(l+r)>>1;    if (r2<=mid){        return queryr(r1,r2,c1,c2,lson);    }    else    if (r1>mid){        return queryr(r1,r2,c1,c2,rson);    }    else{        node a=queryr(r1,r2,c1,c2,lson);        node b=queryr(r1,r2,c1,c2,rson);        node c;        c.maxn=max(a.maxn,b.maxn);        c.mini=min(a.mini,b.mini);        return c;    }}void fixc(int val,int k,int C,int rt,int l,int r){    if (l>=r)    {        db[k][rt]=val;        ds[k][rt]=val;        for (int i=(k>>1);i;i>>=1){            db[i][rt]=max(db[i<<1][rt],db[i<<1|1][rt]);            ds[i][rt]=min(ds[i<<1][rt],ds[i<<1|1][rt]);        }        return;    }    int mid=(l+r)>>1;    if (C<=mid) fixc(val,k,C,lson);    else fixc(val,k,C,rson);    up(k,rt);}void fixr(int val,int R,int C,int rt,int l,int r){    if (l>=r)    {        fixc(val,rt,C,1,1,n);        return;    }    int mid=(l+r)>>1;    if (R<=mid) fixr(val,R,C,lson);    else fixr(val,R,C,rson);}int main(){    int t,kase=0;    scanf("%d",&t);    while (t--)    {        scanf("%d",&n);        buildr(1,1,n);        for (int i=1;i<=n;i++){            for (int j=1;j<=n;j++){                scanf("%d",&A[i][j]);                fixr(A[i][j],i,j,1,1,n);            }        }        int Q,L,R,S;        scanf("%d",&Q);        printf("Case #%d:\n",++kase);        int r1,r2,c1,c2;        while (Q--)        {            scanf("%d%d%d",&L,&R,&S);            r1=max(L-S/2,1);            r2=min(L+S/2,n);            c1=max(R-S/2,1);            c2=min(R+S/2,n);            node ans=queryr(r1,r2,c1,c2,1,1,n);            int ret=(ans.maxn+ans.mini)/2;            printf("%d\n",ret);            fixr(ret,L,R,1,1,n);        }    }    return 0;}

　　


联系
我们