首页 > 代码库 > 【BZOJ】1018: [SHOI2008]堵塞的交通traffic
【BZOJ】1018: [SHOI2008]堵塞的交通traffic
http://www.lydsy.com/JudgeOnline/problem.php?id=1018
题意：有2行，每行有c(c<=100000)个城市，则一共有c-1个格子，现在有q(q<=100000)个操作，操作Open和Close是将格子的四个角相邻的城市连边或删边，操作Ask是询问两个城市是否连通
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const int N=100005;struct T { bool d[2][2], f[2]; T() { CC(d, 0); CC(f, 0); } }t[N<<2];int n, a[N][4], tot;#define lc x<<1#define rc x<<1|1#define lson l, mid, lc#define rson mid+1, r, rcvoid upd1(T &x, int pos=-1) { static bool ok[4][4]; CC(ok, 0); if(pos==-1) { if(x.d[0][0]) ok[0][2]=ok[2][0]=1; if(x.d[0][1]) ok[0][3]=ok[3][0]=1; if(x.d[1][0]) ok[1][2]=ok[2][1]=1; if(x.d[1][1]) ok[1][3]=ok[3][1]=1; if(x.f[0]) ok[0][1]=ok[1][0]=1; if(x.f[1]) ok[2][3]=ok[3][2]=1; } else { CC(x.d, 0); CC(x.f, 0); if(a[pos][0]) ok[0][2]=ok[2][0]=1; if(a[pos][1]) ok[0][1]=ok[1][0]=1; if(a[pos][2]) ok[1][3]=ok[3][1]=1; if(a[pos][3]) ok[3][2]=ok[2][3]=1; } rep(i, 4) ok[i][i]=1; rep(k, 4) rep(i, 4) if(ok[i][k]) rep(j, 4) if(ok[k][j]) ok[i][j]=1; if(ok[0][1]) x.f[0]=1; if(ok[0][2]) x.d[0][0]=1; if(ok[0][3]) x.d[0][1]=1; if(ok[2][3]) x.f[1]=1; if(ok[1][2]) x.d[1][0]=1; if(ok[1][3]) x.d[1][1]=1;}void pushup(T &x, T &l, T &r) { x.d[0][0]=(l.d[0][0]&&r.d[0][0]) || (l.d[0][1]&&r.d[1][0]); x.d[0][1]=(l.d[0][0]&&r.d[0][1]) || (l.d[0][1]&&r.d[1][1]); x.d[1][0]=(l.d[1][0]&&r.d[0][0]) || (l.d[1][1]&&r.d[1][0]); x.d[1][1]=(l.d[1][0]&&r.d[0][1]) || (l.d[1][1]&&r.d[1][1]); x.f[0]=l.f[0] || (l.d[0][0]&&r.f[0]&&l.d[1][1]); x.f[1]=r.f[1] || (r.d[0][0]&&l.f[1]&&r.d[1][1]);}void update(int pos, int l=1, int r=tot, int x=1) { if(l==r) { upd1(t[x], pos); return; } int mid=(l+r)>>1; if(pos<=mid) update(pos, lson); else update(pos, rson); pushup(t[x], t[lc], t[rc]);}void ask(int L, int R, T &ret, int l=1, int r=tot, int x=1) { if(L<=l && r<=R) { memcpy(ret.d, t[x].d, sizeof(ret.d)); memcpy(ret.f, t[x].f, sizeof(ret.f)); return; } int mid=(l+r)>>1; if(R<=mid) { ask(L, R, ret, lson); return; } if(mid<L) { ask(L, R, ret, rson); return; } T t1, t2; ask(L, R, t1, lson); ask(L, R, t2, rson); pushup(ret, t1, t2);}void change(int x1, int y1, int x2, int y2, int f) { if(y1==y2) { if(y1==n) { a[y1-1][3]=f; update(y1-1); } else if(y1==1) { a[y1][1]=f; update(y1); } else { a[y1-1][3]=f; a[y1][1]=f; update(y1-1); update(y1); } } else { if(x1==0) a[y1][0]=f; if(x1==1) a[y1][2]=f; update(y1); } // T tt; // ask(1, 1, tt); dbg(tt.d[0][0]); dbg(tt.d[0][1]); dbg(tt.d[1][0]); dbg(tt.d[1][1]); dbg(tt.f[0]); dbg(tt.f[1]); // dbg(a[1][0]); dbg(a[1][3]);}void ask(int x1, int y1, int x2, int y2) { if(x1==x2 && y1==y2) { puts("Y"); return; } T l, r, mid; if(y1==y2) { if(y1==n) { ask(1, tot, mid); if(mid.f[1]) puts("Y"); else puts("N"); } else if(y1==1) { ask(1, tot, mid); if(mid.f[0]) puts("Y"); else puts("N"); } else { ask(1, y1-1, l); ask(y1, tot, r); if(l.f[1] || r.f[0]) puts("Y"); else puts("N"); } } else { if(y1-1>=1) ask(1, y1-1, l); if(y2<=tot) ask(y2, tot, r); ask(y1, y2-1, mid); if(mid.d[x1][x2]) { puts("Y"); return; } if(y1-1>=1 && l.f[1]) mid.f[0]=1; if(y2<=tot && r.f[0]) mid.f[1]=1; upd1(mid); if(mid.d[x1][x2]) puts("Y"); else puts("N"); }}char s[10];int main() { read(n); tot=n-1; while(scanf("%s", s), s[0]!=‘E‘) { int x1=getint(), y1=getint(), x2=getint(), y2=getint(); --x1; --x2; if(y1>y2) swap(x1, x2), swap(y1, y2); if(s[0]==‘O‘) change(x1, y1, x2, y2, 1); else if(s[0]==‘C‘) change(x1, y1, x2, y2, 0); else ask(x1, y1, x2, y2); } return 0;}
这题有很大可以吐槽的地方！！！！！！！！！！！！！！！！！！！！！！！！！！
首先这是一个坑，现在才来填平了....很早以前写的时候自己随便yy了一个类似lct一样的搞法（用并查集搞的lct...虽然没有路径压缩）交上去wa了...因为我是将整个图分层然后乱搞....
那时候看了一下题解发现是很神的线段树....然后敲了一下自己yy不过来了就放弃了....
然后之后某次我想填掉这个坑...可是按照自己yy的做发现不对于是又放弃...
然后是昨晚上我又来做QAQ发现其实挺好想的...就是维护一下连通嘛blabla的..于是愉快地1h吧不到敲好且过了样例且静态查错了下....竟然wa了QAQ于是造数据和暴力对拍....小数据全过.....于是找标程对拍....好不容易终于拍出了一组数据....可是.....这是n=2000的数据能调？于是返回到静态查错的状态来...可是似乎很累的原因？我就一直盯着屏幕和纸看呀看...输出调试拍呀拍...果然还是太弱了...拍到凌晨还没搞定....4h已废（这个伟大的故事告诉我们状态不好的时候不要想题QAQ更不要调试.............
果然是太弱了....于是今天中午来填坑（因为向root要到了数据...先评测了下...80分........于是再静态查了一下..立马发现了sb错......（果然还是要冷静+有精力才能肉眼拍完码农题啊QAQ）然后就a了》。。。
果然还是太弱....
题解：因为只有两行，因此状态可以设计为每个格子，所以只有c-1个格子（后边将c-1看做n），首先来分析只有一个格子的情况。显然要维护4个城市之间的连通性我直接floyd.....考虑多个格子连在一起的情况...如果我们要求[l, r]的城市的连通性（即[l, r-1]的格子，假设格子编号从1开始从左向右），那么可以用点什么东西维护一下整个区间的格子，则答案就是整个区间边界的4个点的连通性....发现了是不是都很相似，即求多个格子和一个格子都是取边界的4个点判断....而[l, r-1]是可以通过合并出来的...于是上线段树...orz（反正我是没yy出来线段树）即，对于[l, r]的格子（这个区间不是上边那个），我们假设有了中间一个点mid，则一定可以通过知道[l, mid], [mid+1, r]的连通性而推出[l, r]的连通性..（自己手推...）这样问题得到解决...
可是如果仅仅是向上边那样只找[l, r]的连通性来回答询问是不够的....因为可能[l, r]的左边界和右边界在[l, r]这个区间是没有边或是不连通的...但是可能在<=l的区间能找出一条路径使得l的左边界连通，所以我们再查询[1, l-1]，看看l-1这个格子的右边界是否连通就能知道l这个格子的左边界了...r同理.....
最后提示一点，也就是我的sb错，千万要注意序号....就是城市与格子序号之间的关系...即第x列格子对应的格子可能有x-1和x这个格子..
【BZOJ】1018: [SHOI2008]堵塞的交通traffic