题意：
思路：
很巧妙的一个题。
如果不断开的话就是简单的并查集计算连通块的问题。
先来考虑一下暴力的做法，去掉[l,r]之间的边后，直接暴力将[1,l-1]和[r+1,m]的边连接起来，计算出连通块的个数，大概就是这样：
while(k--){ int l,r; scanf("%d%d",&l,&r); for(int i=1;i<=n;i++) root[i]=i; int res=n; for(int i=1;i<l;i++){ int u=a[i],v=b[i]; u=Find(u),v=Find(v); if(u!=v) root[u]=v,res--; } for(int i=r+1;i<=m;i++){ int u=a[i],v=b[i]; u=Find(u),v=Find(v); if(u!=v) root[u]=v,res--; } printf("%d\n",res); }
显然很难卡过去这道题。因为每个区间只是在每次询问后不计这个区间的边，也就相当于每次询问都是相互独立的，即任何一段区间的连通块个数和连边情况都是不会变的。这样就可以用前后缀和来维护，每次询问时只需要将[1,l-1]和[r+1,m]区间连接计算连通块个数即可。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } const ll inf = 0x3f3f3f3f3f3f3f3f; const int maxn=2e4+10,mod=1e8; const double PI = atan(1.0)*4; const double eps=1e-6; int n,m,x[maxn],y[maxn]; struct node{ int root[510],cnt; void init(){ for(int i=1;i<=500;i++) root[i]=i; cnt=0; } int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } void Union(int x,int y){ x=Find(x),y=Find(y); if(x!=y) root[x]=y,cnt++; } }l[maxn],r[maxn]; int main(){ n=read(),m=read(); for(int i=1;i<=m;i++) x[i]=read(),y[i]=read(); l[0].init(); for(int i=1;i<=m;i++){ l[i]=l[i-1]; l[i].Union(x[i],y[i]); } r[m+1].init(); for(int i=m;i;i--){ r[i]=r[i+1]; r[i].Union(x[i],y[i]); } int k=read(); while(k--){ int ll=read(),rr=read(); node res=l[ll-1]; for(int i=1;i<=n;i++) res.Union(i,r[rr+1].Find(i)); cout<<n-res.cnt<<endl; } return 0; }
