2 条题解
-
1
#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; } } }
-
0
平衡树板子
题目要求维护很多条链,不难想到用平衡树,个人用的是 fhq treap 。
将边化成点,每一棵 treap 都以点边点的顺序存了一条链,代表边的点权值为边权,代表点的点权值为 。
操作一
加边操作,合法的条件是:
-
不在同一棵子树。
-
两个点都在链头或链尾,即中序遍历最大或最小。
如果 同时在链头或同时在链尾还要翻转一下 treap 。
然后把 放最后, 放最前,两棵树之间插入边权为 的一个代表边的点,合起来就行。
操作二
删边操作,合法的条件是:
-
在同一棵子树
-
两个点之间只隔了一个代表边的点。
满足条件就直接把那个代表边的点拆掉就行。
操作三
本质上与上面两个一样,读者自行理解。
操作四
判断一下根是否相等就好。
操作五
首先还是判断 是否同根,不同根直接返回。
然后比较一下 在 treap 中排名的大小,不妨设为 。
-
如果 ,要往右边走,于是终点就是最右端的点,时间为 节点后的边权和。
-
如果 ,要往左边走,于是终点就是最左端的点,时间为 节点前的边权和。
实现细节
有几个坑点提一下:
-
查询根和排名需要维护节点父亲,然后从当前节点往上跳统计答案。
-
查询排名时一定要释放从根到它的所有翻转标记。
代码
#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; } } }
-
- 1
信息
- ID
- 4470
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 3
- 已通过
- 2
- 上传者