題目鏈接：

[BJOI2019]送別

?

我們將每段墻的每一面看成一個(gè)點(diǎn)，將每個(gè)點(diǎn)與相鄰的點(diǎn)(即按題中規(guī)則前進(jìn)或后退一步能走到的點(diǎn))連接。那么圖中所有點(diǎn)就形成了若干個(gè)環(huán)，而添加一段墻或刪除一段墻就是把兩個(gè)環(huán)合并或者將一個(gè)環(huán)拆成兩個(gè)環(huán)(當(dāng)然可能只是在環(huán)上插入或刪除兩個(gè)點(diǎn))。將每個(gè)環(huán)從任意位置拆成序列，用平衡樹(shù)(平衡樹(shù)需要能合并、分裂)維護(hù)即可。我們記錄每個(gè)坐標(biāo)點(diǎn)的上下左右是否有墻，如果一個(gè)坐標(biāo)點(diǎn)的四個(gè)方向都沒(méi)有墻則視為這個(gè)點(diǎn)是空的。

對(duì)于插入，有四種情況：

1、插入墻的兩端都是空的，直接將插入墻的兩個(gè)點(diǎn)合并為一個(gè)環(huán)即可。

2、插入墻的一端是空的，在另一端順時(shí)針或逆時(shí)針找到遇到的第一面墻，從那里將序列分成兩段，將插入墻的兩個(gè)點(diǎn)依次插入。

3、插入墻的兩端都不是空的，但兩端屬于不同環(huán)，兩端分別順時(shí)針找到遇到的第一面墻從那里將序列分裂然后將兩個(gè)環(huán)拆成的四個(gè)序列以及插入墻的兩個(gè)點(diǎn)按順序合并即可。

4、插入墻的兩端都不是空的，但兩端屬于同一個(gè)環(huán)，兩端分別順時(shí)針找到遇到的第一面墻從那里拆開(kāi)然后將兩個(gè)環(huán)拆成的四個(gè)序列與插入墻的兩個(gè)點(diǎn)分別合并成兩個(gè)序列。

對(duì)于刪除，同樣有上述四種情況，像上面說(shuō)的一樣討論一下即可。

注意當(dāng)將一個(gè)序列連續(xù)兩次分裂時(shí)，要判斷一下第二次的分裂點(diǎn)屬于第一次分裂出來(lái)的哪個(gè)序列。

因?yàn)槊看畏至鸦蚝喜r(shí)無(wú)法知道操作點(diǎn)所屬$treap$的根，屬于我們將每個(gè)點(diǎn)的父節(jié)點(diǎn)記錄下來(lái)然后反向分裂(即自下而上分裂)。

寫(xiě)的時(shí)候不要按順時(shí)針或逆時(shí)針判斷位于某個(gè)點(diǎn)時(shí)的方向，對(duì)于豎墻，左下右上；對(duì)于橫墻，上左下右。

#include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<bitset> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int f[1200010]; int ls[1200010]; int rs[1200010]; int r[1200010]; int size[1200010]; int vis[510][510][4]; int n,m,q; int opt; int a,b,c,d,e; int s,t; int x,y,z,w; int sum; int root; inline void pushup(int rt) {size[rt]=size[ls[rt]]+size[rs[rt]]+1; } inline int merge(int x,int y) {if(!x||!y){return x+y;}if(r[x]<r[y]){rs[x]=merge(rs[x],y);f[rs[x]]=rs[x]?x:0;pushup(x);return x;}else{ls[y]=merge(x,ls[y]);f[ls[y]]=ls[y]?y:0;pushup(y);return y;} } inline void split(int rt,int &a,int &b) {int x=ls[rt],y=rs[rt];ls[rt]=rs[rt]=0;int now=rt;pushup(rt);while(f[rt]){if(ls[f[rt]]==rt){ls[f[rt]]=y;f[y]=f[rt];y=f[rt];pushup(y);}else{rs[f[rt]]=x;f[x]=f[rt];x=f[rt];pushup(x);}rt=f[rt];}f[x]=f[y]=0;f[now]=0;a=x,b=y; } inline int find(int rt) {while(f[rt]){rt=f[rt];}return rt; } inline int rank(int rt) {int res=size[ls[rt]]+1;while(f[rt]){if(rs[f[rt]]==rt){res+=size[ls[f[rt]]]+1;}rt=f[rt];}return res; } inline int get(int x,int y,int id,int num) {if(id==1){return (x-1)*(m+1)+y+num*sum;}else{return (x-1)*m+y+(m+1)*n+num*sum;} } inline int check(int x,int y,int id,int num) {if(id==0){if(num==0){for(int i=1;i<=3;i++){if(vis[x][y][i%4]){return i%4;}}}else{for(int i=3;i>=1;i--){if(vis[x][y][i%4]){return i%4;}}}}else if(id==1){if(num==0){for(int i=2;i<=4;i++){if(vis[x][y][i%4]){return i%4;}}}else{for(int i=4;i>=2;i--){if(vis[x][y][i%4]){return i%4;}}}}else if(id==2){if(num==0){for(int i=3;i<=5;i++){if(vis[x][y][i%4]){return i%4;}}}else{for(int i=5;i>=3;i--){if(vis[x][y][i%4]){return i%4;}}}}else{if(num==0){for(int i=0;i<=2;i++){if(vis[x][y][i%4]){return i%4;}}}else{for(int i=2;i>=0;i--){if(vis[x][y][i%4]){return i%4;}}}}return -1; } inline int ask(int x,int y,int id,int num) {if(id==0){return get(x,y,2,num);}else if(id==1){return get(x,y,1,num^1);}else if(id==2){return get(x,y-1,2,num^1);}else{return get(x-1,y,1,num);} } inline void ins(int a,int b,int c,int id) {if(id==1){if(check(b,a,1,0)==-1&&check(c,a,3,0)==-1){root=merge(get(b,a,1,0),get(b,a,1,1));}else if(check(b,a,1,0)==-1){int num=check(c,a,3,0);x=ask(c,a,num,0);split(x,y,z);root=merge(merge(y,x),merge(merge(get(c-1,a,1,1),get(c-1,a,1,0)),z));}else if(check(c,a,3,0)==-1){int num=check(b,a,1,1);x=ask(b,a,num,1);split(x,y,z);root=merge(merge(y,merge(get(b,a,1,0),get(b,a,1,1))),merge(x,z));}else{int num1=check(b,a,1,1);int num2=check(c,a,3,0);int rt1=ask(b,a,num1,1);int rt2=ask(c,a,num2,0);if(find(rt1)!=find(rt2)){split(rt1,x,y);split(rt2,z,w);int fx=merge(merge(z,rt2),merge(get(b,a,1,1),merge(rt1,y)));int fy=merge(x,merge(get(b,a,1,0),w));root=merge(fy,fx);}else{split(rt1,x,y);if(find(rt2)==x){split(rt2,z,w);root=merge(merge(rt1,y),merge(merge(z,rt2),get(b,a,1,1)));root=merge(get(b,a,1,0),w);}else{split(rt2,z,w);root=merge(merge(rt1,z),merge(rt2,get(b,a,1,1)));root=merge(get(b,a,1,0),merge(w,x));}}}}else{if(check(a,b,0,0)==-1&&check(a,c,2,0)==-1){root=merge(get(a,b,2,0),get(a,b,2,1));}else if(check(a,b,0,0)==-1){int num=check(a,c,2,0);x=ask(a,c,num,0);split(x,y,z);root=merge(merge(y,x),merge(merge(get(a,b,2,0),get(a,b,2,1)),z));}else if(check(a,c,2,0)==-1){int num=check(a,b,0,1);x=ask(a,b,num,1);split(x,y,z);root=merge(merge(y,merge(get(a,b,2,1),get(a,b,2,0))),merge(x,z));}else{int num1=check(a,b,0,1);int num2=check(a,c,2,0);int rt1=ask(a,b,num1,1);int rt2=ask(a,c,num2,0);if(find(rt1)!=find(rt2)){split(rt1,x,y);split(rt2,z,w);int fx=merge(merge(z,rt2),merge(get(a,b,2,0),merge(rt1,y)));int fy=merge(x,merge(get(a,b,2,1),w));root=merge(fy,fx);}else{split(rt1,x,y);if(find(rt2)==x){split(rt2,z,w);root=merge(merge(rt1,y),merge(merge(z,rt2),get(a,b,2,0)));root=merge(get(a,b,2,1),w);}else{split(rt2,z,w);root=merge(merge(rt1,z),merge(rt2,get(a,b,2,0)));root=merge(get(a,b,2,1),merge(w,x));}}}} } inline void del(int a,int b,int c,int id) {if(id==1){if(check(b,a,1,0)==-1&&check(c,a,3,0)==-1){split(get(b,a,1,0),x,y);}else if(check(b,a,1,0)==-1){int rt1=get(c-1,a,1,1);int rt2=get(c-1,a,1,0);split(rt1,x,y);root=merge(x,y);split(rt2,x,y);root=merge(x,y);}else if(check(c,a,3,0)==-1){int rt1=get(b,a,1,0);int rt2=get(b,a,1,1);split(rt1,x,y);root=merge(x,y);split(rt2,x,y);root=merge(x,y);}else{int rt1=get(b,a,1,0);int rt2=get(b,a,1,1);if(find(rt1)!=find(rt2)){split(rt1,x,y);split(rt2,z,w);root=merge(merge(x,w),merge(z,y));}else{split(rt1,x,y);if(find(rt2)==x){split(rt2,z,w);root=merge(y,z);}else{split(rt2,z,w);root=merge(w,x);}}}}else{if(check(a,b,0,0)==-1&&check(a,c,2,0)==-1){split(get(a,b,2,0),x,y);}else if(check(a,b,0,0)==-1){int rt1=get(a,b,2,0);int rt2=get(a,b,2,1);split(rt1,x,y);root=merge(x,y);split(rt2,x,y);root=merge(x,y);}else if(check(a,c,2,0)==-1){int rt1=get(a,b,2,0);int rt2=get(a,b,2,1);split(rt1,x,y);root=merge(x,y);split(rt2,x,y);root=merge(x,y);}else{int rt1=get(a,b,2,0);int rt2=get(a,b,2,1);if(find(rt1)!=find(rt2)){split(rt1,x,y);split(rt2,z,w);root=merge(merge(z,y),merge(x,w));}else{split(rt1,x,y);if(find(rt2)==x){split(rt2,z,w);root=merge(y,z);}else{split(rt2,z,w);root=merge(w,x);}}}} } inline int query(int s,int t) {root=find(s);if(root!=find(t)){return -1;}int rs=rank(s);int rt=rank(t);if(rs<=rt){return rt-rs;}else{return size[root]-(rs-rt);} } int main() {srand(12378);scanf("%d%d%d",&n,&m,&q);sum=n*(m+1)+m*(n+1);for(int i=1;i<=2*sum;i++){size[i]=1;r[i]=rand();}for(int i=1;i<=m;i++){root=merge(root,get(1,i,2,1));vis[1][i][0]=vis[1][i+1][2]=1;}for(int i=1;i<=n;i++){root=merge(root,get(i,m+1,1,0));vis[i][m+1][1]=vis[i+1][m+1][3]=1;}for(int i=m;i>=1;i--){root=merge(root,get(n+1,i,2,0));vis[n+1][i][0]=vis[n+1][i+1][2]=1;}for(int i=n;i>=1;i--){root=merge(root,get(i,1,1,1));vis[i][1][1]=vis[i+1][1][3]=1;}for(int i=1;i<=n;i++){for(int j=2;j<=m;j++){scanf("%d",&x);if(x){ins(j,i,i+1,1);vis[i][j][1]=vis[i+1][j][3]=1;}}}for(int i=2;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&x);if(x){ins(i,j,j+1,2);vis[i][j][0]=vis[i][j+1][2]=1;}}}while(q--){scanf("%d",&opt);if(opt==1){scanf("%d%d%d%d",&a,&b,&c,&d);a++,b++,c++,d++;if(a>c)swap(a,c);if(b>d)swap(b,d);if(b==d){ins(b,a,c,1);vis[a][b][1]=vis[c][d][3]=1;}else{ins(a,b,d,2);vis[a][b][0]=vis[c][d][2]=1;}}else if(opt==2){scanf("%d%d%d%d",&a,&b,&c,&d);a++,b++,c++,d++;if(a>c)swap(a,c);if(b>d)swap(b,d);if(b==d){vis[a][b][1]=vis[c][d][3]=0;del(b,a,c,1);}else{vis[a][b][0]=vis[c][d][2]=0;del(a,b,d,2);}}else{scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);a++,b++,c++,d++;if(a>c)swap(a,c);if(b>d)swap(b,d);if(b==d){s=get(a,b,1,e);}else{s=get(a,b,2,e);}scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);a++,b++,c++,d++;if(a>c)swap(a,c);if(b>d)swap(b,d);if(b==d){t=get(a,b,1,e);}else{t=get(a,b,2,e);}printf("%d\n",query(s,t));}} }

轉(zhuǎn)載于:https://www.cnblogs.com/Khada-Jhin/p/10787480.html

總結(jié)

以上是生活随笔為你收集整理的[BJOI2019]送别——非旋转treap的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。