首页 > 代码库 > BZOJ 1018: [SHOI2008]堵塞的交通traffic [线段树 区间信息]
BZOJ 1018: [SHOI2008]堵塞的交通traffic [线段树 区间信息]
1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 3064 Solved: 1027
[Submit][Status][Discuss]
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”作为
结束。我们假设在一开始所有的道路都是堵塞的。我们保证 C小于等于100000,信息条数小于等于100000。
Output
对于每个查询,输出一个“Y”或“N”。
Sample Input
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
Sample Output
N
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define pa t[x].fa#define lc t[x].ch[0]#define rc t[x].ch[1]const int N=2e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int c;struct LCTnode{ int ch[2],fa,rev;}t[N];inline int wh(int x){return t[pa].ch[1]==x;}inline int isRoot(int x){return t[pa].ch[0]!=x&&t[pa].ch[1]!=x;}inline void update(int x){}inline void rever(int x){ t[x].rev^=1; swap(lc,rc);}inline void pushDown(int x){ if(t[x].rev){ rever(lc); rever(rc); t[x].rev=0; }}inline void rotate(int x){ int f=t[x].fa,g=t[f].fa,c=wh(x); if(!isRoot(f)) t[g].ch[wh(f)]=x;t[x].fa=g; t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f; t[x].ch[c^1]=f;t[f].fa=x; update(f);update(x);}int st[N],top;inline void splay(int x){ top=0;st[++top]=x; for(int i=x;!isRoot(i);i=t[i].fa) st[++top]=t[i].fa; for(int i=top;i>=1;i--) pushDown(st[i]); for(;!isRoot(x);rotate(x)) if(!isRoot(pa)) rotate(wh(x)==wh(pa)?pa:x);}inline void Access(int x){ for(int y=0;x;y=x,x=pa){ splay(x); rc=y; update(x); }}inline void MakeR(int x){ Access(x);splay(x); rever(x);}inline int FindR(int x){ Access(x);splay(x); while(lc) x=lc; return x;}inline void Link(int x,int y){ MakeR(x); t[x].fa=y;}inline void Cut(int x,int y){ MakeR(x);Access(y);splay(y); t[y].ch[0]=t[x].fa=0; update(y);}int n;inline int id(int x,int y){ if(x==1) return y; else return n+y;}char s[10];int x1,y1,x2,y2,x,y;int main(){ freopen("bzoj_1018.in","r",stdin); //freopen("bzoj_1018.out","w",stdout); n=read(); while(true){ scanf("%s",s); if(s[0]==‘E‘) break; x1=read();y1=read();x2=read();y2=read(); x=id(x1,y1);y=id(x2,y2); printf("begin %d %d %d %d %d\n",++c,x1,y1,x,y); if(s[0]==‘O‘) Link(x,y); if(s[0]==‘C‘) if(FindR(x)==FindR(y)) Cut(x,y); if(s[0]==‘A‘){ if(FindR(x)==FindR(y)) puts("Y"); else puts("N"); } }}
正解是线段树,只有两行所以上下一行信息一起维护啊
保存luld,rurd,luru,ldrd,lurd,ldru,up,down up和down是说这段区间和左面的区间上或下是不是连着的
合并和查询参考了Vampire的代码
核心思想是:每个区间最后的信息都是通过这个区间连通之后的
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define mid ((l+r)>>1)#define lc x<<1#define rc x<<1|1#define lson x<<1,l,mid#define rson x<<1|1,mid+1,rconst int N=2e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,r1,c1,r2,c2;char op[N];struct Node{ int luld,rurd,luru,ldrd,lurd,ldru,up,down; Node():luld(0),rurd(0),luru(0),ldrd(0),lurd(0),ldru(0),up(0),down(0){}}t[N<<2];inline Node merge(Node x,Node y){ Node ret; ret.up=y.up;ret.down=y.down; ret.luld=x.luld|(x.luru&x.up&y.luld&x.down&x.ldrd); ret.rurd=y.rurd|(y.luru&x.up&x.rurd&x.down&y.ldrd); ret.luru=(x.luru&x.up&y.luru) |(x.lurd&x.down&y.ldru); ret.ldrd=(x.ldrd&x.down&y.ldrd)|(x.ldru&x.up&y.lurd); ret.lurd=(x.luru&x.up&y.lurd) |(x.lurd&x.down&y.ldrd); ret.ldru=(x.ldrd&x.down&y.ldru)|(x.ldru&x.up&y.luru); return ret;}void build(int x,int l,int r){ if(l==r) t[x].luru=t[x].ldrd=true; else{ build(lson); build(rson); t[x]=merge(t[lc],t[rc]);//not need }}void segIns1(int x,int l,int r,int c,bool d){ if(l==r) t[x].luld=t[x].rurd=t[x].lurd=t[x].ldru=d; else{ if(c<=mid) segIns1(lson,c,d); else segIns1(rson,c,d); t[x]=merge(t[lc],t[rc]); }}void segIns2(int x,int l,int r,int col,int row,bool d){ if(l==r){ if(row==1) t[x].up=d;else t[x].down=d; }else{ if(col<=mid) segIns2(lson,col,row,d); else segIns2(rson,col,row,d); t[x]=merge(t[lc],t[rc]); }}Node segQue(int x,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return t[x]; else{ Node a,b;int f1=0,f2=0; if(ql<=mid) a=segQue(lson,ql,qr),f1=1; if(mid<qr) b=segQue(rson,ql,qr),f2=1; if(f1&&f2) return merge(a,b); else return f1?a:b; }}bool query(){ if(c1>c2) swap(c1,c2),swap(r1,r2); Node a=segQue(1,1,n,1,c1),b=segQue(1,1,n,c1,c2),c=segQue(1,1,n,c2,n); if(r1==r2){ if(r1==1&&( (b.luru)|(c.luld&b.lurd)|(a.rurd&b.ldru)|(a.rurd&b.ldrd&c.luld) )) return true; if(r1==2&&( (b.ldrd)|(c.luld&b.ldru)|(a.rurd&b.lurd)|(a.rurd&b.luru&c.luld) )) return true; }else{ if(r1==1&&( (b.lurd)|(c.luld&b.luru)|(a.rurd&b.ldrd)|(a.rurd&b.ldru&c.luld) )) return true; if(r2==1&&( (b.ldru)|(c.luld&b.ldrd)|(a.rurd&b.luru)|(a.rurd&b.lurd&c.luld) )) return true; } return false;}int main(){ //freopen("in.txt","r",stdin); n=read(); build(1,1,n); while(true){ scanf("%s",op); if(op[0]==‘E‘) break; r1=read();c1=read();r2=read();c2=read(); if(op[0]==‘O‘){ if(c1==c2) segIns1(1,1,n,c1,1); else segIns2(1,1,n,min(c1,c2),r1,1); } if(op[0]==‘C‘){ if(c1==c2) segIns1(1,1,n,c1,0); else segIns2(1,1,n,min(c1,c2),r1,0); } if(op[0]==‘A‘) printf("%s\n",query()?"Y":"N"); }}
BZOJ 1018: [SHOI2008]堵塞的交通traffic [线段树 区间信息]