BZOJ2816-[ZJOI2012]网络
题意:
题解:
丧心病狂数据结构题,题解想一会就想出来了,但打了半天.
可以发现每一种颜色都是由几条链构成,然后就可以用splay维护每种颜色的每条链,然后连接的时候如果是连接两条链的头部或两条链的尾部,需要翻转其中一条链.所以还要打一个区间翻转的标记.
#include<cstdio> #include<algorithm> #include<stack> #include<map> using namespace std; const int maxn=100000; struct splay_tree{ struct node{ int ch[2],fa,val,tot,sz; bool rev; }a[maxn+10]; int get_child(int p){ if(a[p].fa==-1) return -1; else if(a[a[p].fa].ch[0]==p) return 0; else if(a[a[p].fa].ch[1]==p) return 1; else return -1; } void push_down(int p){ if(a[p].rev){ if(a[p].ch[0]!=-1) a[a[p].ch[0]].rev^=1; if(a[p].ch[1]!=-1) a[a[p].ch[1]].rev^=1; swap(a[p].ch[0],a[p].ch[1]); a[p].rev=0; } } void push_fa_tag(int p,int fa){ stack<int> S; for(int i=p;i!=fa;i=a[i].fa) S.push(i); for(;!S.empty();S.pop()) push_down(S.top()); } void update(int p){ a[p].tot=a[p].val; a[p].sz=1; for(int i=0;i<=1;++i) if(a[p].ch[i]!=-1){ a[p].tot=max(a[p].tot,a[a[p].ch[i]].tot); a[p].sz+=a[a[p].ch[i]].sz; } } void rotate(int p){ int f=a[p].fa,d=get_child(p),dd=get_child(f); a[f].ch[d]=a[p].ch[d^1]; if(a[f].ch[d]!=-1) a[a[f].ch[d]].fa=f; a[p].ch[d^1]=f; a[p].fa=a[f].fa; if(dd!=-1) a[a[p].fa].ch[dd]=p; a[f].fa=p; update(f); update(p); } void splay(int p,int fa){ for(push_fa_tag(p,fa);a[p].fa!=fa;rotate(p)) if(a[a[p].fa].fa!=fa) if(get_child(p)==get_child(a[p].fa)) rotate(a[p].fa); else rotate(p); } int get_root(int p){ for(;a[p].fa!=-1;p=a[p].fa); return p; } }graph[10]; int n,m,c,k,v[maxn+10]; struct edge{ int u,v; edge(int u,int v):u(min(u,v)),v(max(u,v)){} bool operator<(const edge &t)const{ if(u!=t.u) return u<t.u; return v<t.v; } }; map<edge,int> color; void add_edge(int l,int r,int co){ color[edge(l,r)]=co; graph[co].splay(l,-1); graph[co].splay(r,-1); if(graph[co].a[l].ch[1]!=-1){ graph[co].a[l].rev^=1; graph[co].push_down(l); } if(graph[co].a[r].ch[0]!=-1){ graph[co].a[r].rev^=1; graph[co].push_down(r); } graph[co].a[l].ch[1]=r; graph[co].a[r].fa=l; graph[co].update(l); } void change_node(int p,int v){ for(int i=0;i<c;++i){ graph[i].splay(p,-1); graph[i].a[p].val=v; graph[i].update(p); } } void change_edge(int l,int r,int co){ edge eg(l,r); map<edge,int>::iterator it=color.find(eg); if(it==color.end()){ printf("No such edge. "); return; } if(co==it->second){ printf("Success. "); return; } graph[co].splay(l,-1); if(graph[co].a[l].ch[0]!=-1&&graph[co].a[l].ch[1]!=-1){ printf("Error 1. "); return; } graph[co].splay(r,-1); if(graph[co].a[r].ch[0]!=-1&&graph[co].a[r].ch[1]!=-1){ printf("Error 1. "); return; } if(graph[co].get_root(l)==graph[co].get_root(r)){ printf("Error 2. "); return; } if(graph[co].a[l].ch[1]!=-1){ graph[co].a[l].rev^=1; graph[co].push_down(l); } if(graph[co].a[r].ch[0]!=-1){ graph[co].a[r].rev^=1; graph[co].push_down(r); } graph[co].a[l].ch[1]=r; graph[co].a[r].fa=l; graph[co].update(l); int prev=it->second,d; it->second=co; graph[prev].splay(l,-1); graph[prev].splay(r,l); if(graph[prev].a[l].ch[0]==r) d=0; else if(graph[prev].a[l].ch[1]==r) d=1; graph[prev].a[l].ch[d]=-1; graph[prev].a[r].fa=-1; graph[prev].update(l); printf("Success. "); }; void query(int l,int r,int co){ int ans=max(graph[co].a[l].val,graph[co].a[r].val),d; if(l==r){ printf("%d ",ans); return; } if(graph[co].get_root(l)!=graph[co].get_root(r)){ printf("-1 "); return; } graph[co].splay(l,-1); graph[co].splay(r,l); if(graph[co].a[l].ch[0]==r) d=0; else if(graph[co].a[l].ch[1]==r) d=1; if(graph[co].a[r].ch[d^1]!=-1) ans=max(ans,graph[co].a[graph[co].a[r].ch[d^1]].tot); printf("%d ",ans); } int main(){ scanf("%d%d%d%d",&n,&m,&c,&k); for(int i=1;i<=n;++i) scanf("%d",&v[i]); for(int i=0;i<c;++i) for(int j=1;j<=n;++j){ graph[i].a[j].ch[0]=graph[i].a[j].ch[1]=graph[i].a[j].fa=-1; graph[i].a[j].val=v[j]; graph[i].update(j); } for(int i=1;i<=m;++i){ int l,r,co; scanf("%d%d%d",&l,&r,&co); add_edge(l,r,co); } for(int i=1;i<=k;++i){ int op,l,r,co; scanf("%d",&op); if(op==0){ scanf("%d%d",&l,&r); change_node(l,r); }else if(op==1){ scanf("%d%d%d",&l,&r,&co); change_edge(l,r,co); }else if(op==2){ scanf("%d%d%d",&co,&l,&r); query(l,r,co); } } return 0; }