引理
对于一个和为 \(n\) 的数列,不同的数的个数最多为 \(\sqrt n\)
证明:
一个有 \(n\) 个不同的数的数列,和最小就是 \(n\) 的排列时 \(\frac{n(n+1)}{2}\),是 \(\sqrt n\) 级别的。
那么,直接用 \(set\) 维护一下有多少不同的堆数,再记一个桶维护每种数的堆有多少个,询问时直接二分查找即可。
复杂度 \(\mathcal O\rm(q\sqrt nlogn)\)
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
struct nanfeng_stream{
template<typename T>inline nanfeng_stream operator>>(T &x) {
ri f=0;x=0;register char ch=gc();
while(!isdigit(ch)) f|=ch=='-',ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x=f?-x:x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define pb push_back
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=1e5+7,M=3e5+7;
std::set<int> st;
int tmp[N];
int fa[N],siz[N],T[N],sum[N],cnt,n,m;
ll ans;
int find(ri x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
inline int main() {
//FI=freopen("nanfeng.in","r",stdin);
//FO=freopen("nanfeng.out","w",stdout);
cin >> n >> m;
for (ri i(1);i<=n;p(i)) siz[fa[i]=i]=1;
st.insert(1);
T[1]=n;
for (ri z(1),opt,x,y,c;z<=m;p(z)) {
cin >> opt;
if (opt==1) {
cin >> x >> y;
//printf("x=%d y=%d\n",x,y);
int k1=find(x),k2=find(y);
//puts("tst");
if (k1==k2) continue;
fa[k2]=k1;
--T[siz[k1]];
--T[siz[k2]];
if (!T[siz[k1]]) st.erase(siz[k1]);
if (!T[siz[k2]]) st.erase(siz[k2]);
siz[k1]+=siz[k2];
if (!T[siz[k1]]) st.insert(siz[k1]);
++T[siz[k1]];
} else {
cin >> c;
cnt=ans=0;
for (auto x:st) tmp[++cnt]=x;
sum[cnt+1]=0;
for (ri i(cnt);i;--i) sum[i]=sum[i+1]+T[tmp[i]];
if (!st.size()) {printf("0\n");continue;}
if (!c) {printf("%lld\n",(ll)sum[1]*(sum[1]-1)>>1ll);continue;}
for (ri i(1);i<=cnt;p(i)) {
ri x=tmp[i];
ri k=std::lower_bound(tmp+i,tmp+cnt+1,x+c)-tmp;
if (k==cnt+1) break;
ans+=(ll)sum[k]*T[x];
}
printf("%lld\n",ans);
}
}
return 0;
}
}
int main() {return nanfeng::main();}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章