使用回滚莫队可以有效降低思维含量。
对于回滚莫队和可撤销并查集,本文不再赘述。
假设当前询问是 \([L,R]\),目前加入了 \([l,r]\) 的所有点和边。将 \(r\) 增加 \(1\) 时,连边 \((r+1,v\in[l,r])\)。
然后需要处理左边的散块。对于所有零散的 \(l\),连边 \((l,v\in[L,R])\)。上述两种加边能维护 \([L,R]\) 的并查集。并查集合并的同时修改答案。
// Title: Timofey and our friends animals
// Source: CF763E
// Author: Jerrywang
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=100010;
using namespace std;
struct query
{
int l, r, i;
} q[N]; int n, m, k, len, b[N], ans[N];
vector<query> vec[N];
vector<int> g[N];
bool cmp(query x, query y)
{
if(b[x.l]!=b[y.l]) return b[x.l]<b[y.l];
return x.r<y.r;
}
struct op {int u, rt, v, sz;} s[N]; int top=0;
int rt[N], sz[N];
void init()
{
top=0; rep(i, 1, n) rt[i]=i, sz[i]=1;
}
int root(int u) {return u==rt[u]?u:root(rt[u]);}
int merge(int u, int v) // 合并连通块则返回1
{
u=root(u), v=root(v);
if(u==v) return 0;
if(sz[u]>sz[v]) swap(u, v);
s[++top]={u, rt[u], v, sz[v]};
rt[u]=v, sz[v]+=sz[u];
return 1;
}
void goback(int tp) // 撤销
{
while(top>tp)
rt[s[top].u]=s[top].rt, sz[s[top].v]=s[top].sz, top--;
}
void ins(int &res, int u, int l, int r) // 加点
{
res++;
for(int v:g[u]) if(l<=v && v<=r)
res-=merge(u, v);
}
int main()
{
scanf("%d%d%d", &n, &k, &m); len=sqrt(n);
rep(i, 1, n) b[i]=(i-1)/len+1;
rep(i, 1, m)
{
int u, v; scanf("%d%d", &u, &v);
g[u].push_back(v), g[v].push_back(u);
}
scanf("%d", &m);
rep(i, 1, m) scanf("%d%d", &q[i].l, &q[i].r), q[i].i=i;
sort(q+1, q+m+1, cmp);
rep(i, 1, m) vec[b[q[i].l]].push_back(q[i]);
rep(k, 1, b[n])
{
int R=min(n, k*len); init();
int r=R, res=0, res1, _top;
for(auto t:vec[k])
{
if(t.r<=R)
{
res1=0, _top=top;
rep(l, t.l, t.r) ins(res1, l, t.l, t.r);
ans[t.i]=res1, goback(_top);
continue;
}
while(r<t.r) ins(res, ++r, R+1, r);
res1=res, _top=top;
rep(l, t.l, R) ins(res1, l, t.l, r);
ans[t.i]=res1, goback(_top);
}
}
rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}
标签:rt,sz,int,top,CF763E,Timofey,our,define
From: https://www.cnblogs.com/jerrywang2009/p/18064347