[CSP校内集训]打扑克

题意

有\(n\)堆大小为1的扑克，支持合并两堆扑克和查询有多少对扑克堆满足\(|size_i-size_j|\leq c\)，（\(c\)不确定）

思路

暴力做法：开桶记录当前存在有多少个大小为\(i\)的堆，查询可用树状数组或者双指针，时间复杂度\(O(m^2logn)\)或者\(O(m^2)\)

优化：发现枚举大小的桶有很多是空的，实际上，可以证明\(m\)次操作最多出现\(\sqrt{m}\)种不同的堆大小，用一个时刻有序的\(vector/multiset\)即可

Code

（写的太丑了贴个本校大佬的代码）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#define ll long long
using namespace std;
template < class T > inline void read (T &x){
    x=0;char ch=getchar();bool f=0;
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int maxn=1000001;
int n;
int num[maxn];
int fa[maxn];
int getfa (int x){
    if (x==fa[x]) return x;
    return fa[x]=getfa (fa[x]);
}
ll blans[maxn],bloans[maxn];
int siz[maxn];
int blosiz;
int bel[maxn];
int las;
void pre (){
    for (register int i=1;i<=n;++i){
        fa[i]=i; siz[i]=1;
    }
    blans[0]=1ll*n*(n-1)/2ll; num[1]=n;
    blosiz=(int)sqrt (n);
    for (register int i=1;i<=n;++i){
        if (i%blosiz) bel[i]=(i/blosiz)+1;
        else bel[i]=i/blosiz;
    }
    bloans[0]=blans[0]; las=bel[n];
}
int m;
vector < int > vec;
vector < int >::iterator it;
ll query (int x){
    ll ans=0;
    for (int i=x;i<=(bel[x]*blosiz);++i) ans+=blans[i];
    for (int i=bel[x]+1;i<=las;++i) ans+=bloans[i];
    return ans;
}
int main(){
    freopen ("cards.in","r",stdin); freopen ("cards.out","w",stdout);
    read (n); read (m);
    pre();
    while (m--){
        int opt; read (opt);
        if (opt==1){
            int x,y; read (x); read (y);
            x=getfa (x); y=getfa (y);
            if (x==y) continue ;
            if (siz[x]<=blosiz) num[siz[x]]--;
            else vec.erase (lower_bound (vec.begin(),vec.end(),siz[x]));
            for (int i=1;i<=blosiz;++i){
                int k=abs(i-siz[x]);
                blans[k]-=num[i]; bloans[bel[k]]-=num[i];
            }
            for (it=vec.begin();it!=vec.end();++it){
                int k=abs(*it-siz[x]);
                blans[k]--; bloans[bel[k]]--;
            }
            if (siz[y]<=blosiz) num[siz[y]]--;
            else vec.erase (lower_bound (vec.begin(),vec.end(),siz[y]));
            for (int i=1;i<=blosiz;++i){
                int k=abs(i-siz[y]);
                blans[k]-=num[i]; bloans[bel[k]]-=num[i];
            }
            for (it=vec.begin();it!=vec.end();++it){
                int k=abs(*it-siz[y]);
                blans[k]--; bloans[bel[k]]--;
            }
            for (int i=1;i<=blosiz;++i){
                int k=abs(i-siz[x]-siz[y]);
                blans[k]+=num[i]; bloans[bel[k]]+=num[i];
            }
            for (it=vec.begin();it!=vec.end();++it){
                int k=abs(*it-siz[x]-siz[y]);
                blans[k]++; bloans[bel[k]]++;
            }
            if ((siz[x]+siz[y])<=blosiz) num[siz[x]+siz[y]]++;
            else vec.insert (lower_bound (vec.begin(),vec.end(),siz[x]+siz[y]),siz[x]+siz[y]);
            if (siz[x]<siz[y]) swap (x,y);
            siz[x]+=siz[y]; fa[y]=x;
        }
        if (opt==2){
            int x; read (x);
            if (x<0) x=0;
            printf ("%lld",query (x));
            if (m) printf ("\n");
        }
    }
    return 0;
}