题解 P4246 【[SHOI2008]堵塞的交通】

· · 题解

线段树神题……没想到线段树还有这种玩法……

打出这道题对线段树的理解和运用一定有巨大帮助。

这题一看像是LCT的样子，然而LCT还得支持各种奇怪的东西，还有巨大常数……一不小心就会挂。

考虑线段树。咋啥都能考虑

一个节点维护 [l,r] 区间的联通情况。（不考虑 [l,r] 外的道路，不然会写死人）

（u,d,l,r,p,q都是bool。下图中有个错别字，懒得改了）

对于叶子节点，很明显：

本题最恶心也是最厉害的地方来了：pushup。

先看看l。

r同理。这一部分这样写：

//conn[x][0]表示(1,x)和(1,x+1)是否联通
//conn[x][1]表示(2,x)和(2,x+1)是否联通
x.l=l.l|(l.u&conn[l.rig][0]&r.l&conn[l.rig][1]&l.d);
//左边能直接走下去
//左边能走上面，中上联通，再通过右边走到下面，中下联通，再通过左边走下面绕回来
x.r=r.r|(r.u&conn[l.rig][0]&l.r&conn[l.rig][1]&r.d);
//同理

再看看u。

d同理。这一部分这样写：

x.u=(l.u&conn[l.rig][0]&r.u)|(l.p&conn[l.rig][1]&r.q);
//左边能走上面，中上联通，右边能走上面
//左边能走主对角线，中下联通，右边能走副对角线
x.d=(l.d&conn[l.rig][1]&r.d)|(l.q&conn[l.rig][0]&r.p);
//同理

最后还有p：

q同理。最后放出整个pushup代码：

//pushup这样传参的原因待会会说
void pushup(node &x,node l,node r){
    x.lft=l.lft;    //x的左边界，因为conn要用到所以也要pushup
    x.rig=r.rig;    //x的右边界
    x.l=l.l|(l.u&conn[l.rig][0]&r.l&conn[l.rig][1]&l.d);
    x.r=r.r|(r.u&conn[l.rig][0]&l.r&conn[l.rig][1]&r.d);
    x.u=(l.u&conn[l.rig][0]&r.u)|(l.p&conn[l.rig][1]&r.q);
    x.d=(l.d&conn[l.rig][1]&r.d)|(l.q&conn[l.rig][0]&r.p);
    x.p=(l.u&conn[l.rig][0]&r.p)|(l.p&conn[l.rig][1]&r.d);
    x.q=(l.d&conn[l.rig][1]&r.q)|(l.q&conn[l.rig][0]&r.u);
}

现在来写修改操作。

我们发现在同一行和不在同一行有很多区别（要改的东西不一样），那就分开讨论。

先看不在同一行：（即同一列）

对于这一列代表的叶子节点，实际上就是上面和下面的连通性发生了变化。

然后沿途pushup就行了。

在同一行的会比较难懂。我也是看了别的题解才明白……

发现对于 [x,x+1] 这两个点所在的列，直接找到 x 对应的线段树叶子不太好修改。怎么弄呢？

我们发现，修改 [x,x+1] 这两列，会影响到的最小线段树节点是 [l,r]，其中 x=(l+r)/2=mid。即 x 作为线段树节点中点的节点。

会怎么影响呢？其实就是conn会变，然后就会影响整个节点的联通性。

那么修改完conn之后，对这个节点重新pushup一遍就好了。

这里贴个代码：

//o：节点编号，l：左端点，r：右端点
//p,row：表示修改(row+1,p)和(row+1,p+1)，因为第一行在conn是0，第二行是1
//val：开还是关
void modify1(int o,int l,int r,int p,int row,bool val){
    int mid=(l+r)>>1;
    if(mid==p){ //中点就是p
        conn[mid][row]=val; //修改conn
        pushup(seg[o],seg[o<<1],seg[o<<1|1]);   //重新pushup
        return;
    }
    if(mid>=p) modify1(lson,p,row,val); //递归修改
    else modify1(rson,p,row,val);
    pushup(seg[o],seg[o<<1],seg[o<<1|1]);   //更新
}

最后还有询问。询问相信大家都会写。

//返回node方便在递归路上合并各个节点的信息
node query(int o,int l,int r,int ql,int qr){
    if(l>=ql && r<=qr) return seg[o];   //直接返回
    int mid=(l+r)>>1;
    if(mid<ql) return query(rson,ql,qr);    //不需要左儿子
    if(mid>=qr) return query(lson,ql,qr);   //不需要有儿子
    node ans;
    pushup(ans,query(lson,ql,qr),query(rson,ql,qr));    //左右儿子合起来
    return ans;
}

然后main里面大力讨论一下是考虑答案u,d,l,r,p还是q。交上去……

WA？？？？？？！！！！！！

哦对了，我们来测组数据吧：

4
OPEN 1 1 1 2
OPEN 1 3 1 4
OPEN 1 1 2 1
OPEN 2 1 2 2
OPEN 2 2 2 3
OPEN 2 3 2 4
OPEN 1 4 2 4
ASK 1 2 1 3 
EXIT

答案明显是Y。但是我们输出了N？为什么？

我们把这个图画出来：

原来如此。那么求出三个区间大力讨论一下。写法跟pushup差不多，如果理解了pushup那么这一块也应该不难理解。

直接放代码吧：

#include<bits/stdc++.h>
using namespace std;
const int maxn=444444;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    char ch=getchar();int x=0,f=0;
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
struct node{
    int lft,rig;
    bool l,r,u,d,p,q;
}seg[maxn]; //节点
int n;
bool conn[maxn][2];
void pushup(node &x,node l,node r){
    x.lft=l.lft;
    x.rig=r.rig;
    x.l=l.l|(l.u&conn[l.rig][0]&r.l&conn[l.rig][1]&l.d);
    x.r=r.r|(r.u&conn[l.rig][0]&l.r&conn[l.rig][1]&r.d);
    x.u=(l.u&conn[l.rig][0]&r.u)|(l.p&conn[l.rig][1]&r.q);
    x.d=(l.d&conn[l.rig][1]&r.d)|(l.q&conn[l.rig][0]&r.p);
    x.p=(l.u&conn[l.rig][0]&r.p)|(l.p&conn[l.rig][1]&r.d);
    x.q=(l.d&conn[l.rig][1]&r.q)|(l.q&conn[l.rig][0]&r.u);
}
void build(int o,int l,int r){  //建树
    if(l==r){
        seg[o].lft=seg[o].rig=l;    //叶子节点左右边界
        seg[o].u=seg[o].d=1;    //左右联通
        return;
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    pushup(seg[o],seg[o<<1],seg[o<<1|1]);
}
void modify1(int o,int l,int r,int p,int row,bool val){ //同行修改
    int mid=(l+r)>>1;
    if(mid==p){
        conn[mid][row]=val;
        pushup(seg[o],seg[o<<1],seg[o<<1|1]);
        return;
    }
    if(mid>=p) modify1(lson,p,row,val);
    else modify1(rson,p,row,val);
    pushup(seg[o],seg[o<<1],seg[o<<1|1]);
}
void modify2(int o,int l,int r,int p,bool val){ //不同行修改，第p列
    if(l==r){
        seg[o].l=seg[o].r=seg[o].p=seg[o].q=val;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=p) modify2(lson,p,val);
    else modify2(rson,p,val);
    pushup(seg[o],seg[o<<1],seg[o<<1|1]);
}
node query(int o,int l,int r,int ql,int qr){    //查询区间[ql,qr]的节点
    if(l>=ql && r<=qr) return seg[o];
    int mid=(l+r)>>1;
    if(mid<ql) return query(rson,ql,qr);
    if(mid>=qr) return query(lson,ql,qr);
    node ans;
    pushup(ans,query(lson,ql,qr),query(rson,ql,qr));
    return ans;
} 
int main(){
    n=read();char op[10];
    build(1,1,n);
    while(~scanf("%s",op) && op[0]!='E'){
        int a=read(),b=read(),c=read(),d=read();
        switch(op[0]){
            case 'C':   //关路
                if(a==c) modify1(1,1,n,min(b,d),a-1,0); //同一行
                else modify2(1,1,n,b,0);    //不同行
                break;
            case 'O':   //开路
                if(a==c) modify1(1,1,n,min(b,d),a-1,1);
                else modify2(1,1,n,b,1);
                break;
            case 'A':   //询问
                if(b>d) swap(a,c),swap(b,d);    //列编号小的放前面
                node ans1=query(1,1,n,b,d),ans2=query(1,1,n,1,b),ans3=query(1,1,n,d,n); //三段
                bool flag=false;
                if(a==1){
                    if(c==1){   //左上，右上
                        if(ans1.u) flag=true;   //直接走上面
                        if(ans2.r&ans1.d&ans3.l) flag=true; //绕路走
                    }
                    else{   //左上，右下
                        if(ans1.p) flag=true;   //直接走
                        if(ans2.r&ans1.d) flag=true;    //从左边绕
                        if(ans3.l&ans1.u) flag=true;    //从右边绕
                    }
                }
                else{
                    if(c==1){   //左下，右上
                        if(ans1.q) flag=true;   //直接走
                        if(ans2.r&ans1.u) flag=true;    //从左边绕
                        if(ans3.l&ans1.d) flag=true;    //从右边绕
                    }
                    else{   //左下，右下
                        if(ans1.d) flag=true;   //直接走
                        if(ans2.r&ans1.u&ans3.l) flag=true; //绕路走
                    }
                }
                puts(flag?"Y":"N");
        }
    }
}

这可能是我写过最认真的一篇题解了。

主要还是因为这题太有意义了，而且洛谷上题解没几个图，有点难懂……

希望能帮到大家。两开花，谢谢支持。