USACO 2017 Open Platinum

Description:

有一个$n$个点，$m$条边的图，每个点都有颜色，颜色种类的范围为$[1,K]$。 现在有$q$个操作，每个操作将点$x$的颜色改为$k$，在每个操作后求不同颜色的最小距离。 $n\le 2\cdot 10^5,m\le 4\cdot 10^5,K\le 10^6,q\le 2\cdot 10^5,w_i\le 10^6$

Solution:

对于这个$n$为$2\cdot 10^5$的图，大概已经没有什么图论算法可以解决问题了而且我们发现答案一定是给定的某一边的边权对于暴力的做法（$\Theta (ml\log mq)$），我们是将边权排序，找最小不同颜色的边而将边排序，我们很容易联想到最小生成树，那么答案是不是一定在最小生成树上呢？我们可以来反证一下若答案是一条非树（最小生成树）边，那么该边的两点颜色不同，且这两点之间一定有树边，且这些树边的边权一定比这条非树边小，且一定会有至少一条不同颜色的点的边。这样，我们可以用线段树来维护树上每个点与它颜色为$c$的儿子的最小距离。但是操作还要修改，就需要用一个全局的$multiset$来维护答案。这样复杂度是$\Theta (n\log n)$。

Code

#include<bits/stdc++.h> using namespace std; #define REP(i,f,t) for(int i=(f),i##_end_=(t);i<=i##_end_;++i) #define SREP(i,f,t) for(int i=(f),i##_end_=(t);i<i##_end_;++i) #define DREP(i,f,t) for(int i=(f),i##_end_=(t);i>=i##_end_;--i) #define ll long long template<class T>inline bool chkmin(T &x,T y){return x>y?x=y,1:0;} template<class T>inline bool chkmax(T &x,T y){return x<y?x=y,1:0;} template<class T>inline void Rd(T &x){ x=0;char c; while((c=getchar())<48); do x=(x<<1)+(x<<3)+(c^48); while((c=getchar())>47); } const int N=2e5+2,INF=0x3f3f3f3f; int n,m,K,q; int col[N]; struct node{ int x,y,w,id; bool operator<(const node &_)const{ return w<_.w; } }em[N<<1]; struct p40{ void solve(){ while(q--){ int x,k; Rd(x),Rd(k); col[x]=k; REP(i,1,m){ if(col[em[i].x]==col[em[i].y])continue; printf("%d\n",em[i].w); break; } } } }p1; struct p100{ int fa[N]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int qwq,head[N]; struct edge{ int to,nxt,w; }E[N<<1]; void addedge(int x,int y,int z){E[qwq]=(edge){y,head[x],z};head[x]=qwq++;} int Fa[N],dis[N]; int res[N]; multiset<int>ans; int tim,rt[N]; int Lson[N*40],Rson[N*40],Mn[N*40]; int cnt,Id[N*40];//叶子 multiset<int>Leaf[N<<1]; void Update(int l,int r,int x,int w,int op,int &p){ if(!p) p=++tim,Mn[p]=INF; if(l==r){ if(!Id[p])Id[p]=++cnt,Leaf[Id[p]].insert(INF); if(op)Leaf[Id[p]].insert(w); else Leaf[Id[p]].erase(Leaf[Id[p]].find(w)); Mn[p]=*Leaf[Id[p]].begin(); return; } int mid=(l+r)>>1; if(x<=mid)Update(l,mid,x,w,op,Lson[p]); else Update(mid+1,r,x,w,op,Rson[p]); chkmin(Mn[p]=Mn[Lson[p]],Mn[Rson[p]]); } int Query(int l,int r,int L,int R,int p){ if(!p || L>R)return INF; if(l==L && r==R) return Mn[p]; int mid=(l+r)>>1; if(R<=mid)return Query(l,mid,L,R,Lson[p]); else if(L>mid)return Query(mid+1,r,L,R,Rson[p]); else return min(Query(l,mid,L,mid,Lson[p]),Query(mid+1,r,mid+1,R,Rson[p])); } void dfs(int x){ for(int i=head[x];~i;i=E[i].nxt){ int y=E[i].to; if(y==Fa[x])continue; Fa[y]=x; Update(1,K,col[y],dis[y]=E[i].w,1,rt[x]); dfs(y); } } void solve(){ REP(i,1,n)fa[i]=i; memset(head,-1,sizeof(head)); int num=0; REP(i,1,m){ int x=em[i].x,y=em[i].y; int fx=find(x),fy=find(y); if(fx!=fy){ fa[fx]=fy; addedge(x,y,em[i].w); addedge(y,x,em[i].w); ++num; } if(num==n-1)break; } Mn[0]=INF; dfs(1); REP(i,1,n) res[i]=min(Query(1,K,1,col[i]-1,rt[i]),Query(1,K,col[i]+1,K,rt[i])),ans.insert(res[i]); while(q--){ int x,k; Rd(x),Rd(k); ans.erase(ans.find(res[x])); res[x]=min(Query(1,K,1,k-1,rt[x]),Query(1,K,k+1,K,rt[x])); ans.insert(res[x]); if(x!=1){ int f=Fa[x]; ans.erase(ans.find(res[f])); Update(1,K,col[x],dis[x],0,rt[f]),Update(1,K,k,dis[x],1,rt[f]); res[f]=min(Query(1,K,1,col[f]-1,rt[f]),Query(1,K,col[f]+1,K,rt[f])); ans.insert(res[f]); } col[x]=k; printf("%d\n",*ans.begin()); } } }p2; int main(){ // freopen("war.in","r",stdin); // freopen("war.out","w",stdout); Rd(n),Rd(m),Rd(K),Rd(q); REP(i,1,m){ int a,b,c; Rd(a),Rd(b),Rd(c); em[i]=(node){a,b,c,i}; } REP(i,1,n) Rd(col[i]); sort(em+1,em+1+m); if(m<=10000 && q<=10000)p1.solve();//O(mlogm+mq) else p2.solve();//O(nlogn) return 0; }