「yyOI R1」youyou 的军训

· · 题解

给一篇不用倍增的题解。

题意

给定一个无向图，每次在原图基础上删去所有边权小于 q 的边，查询一个点所在联通块的大小。边权带修，但相对大小不变。

题解

可以发现，删完边以后最多只有 n 种状态，考虑将其预处理。题目保证：所有对朋友关系之间的敏感值互不相同，所以可以看作每次从小到大将一条边删去，维护每个点的连通块大小。考虑其逆过程，非常巧啊，这不就是 Kruskal 算法生成最大生成树吗！而且题目保证：修改后的敏感值与原来的敏感值排名相同，所以最大生成树的形态不会改变。

定义 siz_i 表示 i 所在的连通块大小，fa_i 表示 i 所在的连生成树的根节点。为了方便维护连通块的大小，只需要维护 siz_{fa_i} 的大小即可。每次合并时，只需修改根节点的 siz 即可。

但这样还不够，空间复杂度不能接受，用可持久化数组就太过麻烦了。考虑直接将询问离线，在每次 1 操作时，将当前状态要删的边数下有哪几个节点需要查询记录下来即可。对于每个 3 操作，可以发现一个点的答案，只与当前要删几条边有关，所以直接在原数组修改即可。

时间复杂度 \mathcal O(n \log n)，瓶颈在排序以及二分。

代码

#include<bits/stdc++.h>
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
inline char readchar(){
    if(p1!=p2) {
        return *p1++;
    }
    return p1==(p2=(p1=buf)+fread(buf,1,Size-1,stdin))?EOF:*p1++;
}
inline void flush(){
    fwrite(buffer,1,op1+1,stdout),op1=-1;
}
inline void writechar(const char &x) {
    if(op1==op2) flush();
    buffer[++op1]=x;
}
#ifndef ONLINE_JUDGE
#define readchar getchar
#endif
#define putchar writechar
inline int read() {
    int s=1,c=readchar(),x=0;
    while(c<=32) {
        c=readchar();
    }
    if(c=='-') {
        s=-1,c=readchar();
    }
    for(; ('0'<=c && c<='9'); c=readchar()) {
        x=x*10+c-'0';
    }
    return x*s;
}
inline void print(long long x) {
    if(x<0) {
        writechar('-'),x=-x;
    }
    char s[25];
    int n=0;
    while(x||!n) {
        s[n++]='0'+x%10,x/=10;
    }
    while(n--) {
        writechar(s[n]);
    }
}
const int N=4e5+5;
int n,m,T,i,j,rk[N],ans[N],cnt,opt,x,y,l,r,mid,len,fa[N],siz[N];
struct ed{
    int x,y,k,id;
}a[N];
struct nd{
   int id,val;
};
vector<nd>g[N];
inline bool cmp(ed x,ed y){
    return x.k>y.k;
}
inline int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
signed main() {
    n=read();m=read();T=read();
    for(i=1;i<=m;i++){
        a[i].x=read();a[i].y=read();
        a[i].k=read();a[i].id=i;
    }
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++)
       rk[a[i].id]=i;
    int cur=m;
    for(i=1;i<=T;i++){
        opt=read();x=read();
        if(opt==1){
            l=1;r=m;
            int ans=0;
            while(l<=r){//二分出要保留几条边
                mid=l+r>>1;
                if(a[mid].k>=x){
                    l=mid+1;
                    ans=mid;
                }
                else r=mid-1;
            }
            cur=ans;
        }
        else if(opt==2){
            nd tmp;
            tmp.id=++len;tmp.val=x;
            g[cur].push_back(tmp);
        }
        else a[rk[x]].k=read();
    }
    for(i=1;i<=n;i++)fa[i]=i,rk[i]=siz[i]=1;//注意，这里的rk数组用于并查集按秩合并，为了省空间用了相同的数组
    for(auto i:g[0])ans[i.id]=1;
    for(i=1;i<=m;i++){
        int fx=find(a[i].x),fy=find(a[i].y);
        if(fx!=fy){//按秩合并
             if(rk[fx]<=rk[fy])fa[fy]=fx,siz[fx]+=siz[fy];
            else fa[fy]=fx,siz[fy]+=siz[fx];
            if(rk[fx]==rk[fy]&&fx!=fy)rk[fy]++;
        }
        for(auto j:g[i])
           ans[j.id]=siz[find(j.val)];
    } 
    for(i=1;i<=len;i++)
      print(ans[i]),putchar('\n');
    flush();
    return 0;
}