玄学cdq

O(nlog^2n)的动态最小生成树

其实就是按照时间cdq分治+剪枝（剪掉一定出现和不可能出现的边）

处理[l,r]之间的修改以及修改之后的询问，不能确定是否加入的边集为E

对于会被改变边权的边，边集为Q，暂时不能确定

不妨大力假设：

都是-inf，这个时候把Q的边都加入之后，剩下的E进行kruskal如果还能加入，那么在[l,r]这个区间里的所有询问，一定都能加进去

并查集带着必须边，然后处理Q都是inf，剩下的E进行kruskal，如果还是不能加入，那么在[l,r]这个区间里的所有询问，一定都不会加进去

这样，Q和第二次能加进去的边继续往左右递归，继续确定。

到了l==r时候，

把这个修改生效（因为之后再考虑的时候边权一定已经变了）

暴力把E中的边进行kruskal即可。

按秩合并并查集撤销，有些必须边出了[l,r]可能就被替换了。

 

说白了就是，cdq分治，强行维护备选边集+大力剪枝

感性理解一下复杂度：

看做n,m,q同阶

当Q中的边集最分散的时候，也就是形成一棵树，此时能确定的边是最少的。

这样，每次len/2，那么至少会多确定len/2个边（解放了n/2个点）

规模大概/=2

实际应该远不到上界，但是sort常数很大

O(nlog^2n)

 

注意，并查集不要随手写成路径压缩！！！

// luogu-judger-enable-o2// luogu-judger-enable-o2#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=50000+5;int n,m,q;struct edge{    int x,y,w;    bool friend operator <(edge a,edge b){        return a.w
          
            >buc;void push(int &x,int v){buc.push_back(mk(&x,x));x=v;}void roll(int t){ while((int)buc.size()>t) *buc.back().fi=buc.back().se,buc.pop_back();}void merge(int x,int y){ x=fin(x);y=fin(y); if(x==y) return; if(sz[x]>sz[y]) swap(x,y); push(fa[x],y);push(sz[y],sz[x]+sz[y]);}void wrk(vector
           
             &e,int l,int r,ll &val){ int st=buc.size(); static vector
            
             tmp;tmp.clear(); sort(e.begin(),e.end(),cmp); for(reg i=l;i<=r;++i) merge(E[Q[i].id].x,E[Q[i].id].y); for(solid i:e){ if(exi[i]==tag) continue; int x=fin(E[i].x),y=fin(E[i].y); if(x!=y){ merge(x,y);val+=E[i].w;tmp.pb(i); } } roll(st); for(solid i:tmp){ merge(E[i].x,E[i].y); }}void dele(vector
             
               &e){ vector
              
               tmp; sort(e.begin(),e.end(),cmp); int st=buc.size(); for(solid i:e){ if(exi[i]==tag){ tmp.pb(i);continue; } int x=fin(E[i].x),y=fin(E[i].y); if(x!=y){ merge(x,y);tmp.pb(i); } } roll(st); e.swap(tmp);}void sol(int l,int r,vector
               
                e,ll val){ // cout<<" l "<
                
                 <<" r "<
                 
                  <<" val "<
                  
                   <
                   
                    >1; sol(l,mid,e,val);sol(mid+1,r,e,val); } roll(st);}int main(){ rd(n);rd(m);rd(q); vector
                    
                     st; for(reg i=1;i<=m;++i){ rd(E[i].x);rd(E[i].y);rd(E[i].w); st.push_back(i); } for(reg i=1;i<=n;++i) fa[i]=i,sz[i]=1; for(reg i=1;i<=q;++i){ rd(Q[i].id);rd(Q[i].w); } sol(1,q,st,0); for(reg i=1;i<=q;++i){ printf("%lld\n",ans[i]); } return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/