勤快学

bzoj1018:[SHOI2008]堵塞的交通traffic

  标签:bzoj  SHOI  traffic  1018  2008    发布于:2016年11月04日

                           

思路:线段树好题,用线段树维护连通性。

区间[l,r]表示左端点为l,右端点为r,宽度为2的矩形,那么线段树区间维护的就是该区间内的四个角的连通情况,注意是该区间内的连通情况,也就是说只能通过该区间内部进行连通而不能越出区间而进行连通。

一共六种连通情况:左上对右上,左上对左下,左上对右下,右上对左下,右上对右下,左下对右下。

线段树的每一个节点均维护一个域a[]用来维护该区间内的连通情况,对应下图所示

技术分享

然后维护的话要注意的就是因为左儿子是[l,mid],右儿子是[mid+1,r],因为线段树叶子节点表示的是对应位置的格子,所以左儿子和右儿子之间是存在边的,那么就要考虑这条边是否连通,这会对连通性造成影响。

对于a1(a3类似)的维护:可以直接用左儿子的a1直接更新答案,也可以用左儿子的a2,a4,右儿子的a1,再加上中间跨过的两条边来更新答案(相当于从左边绕到右边再绕回到左边)。

对于a2(a4类似)的维护:可以用左儿子的a5,右儿子的a6,和下面那条边更新,也可以用左儿子的a2,右儿子的a2,和上面那条边更新。

对于a5(a6类似)的维护:可以用左儿子的a5,右儿子的a4,和下面那条边更新,也可以用左儿子的a2,右儿子的a5,和上面那条边更新。

最后就是query,因为线段树维护的是区间内的连通情况,所以就不能直接query输入的,因为可能会绕出区间再绕回来最终连通,这样就可能有四种情况,例子如下图所示:

技术分享

然后分四种情况讨论即可。(细节的确有点小多,具体看代码)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 100005
 
int n,pre;
char s[10];
bool a[maxn*2],first;
 
inline int read(){
    int x=0;char ch=getchar();
    for (;ch<‘0‘||ch>‘9‘;ch=getchar());
    for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
    return x;
}
 
int calc(int x,int y){return (x-1)*n+y;}
 
struct segment_tree{
    struct treenode{
        bool a[7];
        treenode(){}
        treenode(int x){for (int i=1;i<=6;i++) a[i]=x;}
    }tree[4*maxn];
    void build(int p,int l,int r){
        if (l==r){tree[p].a[2]=tree[p].a[4]=1;return;}
        int mid=(l+r)>>1; build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    }
    treenode merge(treenode ls,treenode rs,int mid){
        treenode ans(0);
        ans.a[1]=ls.a[1]|(ls.a[2]&a[calc(1,mid)]&rs.a[1]&a[calc(2,mid)]&ls.a[4]);
        ans.a[2]=(ls.a[2]&a[calc(1,mid)]&rs.a[2])|(ls.a[5]&a[calc(2,mid)]&rs.a[6]);
        ans.a[3]=rs.a[3]|(rs.a[2]&a[calc(1,mid)]&ls.a[3]&a[calc(2,mid)]&rs.a[4]);
        ans.a[4]=(ls.a[6]&a[calc(1,mid)]&rs.a[5])|(ls.a[4]&a[calc(2,mid)]&rs.a[4]);
        ans.a[5]=(ls.a[5]&a[calc(2,mid)]&rs.a[4])|(ls.a[2]&a[calc(1,mid)]&rs.a[5]);
        ans.a[6]=(ls.a[6]&a[calc(1,mid)]&rs.a[2])|(ls.a[4]&a[calc(2,mid)]&rs.a[6]);
        return ans;
    }
    void change1(int p,int l,int r,int x,int y){
        if (x<=l&&r<=y){if (l!=r) tree[p]=merge(tree[p<<1],tree[p<<1|1],(l+r)>>1); return;}
        int mid=(l+r)>>1;
        if (x<=mid) change1(p<<1,l,mid,x,y);
        if (y>mid) change1(p<<1|1,mid+1,r,x,y);
        tree[p]=merge(tree[p<<1],tree[p<<1|1],mid);
    }
    void change2(int p,int l,int r,int pos){
        if (l==r){tree[p].a[1]^=1,tree[p].a[3]^=1,tree[p].a[5]^=1,tree[p].a[6]^=1;return;}
        int mid=(l+r)>>1;
        if (pos<=mid) change2(p<<1,l,mid,pos);else change2(p<<1|1,mid+1,r,pos);
        tree[p]=merge(tree[p<<1],tree[p<<1|1],mid);
    }
    void query(int p,int l,int r,int x,int y,treenode &ans){
        if (x<=l&&r<=y){
            if (first) ans=tree[p],first=0;
            else ans=merge(ans,tree[p],pre);
            pre=r;
            return;
        }
        int mid=(l+r)>>1;
        if (x<=mid) query(p<<1,l,mid,x,y,ans);
        if (y>mid) query(p<<1|1,mid+1,r,x,y,ans);
    }
    treenode query(int l,int r){
        treenode ans(0);first=1,pre=0;
        query(1,1,n,l,r,ans);
        return ans;
    }
}T;
 
int main(){
    n=read(),T.build(1,1,n);
    while (scanf("%s",s+1)!=EOF){
        if (s[1]==‘E‘) break;
        if (s[1]==‘O‘||s[1]==‘C‘){
            int x1=read(),y1=read(),x2=read(),y2=read();
            if (y1>y2) swap(y1,y2);
            if (x1==x2) a[calc(x1,y1)]^=1,T.change1(1,1,n,y1,y2);
            else T.change2(1,1,n,y1);
        }
        else{
            int x1=read(),y1=read(),x2=read(),y2=read();bool flag=0;
            int mn=min(y1,y2),mx=max(y1,y2);
            segment_tree::treenode t1=T.query(1,mn),t2=T.query(mn,mx),t3=T.query(mx,n);
            if (x1==x2){
                if (x1==1){
                    flag|=t2.a[2];
                    flag|=t1.a[3]&t2.a[6];
                    flag|=t2.a[5]&t3.a[1];
                    flag|=t1.a[1]&t2.a[4]&t3.a[1];
                }
                else{
                    flag|=t2.a[4];
                    flag|=t1.a[3]&t2.a[5];
                    flag|=t2.a[6]&t3.a[1];
                    flag|=t1.a[3]&t2.a[2]&t3.a[1];
                }
            }
            else{
                if ((x1==1&&y1<y2)||(x1==2&&y1>y2)){
                    flag|=t2.a[5];
                    flag|=t1.a[3]&t2.a[4];
                    flag|=t2.a[2]&t3.a[1];
                    flag|=t1.a[3]&t2.a[6]&t3.a[1];
                }
                else{
                    flag|=t2.a[6];
                    flag|=t1.a[3]&t2.a[2];
                    flag|=t2.a[4]&t3.a[1];
                    flag|=t1.a[3]&t2.a[5]&t3.a[1];
                }
            }
            puts(flag?"Y":"N");
        }
    }
    return 0;
}

  

                           

上一篇:[Jmeter]jmeter之参数化

下一篇:php+jquery+ajax+json的一个最简单实例