BZOJ4777 [Usaco2017 Open]Switch Grass[最小生成树+权值线段树套平衡树]

标题解法是吓人的。

图上修改询问，不好用数据结构操作。尝试转化为树来维护。发现（不要问怎么发现的）最小生成树在这里比较行得通，因为最近异色点对一定是相邻的（很好想），所以只要看最短的一条两端连着异色点的边，而分析一下kruskal的过程，发现满足这种要求的最小边一定会被加进去（因为相邻异色点总要联通），所以不管颜色怎么修改，答案一定在最小生成树上。于是，问题转化为了一棵树。`````

修改一个点的颜色，不妨只关心他和他儿子之间的所有边。由于要查询和自己颜色不同的儿子的最小权值，与颜色有关，所以可以对于每个点，开一个动态开点的以颜色为权值的线段树维护最小边权，这样可以直接把儿子插进去，查颜色$[1,color_x)cup(color_x,k]$的最小值，这样$color_x$变化也可以快速查询啦。但是，由于原来的颜色没有了，所以要把自己原来的颜色从父亲对应的树上删掉，为了保证其他相同颜色的权值不会被影响，所以线段树每个叶子要开一个平衡树（这里用了multiset），来维护相同颜色的各种权值，然后删除这个点就行了，然后再再把新的颜色插入到父亲里。对于每个点，到儿子的最小异色点距离如果是$f_x$，那么每次修改，父亲和自己的$f_x$会变动，求全局$f$只要在开一个multiset就好了。

空间问题：初始每个点会被父亲插入一次，插入multiset一次，总的被插入$n$个点，之后的每次修改，每次父亲插入新的颜色一次，插入新的multiset一次，空间量级$O((n+q)log n+(n+q))$。

时间：$O((n+q)log^2 n)$。

Note：细节注意。

Note：BZOJ跑的比较卡内存，所以把内存开小了一点才贴着上限过的。下面的code没改小。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<queue>
  7 #include<set>
  8 #define dbg(x) cerr << #x << " = " << x <<endl
  9 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
 10 using namespace std;
 11 typedef long long ll;
 12 typedef double db;
 13 typedef pair<int,int> pii;
 14 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
 15 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
 16 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
 17 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
 18 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
 19 template<typename T>inline T read(T&x){
 20     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
 21     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
 22 }
 23 const int N=2e5+7,INF=0x3f3f3f3f;
 24 struct tree_edge{int nxt,to,w;}G[N<<1];
 25 struct edge{
 26     int u,v,w;
 27     inline bool operator <(const edge&A)const{return w<A.w;}
 28 }e[N];
 29 int Head[N],tot;
 30 int n,m,k,q;
 31 inline void Addedge(int x,int y,int z){
 32     G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot,G[tot].w=z;
 33     G[++tot].to=x,G[tot].nxt=Head[y],Head[y]=tot,G[tot].w=z;
 34 }
 35 int anc[N];
 36 inline int get_anc(int x){return anc[x]==x?x:anc[x]=get_anc(anc[x]);}
 37 inline void Kruskal(){
 38     sort(e+1,e+m+1);
 39     for(register int i=1;i<=n;++i)anc[i]=i;
 40     for(register int i=1;i<=m;++i)if(get_anc(e[i].u)^get_anc(e[i].v))anc[anc[e[i].u]]=anc[e[i].v],Addedge(e[i].u,e[i].v,e[i].w);
 41 }
 42 
 43 struct segment_tree{
 44     int lc[N*36],rc[N*36],minv[N*36],pos[N*36],cnt,mt;
 45     multiset<int> s[N<<1];
 46     segment_tree(){memset(minv,0x3f,sizeof minv);}
 47     inline void pushup(int i){minv[i]=_min(minv[lc[i]],minv[rc[i]]);}
 48     void Insert(int&i,int L,int R,int c,int w){
 49         if(!i)i=++cnt;
 50         if(L==R){
 51             if(!pos[i])pos[i]=++mt;
 52             s[pos[i]].insert(w);minv[i]=*s[pos[i]].begin();
 53             return;
 54         }
 55         int mid=L+R>>1;
 56         if(c<=mid)Insert(lc[i],L,mid,c,w);
 57         else Insert(rc[i],mid+1,R,c,w);
 58         pushup(i);
 59     }
 60     int Query_min(int i,int L,int R,int ql,int qr){
 61         if(ql<=L&&qr>=R)return minv[i];
 62         int mid=L+R>>1,ret=INF;
 63         if(ql<=mid)MIN(ret,Query_min(lc[i],L,mid,ql,qr));
 64         if(qr>mid)MIN(ret,Query_min(rc[i],mid+1,R,ql,qr));
 65         return ret;
 66     }
 67     void Delete(int i,int L,int R,int c,int w){
 68         if(L==R){
 69             s[pos[i]].erase(s[pos[i]].find(w));
 70             minv[i]=s[pos[i]].empty()?INF:*s[pos[i]].begin();
 71             return;
 72         }
 73         int mid=L+R>>1;
 74         if(c<=mid)Delete(lc[i],L,mid,c,w);
 75         else Delete(rc[i],mid+1,R,c,w);
 76         pushup(i);
 77     }
 78 }T;
 79 
 80 int minv[N],fa[N],wt[N],val[N],rt[N];
 81 multiset<int> ans;
 82 #define y G[j].to
 83 void dfs(int x,int fat){
 84     fa[x]=fat;
 85     for(register int j=Head[x];j;j=G[j].nxt)if(y^fat)dfs(y,x),T.Insert(rt[x],1,k,val[y],wt[y]=G[j].w);
 86     if(rt[x])minv[x]=_min(val[x]>1?T.Query_min(rt[x],1,k,1,val[x]-1):INF,val[x]<k?T.Query_min(rt[x],1,k,val[x]+1,k):INF),ans.insert(minv[x]);
 87 }
 88 #undef y
 89 inline void change_father(int x,int c){
 90     if(!fa[x])return;
 91     T.Delete(rt[fa[x]],1,k,val[x],wt[x]);//dbg("delete ok");
 92     T.Insert(rt[fa[x]],1,k,c,wt[x]);//dbg("insert ok");
 93     ans.erase(ans.find(minv[fa[x]]));
 94     ans.insert(minv[fa[x]]=_min(val[fa[x]]>1?T.Query_min(rt[fa[x]],1,k,1,val[fa[x]]-1):INF,val[fa[x]]<k?T.Query_min(rt[fa[x]],1,k,val[fa[x]]+1,k):INF));
 95 //    dbg2("new father",minv[fa[x]]);
 96 }
 97 inline void change_self(int x,int c){
 98     if(!rt[x])return;
 99     ans.erase(ans.find(minv[x]));
100     ans.insert(minv[x]=_min(val[x]>1?T.Query_min(rt[x],1,k,1,val[x]-1):INF,val[x]<k?T.Query_min(rt[x],1,k,val[x]+1,k):INF));
101 //    dbg2("new self",minv[x]);
102 }
103 inline void Query(){
104     int x,c;
105     while(q--){
106         read(x),read(c);
107         change_father(x,c);
108         val[x]=c;
109         change_self(x,c);
110         printf("%d
",*ans.begin());
111     }
112 }
113 inline void Init(){
114     read(n),read(m),read(k),read(q);
115     for(register int i=1;i<=m;++i)read(e[i].u),read(e[i].v),read(e[i].w);
116     for(register int i=1;i<=n;++i)read(val[i]);
117 }
118 
119 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
120     Init();
121     Kruskal();
122     dfs(1,0);
123     Query();
124     return 0;
125 }

View Code

总结：图上的操作题如果觉得维护困难可以尝试转化成树上问题，这时不妨就看看MST可不可以。