题面：
题意：
有 n 个球员， m 个粉丝。
一个粉丝可能喜欢多个球员。
现在要从 n 个球员中选出一些球员来参加比赛，使得所有的粉丝都愿意观看这场比赛。
某个粉丝喜欢观看这场比赛的条件满足以下之一即可：
（1）粉丝 i 喜欢的球员 j 在这场比赛中。
（2）粉丝 x 喜欢观看球员 j 的比赛，粉丝 i,x 都喜欢观看球员 y 的比赛，那么粉丝 i 喜欢观看球员 j 的比赛。
给定 q 次喜欢关系的改变，每次询问至少选出多少球员，才能让所有粉丝都喜欢观看这场比赛。
如果不能满足让所有粉丝都喜欢观看这场比赛，输出-1。
题解：
如果把这个关系建成一个图的话。其实就是需要求n个球员的连通分量个数（因为条件（2），导致了喜欢关系可以传递）。
如果有球迷的度为0，答案就是-1。
否则答案就是（n个球员的连通分量个数）- (孤立球员个数)
所以只需要在加边和删边的时候，维护n个球员的连通分量个数。
x是球员，y是球迷。
x, y加边时候，如果他们本来不连通，而且y原来有边，连通分量减一。
x, y删边时候，如果删完他们变得不连通，而且y还有边，连通分量加一。
在离线的同时记录一下每一时刻球迷的度为0的个数和孤立球员的个数。
因为我们在统计到 i 的状态时，若有粉丝的度为0，那么答案为-1。也就是说若最终状态合法，那么粉丝一定在若干个连通块中，这些联通块中一定都有球员。所以我们只需要统计最终连通块的数量，那么（最终总连通块的数量-孤立球员个数）就是答案
线段树上维护按秩合并可撤销并查集，时间复杂度 O(nlog2n)
LCT维护删边时间最大的生成树，时间复杂度 O(nlogn)
代码（1）：线段树上维护按秩合并可撤销并查集
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=400100;
const int maxp=800100;
const int maxm=1000100;
const int up=200000;
int n,m,q;
int f[maxn],d[maxn],top=0;
pair<int,int>st[maxn];
int cntp;
int di[maxn],cntq,cntf;
struct tree
{
int l,r;
vector<pair<int,int> >vc;
}t[maxn<<2];
int ans[maxn];
map<pair<int,int>,int>mp;
int fi(int x)
{
if(f[x]==x) return x;
else return fi(f[x]);
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
t[cnt].vc.clear();
if(l==r) return ;
build(l,tmid,lc);
build(tmid+1,r,rc);
}
void change(int l,int r,int cnt,pair<int,int> val)
{
if(l>r) return ;
if(l<=t[cnt].l&&t[cnt].r<=r)
{
t[cnt].vc.pb(val);
return ;
}
if(t[lc].r>=l) change(l,r,lc,val);
if(t[rc].l<=r) change(l,r,rc,val);
}
void _merge(int x,int y)
{
int xx=fi(x),yy=fi(y);
if(xx==yy) return ;
cntp--;
if(d[xx]>d[yy]) swap(xx,yy);
st[++top]=pr(xx,d[xx]==d[yy]);
f[xx]=yy;
d[yy]+=(d[xx]==d[yy]);
}
void dfs(int l,int r,int cnt)
{
int now=top;
for(int i=0;i<t[cnt].vc.size();i++)
_merge(t[cnt].vc[i].first,t[cnt].vc[i].second);
if(l==r)
{
if(ans[l]>0) ans[l]=-1;
else ans[l]+=cntp;
}
else
{
dfs(l,tmid,lc);
dfs(tmid+1,r,rc);
}
while(top>now)
{
d[f[st[top].first]]-=st[top].second;
f[st[top].first]=st[top].first;
top--,cntp++;
}
}
int main(void)
{
scanf("%d%d%d",&n,&m,&q);
cntp=n+m,cntq=n,cntf=m;
for(int i=1;i<=n+m;i++)
f[i]=i,d[i]=1;
build(1,q,1);
int k,x,y;
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
scanf("%d",&x);
mp[pr(x+n,i)]=1;
if(++di[i]==1) cntq--;
if(++di[x+n]==1) cntf--;
}
}
for(int i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
if(mp.count(pr(x+n,y)))
{
int pos=mp[pr(x+n,y)];
mp.erase(pr(x+n,y));
change(pos,i-1,1,pr(x+n,y));
if(--di[y]==0) cntq++;
if(--di[x+n]==0) cntf++;
}
else
{
mp[pr(x+n,y)]=i;
if(++di[y]==1) cntq--;
if(++di[x+n]==1) cntf--;
}
if(cntf) ans[i]=1;
else ans[i]=-cntq;
}
for(auto p : mp)
change(p.second,q,1,pr(p.first.first,p.first.second));
dfs(1,q,1);
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
代码（2）LCT维护删边时间最大的生成树
人丑常数大，比两个log的线段树分治跑的还慢。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1100100;
const int maxp=800100;
const int maxm=1000100;
const int up=200000;
struct tree
{
int son[2];
int fa,minn,rev;
}t[maxn];
int st[maxn];
int deltime[maxn],isdel[maxn];
int n,m,q;
int idin[maxn];
int cnt,cntp,cntq,cntf;
struct node
{
int x,y;
int begintime,endtime;
int id;
node(){}
node(int a,int b,int c,int d,int e)
{
x=a,y=b,begintime=c,endtime=d,id=e;
}
}in[maxn],out[maxn];
bool cmpin(const node &a,const node &b)
{
return a.begintime<b.begintime;
}
bool cmpout(const node &a,const node &b)
{
return a.endtime<b.endtime;
}
map<pair<int,int>,int>mp;
int ans[maxn],di[maxn];
void pushup(int x)
{
t[x].minn=x;
if(t[x].son[0])
t[x].minn=deltime[t[x].minn]<deltime[t[t[x].son[0]].minn]?t[x].minn:t[t[x].son[0]].minn;
if(t[x].son[1])
t[x].minn=deltime[t[x].minn]<deltime[t[t[x].son[1]].minn]?t[x].minn:t[t[x].son[1]].minn;
}
void _reverse(int x)
{
if(!x) return ;
swap(t[x].son[0],t[x].son[1]);
t[x].rev^=1;
}
void pushdown(int x)
{
if(!x) return ;
if(t[x].rev)
{
_reverse(t[x].son[0]);
_reverse(t[x].son[1]);
t[x].rev=0;
}
}
bool notroot(int x)
{
return t[t[x].fa].son[0]==x||t[t[x].fa].son[1]==x;
}
int get_son(int x)
{
return x==t[t[x].fa].son[1];
}
void rot(int x)
{
int y=t[x].fa,z=t[y].fa;
int k=get_son(x),w=t[x].son[k^1];
t[y].son[k]=w,t[w].fa=y;
if(notroot(y))t[z].son[get_son(y)]=x;
t[x].fa=z;
t[x].son[k^1]=y,t[y].fa=x;
pushup(y),pushup(x);
}
void splay(int x)
{
int top=0;
st[++top]=x;
for(int pos=x;notroot(pos);pos=t[pos].fa) st[++top]=t[pos].fa;
while(top) pushdown(st[top--]);
while(notroot(x))
{
int y=t[x].fa;
int z=t[y].fa;
if(notroot(y))
if(get_son(x)==get_son(y)) rot(y);
else rot(x);
rot(x);
}
}
void access(int x)
{
for(int y=0;x;y=x,x=t[x].fa)
{
splay(x);
t[x].son[1]=y;
pushup(x);
}
}
void makeroot(int x)
{
access(x);
splay(x);
_reverse(x);
}
int findroot(int x)
{
access(x);
splay(x);
while(t[x].son[0]) pushdown(x),x=t[x].son[0];
splay(x);
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
bool link(int x,int y)
{
makeroot(x);
if(findroot(y)==x) return false;
t[x].fa=y;
return true;
}
bool cut(int x,int y)
{
makeroot(x);
if(findroot(y)!=x||t[y].fa!=x||t[y].son[0]) return false;
t[y].fa=t[x].son[1]=0;
pushup(x);
return true;
}
bool connected(int x,int y)
{
x=findroot(x);
y=findroot(y);
return x==y;
}
//这好像就是 split 函数
void ***(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void _insert(int p)
{
deltime[in[p].id]=in[p].endtime;
t[in[p].id].minn=in[p].id;
int x=in[p].x,y=in[p].y,id=in[p].id;
if(connected(x,y))
{
***(x,y);
if(deltime[t[y].minn]>deltime[id])
isdel[id]=1;
else
{
isdel[t[y].minn]=1;
int de=t[y].minn;
cut(in[idin[de]].x,de);
cut(in[idin[de]].y,de);
link(x,id);
link(y,id);
}
}
else
{
link(in[p].x,in[p].id);
link(in[p].y,in[p].id);
cntp--;
}
}
void del(int p)
{
if(isdel[out[p].id])
isdel[out[p].id]=0;
else
{
cut(out[p].x,out[p].id);
cut(out[p].y,out[p].id);
cntp++;
}
}
int main(void)
{
scanf("%d%d%d",&n,&m,&q);
cntp=n+m,cntq=n,cntf=m;
for(int i=1;i<=n+m;i++)
deltime[i]=inf;
int k,x,y;
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
scanf("%d",&x);
mp[pr(x+n,i)]=1;
if(++di[i]==1) cntq--;
if(++di[x+n]==1) cntf--;
}
}
for(int i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
if(mp.count(pr(x+n,y)))
{
int pos=mp[pr(x+n,y)];
mp.erase(pr(x+n,y));
if(--di[y]==0) cntq++;
if(--di[x+n]==0) cntf++;
++cnt;
in[cnt]=node(x+n,y,pos,i,cnt+n+m);
out[cnt]=in[cnt];
}
else
{
mp[pr(x+n,y)]=i;
if(++di[y]==1) cntq--;
if(++di[x+n]==1) cntf--;
}
if(cntf) ans[i]=1;
else ans[i]=-cntq;
}
for(auto p : mp)
{
++cnt;
in[cnt]=node(p.first.first,p.first.second,p.second,q+1,cnt+n+m);
out[cnt]=in[cnt];
}
sort(in+1,in+cnt+1,cmpin);
sort(out+1,out+cnt+1,cmpout);
for(int i=1;i<=cnt;i++)
idin[in[i].id]=i;
int cntin=1,cntout=1;
for(int i=1;i<=q;i++)
{
while(cntin<=cnt&&in[cntin].begintime<=i)
_insert(cntin++);
while(cntout<=cnt&&out[cntout].endtime<=i)
del(cntout++);
if(ans[i]==1) printf("-1\n");
else printf("%d\n",ans[i]+cntp);
}
return 0;
}
京公网安备 11010502036488号