题意

题目描述

有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个\(2\)行\(C\)列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有\(2C\)个城市和\(3C-2\)条道路。

小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：

Close r1 c1 r2 c2：相邻的两座城市\((r_1, c_1)\)和\((r_2, c_2)\)之间的道路被堵塞了；
Open r1 c1 r2 c2：相邻的两座城市\((r_1, c_1)\)和\((r_2, c_2)\)之间的道路被疏通了；
Ask r1 c1 r2 c2：询问城市\((r_1, c_1)\)和\((r_2, c_2)\)是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N。

注：\(r_i\)表示行数，\(c_i\)表示列数， \(1\leq r_i\leq 2,1\leq c_i\leq C\)。

输入输出格式

输入格式：

第一行只有一个整数\(C\)，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行Exit作为结束。我们假设在一开始所有的道路都是堵塞的。我们保证\(C\)小于等于\(100000\)，信息条数小于等于\(100000\)。

输出格式：

对于每个查询，输出一个Y或N。

输入输出样例

输入样例#1：

2

Open 1 1 1 2

Open 1 2 2 2

Ask 1 1 2 2

Ask 2 1 2 2

Exit

输出样例#1：

Y

N

说明

数据范围：

对于\(100\%\)的数据，\(1\leq C\leq 100000,1\leq \text{信息条数}\leq 100000\)。

思路

什么**线段树。 --Mercury

用线段树来写，每个结点维护区间\([l,r]\)的连通性。维护时记录六个值：

\(ldrd(left-down\ to\ right-down)\)
\(luru(left-up\ to\ right-up)\)
\(luld(left-up\ to\ left-down)\)
\(rurd(right-up\ to\ right-down)\)
\(lurd(left-up\ to\ right-down)\)
\(ldru(left-down\ to\ right-up)\)

合并过程其实就是大力模拟的过程，考虑所有的路的经过情况。详见代码的两个update函数。

修改的时候要分类讨论，横线的变化与竖线的变化是不同的情况。

查询的时候要注意，两点可能绕外面的路互相到达，所以还是要大力模拟，考虑绕路和不绕路的情况。

代码的变量名还是比较清楚的，所以就详见代码吧（才不是我懒得写）。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1e5+5;

int n;

int ru[MAXN],rd[MAXN];

struct SegmentTree

{

    int l,r;

    bool ldrd,luru,luld,rurd,lurd,ldru;

    #define l(x) tree[x].l

    #define r(x) tree[x].r

    #define ldrd(x) tree[x].ldrd

    #define luru(x) tree[x].luru

    #define luld(x) tree[x].luld

    #define rurd(x) tree[x].rurd

    #define lurd(x) tree[x].lurd

    #define ldru(x) tree[x].ldru

}tree[MAXN<<2];

int read()

{

    int re=0;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

char readc()

{

    char ch=getchar();

    while(!isalpha(ch)) ch=getchar();

    return ch;

}

void update(int p)

{

    l(p)=l(p<<1),r(p)=r(p<<1|1);

    ldrd(p)=(ldrd(p<<1)&&rd[r(p<<1)]&&ldrd(p<<1|1))||(ldru(p<<1)&&ru[r(p<<1)]&&lurd(p<<1|1));

    luru(p)=(luru(p<<1)&&ru[r(p<<1)]&&luru(p<<1|1))||(lurd(p<<1)&&rd[r(p<<1)]&&ldru(p<<1|1));

    luld(p)=luld(p<<1)||(luru(p<<1)&&ru[r(p<<1)]&&luld(p<<1|1)&&rd[r(p<<1)]&&ldrd(p<<1));

    rurd(p)=rurd(p<<1|1)||(luru(p<<1|1)&&ru[r(p<<1)]&&rurd(p<<1)&&rd[r(p<<1)]&&ldrd(p<<1|1));

    lurd(p)=(luru(p<<1)&&ru[r(p<<1)]&&lurd(p<<1|1))||(lurd(p<<1)&&rd[r(p<<1)]&&ldrd(p<<1|1));

    ldru(p)=(ldrd(p<<1)&&rd[r(p<<1)]&&ldru(p<<1|1))||(ldru(p<<1)&&ru[r(p<<1)]&&luru(p<<1|1));

}

void update(SegmentTree &re,SegmentTree x,SegmentTree y)

{

    re.l=x.l,re.r=y.r;

    re.ldrd=(x.ldrd&&rd[x.r]&&y.ldrd)||(x.ldru&&ru[x.r]&&y.lurd);

    re.luru=(x.luru&&ru[x.r]&&y.luru)||(x.lurd&&rd[x.r]&&y.ldru);

    re.luld=x.luld||(x.luru&&ru[x.r]&&y.luld&&rd[x.r]&&x.ldrd);

    re.rurd=y.rurd||(y.luru&&ru[x.r]&&x.rurd&&rd[x.r]&&y.ldrd);

    re.lurd=(x.luru&&ru[x.r]&&y.lurd)||(x.lurd&&rd[x.r]&&y.ldrd);

    re.ldru=(x.ldrd&&rd[x.r]&&y.ldru)||(x.ldru&&ru[x.r]&&y.luru);

}

void build(int p,int ll,int rr)

{

    if(ll==rr)

    {

        l(p)=ll,r(p)=rr;

        luru(p)=ldrd(p)=true;

        return ;

    }

    int mid=(ll+rr)>>1;

    build(p<<1,ll,mid);

    build(p<<1|1,mid+1,rr);

    update(p);

}

void change1(int p,int des,bool up,bool val)

{

    int mid=(l(p)+r(p))>>1;

    if(mid==des)

    {

        if(up) ru[des]=val;

        else rd[des]=val;

        update(p);

        return ;

    }

    if(des<=mid) change1(p<<1,des,up,val);

    else change1(p<<1|1,des,up,val);

    update(p);

}

void change2(int p,int des,bool val)

{

    if(l(p)==r(p))

    {

        luld(p)=rurd(p)=lurd(p)=ldru(p)=val;

        return ;

    }

    int mid=(l(p)+r(p))>>1;

    if(des<=mid) change2(p<<1,des,val);

    else change2(p<<1|1,des,val);

    update(p);

}

SegmentTree ask(int p,int ll,int rr)

{

    if(ll<=l(p)&&r(p)<=rr) return tree[p];

    int mid=(l(p)+r(p))>>1;

    if(rr<=mid) return ask(p<<1,ll,rr);

    else if(ll>mid) return ask(p<<1|1,ll,rr);

    else

    {

        SegmentTree re;

        update(re,ask(p<<1,ll,rr),ask(p<<1|1,ll,rr));

        return re;

    }

}

int main()

{

    n=read();

    build(1,1,n);

    while(true)

    {

        char opt=readc();

        if(opt=='E') break;

        int x=read(),y=read(),xx=read(),yy=read();

        if(y>yy) swap(x,xx),swap(y,yy);

        if(opt=='C')

        {

            if(y==yy) change2(1,y,false);

            else change1(1,y,x==1,false);

        }

        else if(opt=='O')

        {

            if(y==yy) change2(1,y,true);

            else change1(1,y,x==1,true);

        }

        else if(opt=='A')

        {

            SegmentTree ll=ask(1,1,y),mid=ask(1,y,yy),rr=ask(1,yy,n);

            if(x==1&&xx==1)

            {

                if(mid.luru||(ll.rurd&&mid.ldru)||(mid.lurd&&rr.luld)||(ll.rurd&&mid.ldrd&&rr.luld)) puts("Y");

                else puts("N");

            }

            else if(x==2&&xx==2)

            {

                if(mid.ldrd||(ll.rurd&&mid.lurd)||(mid.ldru&&rr.luld)||(ll.rurd&&mid.luru&&rr.luld)) puts("Y");

                else puts("N");

            }

            else if(x==1&&xx==2)

            {

                if(mid.lurd||(ll.rurd&&mid.ldrd)||(mid.luru&&rr.luld)||(ll.rurd&&mid.ldru&&rr.luld)) puts("Y");

                else puts("N");

            }

            else if(x==2&&xx==1)

            {

                if(mid.ldru||(ll.rurd&&mid.luru)||(mid.ldrd&&rr.luld)||(ll.rurd&&mid.lurd&&rr.luld)) puts("Y");

                else puts("N");

            }

        }

    }

    return 0;

}

巴特西

Luogu P4246 [SHOI2008]堵塞的交通(线段树+模拟)

题意