题解 [JSOI2013]公交系统
平衡树板子
题目要求维护很多条链，不难想到用平衡树，个人用的是 fhq treap 。
将边化成点，每一棵 treap 都以点边点的顺序存了一条链，代表边的点权值为边权，代表点的点权值为
操作一
加边操作，合法的条件是：
-
不在同一棵子树。
-
两个点都在链头或链尾，即中序遍历最大或最小。
如果
然后把
操作二
删边操作，合法的条件是：
-
在同一棵子树
-
两个点之间只隔了一个代表边的点。
满足条件就直接把那个代表边的点拆掉就行。
操作三
本质上与上面两个一样，读者自行理解。
操作四
判断一下根是否相等就好。
操作五
首先还是判断
然后比较一下
-
如果
rx<ry ，要往右边走，于是终点就是最右端的点，时间为x 节点后的边权和。 -
如果
rx>ry ，要往左边走，于是终点就是最左端的点，时间为x 节点前的边权和。
实现细节
有几个坑点提一下：
-
查询根和排名需要维护节点父亲，然后从当前节点往上跳统计答案。
-
查询排名时一定要释放从根到它的所有翻转标记。
代码
#include<cstdio>
#include<cstdlib>
#define rep(a,b,c) for(int c=(a);c<=(b);++c)
#define drep(a,b,c) for(int c=(a);c>=(b);--c)
inline int read()
{
int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
inline int Get()
{
char ch;do ch=getchar();while(ch<'a'||ch>'z');switch(ch)
{
case 'a': return 1;case 'c': return 3;case 'r': return 4;
case 'd': getchar();return getchar()=='l'?2:5;
}return 0;
}
inline void print(const int &p){if(p>9)print(p/10);putchar(p%10+'0');}
inline void pt(const int &p,const char &ch='\n'){print(p<0?putchar('-'),-p:p);putchar(ch);}
template<typename T> inline void Swap(T&x,T&y){T tmp=x;x=y;y=tmp;}
const int N=1e5+10;int T1,T2,T3,n,cgt;
struct FHQ{int l,r,siz,vl,sm,fa;bool tg;short key;inline FHQ(){key=rand();siz=1;}}t[N<<2];
inline void Rev(int x){Swap(t[x].l,t[x].r);t[x].tg^=1;}
inline void pushdown(int x){if(t[x].tg)Rev(t[x].l),Rev(t[x].r),t[x].tg=false;}
inline void update(int x)
{
t[x].siz=t[t[x].l].siz+t[t[x].r].siz+1;
t[x].sm=t[t[x].l].sm+t[t[x].r].sm+t[x].vl;
t[t[x].l].fa=t[t[x].r].fa=x;t[x].fa=0;
}
inline void split(int cur,int k,int &x,int &y)
{
if(!cur){x=y=0;return;}pushdown(cur);
if(t[t[cur].l].siz>=k){y=cur;split(t[cur].l,k,x,t[cur].l);update(y);return;}
x=cur;split(t[cur].r,k-t[t[cur].l].siz-1,t[cur].r,y),update(x);
}
inline int merge(int x,int y)
{
if(!x||!y)return x|y;pushdown(x);pushdown(y);
if(t[x].key<t[y].key){t[x].r=merge(t[x].r,y);update(x);return x;}
t[y].l=merge(x,t[y].l);update(y);return y;
}
inline int fnd(int x){while(t[x].fa)x=t[x].fa;return x;}
inline void pushall(int x){if(t[x].fa)pushall(t[x].fa);pushdown(x);}
inline int rnk(int k){pushall(k);int r=t[t[k].l].siz;while(t[k].fa){r+=(k==t[t[k].fa].r)?t[t[t[k].fa].l].siz+1:0;k=t[k].fa;}return r+1;}
inline void add(int x,int y,int z)
{
int fx=fnd(x),fy=fnd(y);
if(fx==fy)return puts("ERROR"),void();
int rx=rnk(x),ry=rnk(y);
if((rx==1||rx==t[fx].siz)&&(ry==1||ry==t[fy].siz))
{
if(rx==1)Swap(x,y),Swap(fx,fy),Swap(rx,ry);
if(rx==1)Rev(fx);if(ry==t[fy].siz)Rev(fy);
t[++cgt].siz=1;t[cgt].vl=t[cgt].sm=z;merge(merge(fx,cgt),fy);puts("OK");
}
else puts("ERROR");
}
inline void del(int x,int y)
{
int fx=fnd(x),fy=fnd(y);if(fx!=fy)return puts("ERROR"),void();
int rx=rnk(x),ry=rnk(y);if(rx>ry)Swap(rx,ry),Swap(fx,fy),Swap(x,y);
if(ry!=rx+2)puts("ERROR");else{split(fx,rx,T1,T2);split(T2,1,T1,T3);puts("OK");}
}
inline void chg(int x,int y,int z)
{
int fx=fnd(x),fy=fnd(y);if(fx!=fy)return puts("ERROR"),void();
int rx=rnk(x),ry=rnk(y);if(rx>ry)Swap(rx,ry),Swap(fx,fy),Swap(x,y);
if(ry!=rx+2)return puts("ERROR"),void();
split(fx,rx,T1,T2);split(T2,1,T2,T3);t[T2].sm=t[T2].vl=z;
merge(merge(T1,T2),T3);puts("OK");
}
inline void qry(int x,int y)
{
int fx=fnd(x),fy=fnd(y);if(fx!=fy)return puts("ERROR"),void();
int rx=rnk(x),ry=rnk(y);if(rx<ry)
{
int c=fx;while(t[c].r)pushdown(c),c=t[c].r,pushdown(c);pt(c,' ');
split(fx,rx,T1,T2);pt(t[T2].sm);merge(T1,T2);
}
else
{
int c=fx;while(t[c].l)pushdown(c),c=t[c].l,pushdown(c);pt(c,' ');
split(fx,rx,T1,T2);pt(t[T1].sm);merge(T1,T2);
}
}
int main()
{
t[0].siz=0;cgt=n=read();int Q=read();rep(1,Q,i)
{
int opt=Get(),x=read(),y=read();
switch(opt)
{
case 4: puts(fnd(x)==fnd(y)?"YES":"NO");break;
case 1: add(x,y,read());break;case 2: del(x,y);break;
case 3: chg(x,y,read());break;case 5: qry(x,y);break;
}
}
}