题解：P15005 [UOI 2019 II Stage] 幸福值

· · 题解

时光倒流后用整体二分和可撤销并查集处理即可，但是忘了可以用可撤销并查集维护，所以采用的是每层回溯后重新遍历的方式。

如果采用后面的做法，显然得需要一个类似 BFS 形式的遍历，这里直接采用类似线段树的形式存贮的，似乎也比较好写，如果每层处理完后回收空间的话空间复杂度为线性，但这里比较懒没写，所以空间复杂度为线性对数。

#include<bits/stdc++.h>
using namespace std;
template <typename T>
void in(T &x){
    char c=getchar(), f=1;
    while ((c<'0' || c>'9') && c!='-') c=getchar();
    if (c=='-') f=-1, c=getchar();
    for (x=0; c>='0' && c<='9'; c=getchar())
        x=x*10+c-'0';
    x*=f;
}
#define pr pair<int,int>
#define mp make_pair
#define pb push_back
const int N=2e5+5;
int F[N],S[N];
int n,m,d,s,a[N],fa[N];
long long sz[N];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    x=find(x);y=find(y);
    if(x!=y){fa[x]=y;sz[y]+=sz[x];}
}
void copy(){for(int i=1;i<=n;i++)fa[i]=F[i],sz[i]=S[i];}
int op[N],x[N],y[N];
pr E[N];
map<pr,int>P;

struct Q{long long x,y,z,id;};
vector<Q>Ask[N<<2];
int ANS[N];
int L[N<<2],R[N<<2],mid[N<<2],D[N<<2];
void init(int o,int l,int r,int dep){
    L[o]=l,R[o]=r,mid[o]=(l+r)/2,D[o]=dep;
    if(l==r)return ;
    init(o<<1,mid[o]+1,r,dep+1);
    init(o<<1|1,l,mid[o],dep+1);
}
void calc(){
    int no=1,date=d;
    for(int i=1;i<=d*4;i++){
        if((int)Ask[i].size()==0)continue;
        if(L[i]==R[i]){
            for(auto tp:Ask[i])ANS[tp.id]=L[i];
            continue;
        }
        if(D[i]!=no){
            no=D[i];
            copy();
            date=d;
        }
        while(date>mid[i]+1){
            if(op[date]==1)merge(x[date],y[date]);
            else sz[find(x[date])]+=y[date];
            date--;
        }
        for(auto tp:Ask[i]){
            if(sz[find(tp.x)]+sz[find(tp.y)]>=tp.z)Ask[i<<1].pb(tp);
            else Ask[i<<1|1].pb(tp);
        }
    }
}
int main(){
    in(n);in(m);in(d);in(s);
    for(int i=1;i<=n;i++)in(a[i]);
    for(int i=1;i<=m;i++){
        int u,v;in(u);in(v);
        if(u>v)swap(u,v);
        E[i]=mp(u,v);P[mp(u,v)]=i;
    }
    for(int i=1;i<=d;i++){in(op[i]);in(x[i]);in(y[i]);}
    for(int i=1;i<=n;i++)sz[i]=a[i],fa[i]=i;
    for(int i=1;i<=m;i++){auto [x,y]=E[i];merge(x,y);}
    for(int i=1;i<=s;i++){
        long long x,y,z;in(x);in(y);in(z);
        if(sz[find(x)]+sz[find(y)]<z)ANS[i]=-1;
        else Ask[1].pb((Q){x,y,z,i});
    }
    for(int i=1;i<=d;i++){
        if(op[i]==1){
            if(x[i]>y[i])swap(x[i],y[i]);
            E[P[mp(x[i],y[i])]]=mp(1,1);
        }   
        else a[x[i]]-=y[i];
    }
    for(int i=1;i<=n;i++)sz[i]=a[i],fa[i]=i;
    for(int i=1;i<=m;i++){auto [x,y]=E[i];merge(x,y);}
    for(int i=1;i<=n;i++)F[i]=fa[i],S[i]=sz[i];
    init(1,0,d,1);
    calc();
    for(int i=1;i<=s;i++)printf("%d\n",ANS[i]);
    return 0;
}