【bzoj1018】[SHOI2008]堵塞的交通traffic

2015.04.24 11:35 Fri | 2次阅读 | 旧日oi | 固定链接 | 源码

Description

有一天,由于某种穿越现象作用,你来到了传说中的小人国。小人国的布局非常奇特,整个国家的交通系统可以被看成是一个2行C列的矩形网格,网格上的每个点代表一个城市,相邻的城市之间有一条道路,所以总共有2C个城市和3C-2条道路。 小人国的交通状况非常槽糕。有的时候由于交通堵塞,两座城市之间的道路会变得不连通,直到拥堵解决,道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事,部长听说你来自一个科技高度发达的世界,喜出望外地要求你编写一个查询应答系统,以挽救已经病入膏肓的小人国交通系统。 小人国的交通部将提供一些交通信息给你,你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式: Close r1 c1 r2 c2:相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了; Open r1 c1 r2 c2:相邻的两座城市(r1,c1)和(r2,c2)之间的道路被疏通了; Ask r1 c1 r2 c2:询问城市(r1,c1)和(r2,c2)是否连通。如果存在一条路径使得这两条城市连通,则返回Y,否则返回N;

Input

第一行只有一个整数C,表示网格的列数。接下来若干行,每行为一条交通信息,以单独的一行“Exit”作为结束。我们假设在一开始所有的道路都是堵塞的。 对30%测试数据,我们保证C小于等于1000,信息条数小于等于1000; 对100%测试数据,我们保证 C小于等于100000,信息条数小于等于100000。

Output

对于每个查询,输出一个“Y”或“N”。

Sample Input

2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit

Sample Output

Y
N

题解

线段树维护区间连通性,没什么好说的,看代码注释吧,一定要注意细节!!

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
int n,r1,r2,c1,c2;
char str[10];
struct node{
    bool h[2],s[2],x[2];
}a[maxn<<2];
bool down[maxn],ri[maxn][2];
void pushup(node &a,node &l,node &r,int mid)
{
    a.h[0]=(l.h[0]&&ri[mid][0]&&r.h[0])||(l.x[0]&&ri[mid][1]&&r.x[1]);//左上到右上
    a.h[1]=(l.h[1]&&ri[mid][1]&&r.h[1])||(l.x[1]&&ri[mid][0]&&r.x[0]);//左下到右下
    a.s[0]=l.s[0]||(l.h[0]&&ri[mid][0]&&r.s[0]&&ri[mid][1]&&l.h[1]);//左上到左下
    a.s[1]=r.s[1]||(r.h[0]&&ri[mid][0]&&l.s[1]&&ri[mid][1]&&r.h[1]);//右上到右下
    a.x[0]=(l.h[0]&&ri[mid][0]&&r.x[0])||(l.x[0]&&ri[mid][1]&&r.h[1]);//左上到右下
    a.x[1]=(l.h[1]&&ri[mid][1]&&r.x[1])||(l.x[1]&&ri[mid][0]&&r.h[0]);//左下到右上
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        a[rt].h[0]=a[rt].h[1]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int l,int r,int rt,int x)
{
    if(l==r)
    {
        a[rt].s[0]=a[rt].s[1]=a[rt].x[0]=a[rt].x[1]=down[x];
        a[rt].h[0]=a[rt].h[1]=1;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(lson,x);
    else update(rson,x);
    pushup(a[rt],a[rt<<1],a[rt<<1|1],mid);
}
void change(bool k)
{
    if(c1==c2) down[c1]=k;
    if(c1>c2) swap(c1,c2);
    if(r1==0&&r2==0) ri[c1][0]=k;
    else if(r1==1&&r2==1) ri[c1][1]=k;
    update(1,n,1,c1);
}
void get_st(node &p,int l,int r,int rt,int L,int R)
{
    if(L==l&&R==r)
    {
        p=a[rt];
        return;
    }
    int mid=(l+r)>>1;
    if(R<=mid) get_st(p,lson,L,R);
    else if(L>mid) get_st(p,rson,L,R);
    else
    {
        node tmp1,tmp2;
        get_st(tmp1,lson,L,mid);
        get_st(tmp2,rson,mid+1,R);
        pushup(p,tmp1,tmp2,mid);
    }
}
void get_ans()
{
    node p1,p2,p3;
    if(c1>c2) swap(r1,r2),swap(c1,c2);
    get_st(p1,1,n,1,1,c1);
    get_st(p2,1,n,1,c1,c2);
    get_st(p3,1,n,1,c2,n);
    if(r1==r2)
    {
        if(r1==0)
        {
            if(p2.h[0]||(p1.s[1]&&p2.x[1])||(p3.s[0]&&p2.x[0])||(p1.s[1]&&p2.h[1]&&p3.s[0])) puts("Y");//一定别忘了最后那段
            else puts("N");
        }
        else
        {
            if(p2.h[1]||(p1.s[1]&&p2.x[0])||(p3.s[0]&&p2.x[1])||(p1.s[1]&&p2.h[0]&&p3.s[0])) puts("Y");
            else puts("N");
        }
    }
    else
    {
        if(r1==0)
        {
            if(p2.x[0]||(p1.s[1]&&p2.h[1])||(p3.s[0]&&p2.h[0])||(p1.s[1]&&p2.x[1]&&p3.s[0])) puts("Y");
            else puts("N");
        }
        else
        {
            if(p2.x[1]||(p1.s[1]&&p2.h[0])||(p3.s[0]&&p2.h[1])||(p1.s[1]&&p2.x[0]&&p3.s[0])) puts("Y");
            else puts("N");
        }
    }
}
int main()
{
    cin>>n;
    build(1,n,1);
    while(scanf("%s",str)&&str[0]!='E')
    {
        scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
        r1--;r2--;
        if(str[0]=='O') change(1);
        else if(str[0]=='C') change(0);
        else get_ans();
    }
}```