The country contains N cities numbered from 1 to N and M undirected roads connecting pairs of cities. There are some queries. Each query is represented by two numbers: L and R , meaning that all the cities whose number is between L and R(L and R are included) are safe, and other cities are not safe. We define city A can reach city B if and only if they are both safe and there exists a path from A to B that the cities on the path are all safe.
For each query, you need to figure out the number of pairs of cities that can reach each other under the condition given by the query.
Input
First line contains one number T which means the number of test cases.
For each test case, first line contains three numbers, above mentioned N , M and Q.
Next M lines, each line contains two integers: X, Y (X != Y) which means there is a road between city X and city Y (1 <= X,Y <= N).
Next Q lines, each line contains two numbers: L, R which indicates an query(1 <= L,R <= N, L <= R).
T <= 5, N , M <= 50000, Q <= 100000
Output
For each test case, output Q lines, each line contains the answer of the correspondent query.
分块
自己想了一个神头鬼脸的乱搞写法，炸胡过掉了
1 #include<bits/stdc++.h> 2 #define N 100005 3 #define Q 200005 4 #define S 233 5 using namespace std; 6 struct ee{int go,next;} e[N*2],qe[Q]; 7 int ljb[N],qljb[N*2]; 8 9 int f[N],s[N]; 10 int gf(int x){ 11 if (f[x]==x) return x; 12 f[x]=gf(f[x]); 13 return f[x]; 14 } 15 int gff(int x){return f[x]==x?x:gff(f[x]);} 16 17 struct aa{int x,y;} a[N*2]; 18 int l[Q],r[Q],st[N],ed[N],pr[Q],stid[S*2+10],stf[S*2+10],sts[S*2+10]; 19 int main(){ 20 int ttt;scanf("%d",&ttt); 21 for (;ttt--;){ 22 int n,m,q,an=0,cnt=0,qcnt=0;scanf("%d%d%d",&n,&m,&q); 23 for (int i=1;i<=n;i++) ljb[i]=0; 24 for (int i=1;i<=m;i++){ 25 int x,y;scanf("%d%d",&x,&y); 26 e[++cnt]=(ee){y,ljb[x]};ljb[x]=cnt; 27 e[++cnt]=(ee){x,ljb[y]};ljb[y]=cnt; 28 } 29 for (int i=1;i<=n;i++){ 30 st[i]=an+1; 31 for (int j=ljb[i];j;j=e[j].next) a[++an]=(aa){i,e[j].go}; 32 ed[i]=an; 33 } 34 for (int i=1;i<=an;i++) qljb[i]=0; 35 for (int i=1;i<=q;i++){ 36 scanf("%d%d",&l[i],&r[i]);pr[i]=-1; 37 qe[++qcnt]=(ee){i,qljb[ed[r[i]]]};qljb[ed[r[i]]]=qcnt; 38 } 39 for (int sta=S;sta<=an;sta+=S){ 40 for (int i=1;i<=n;i++) f[i]=i,s[i]=1; 41 int ans=0; 42 for (int j=sta+1;j<=an;j++){ 43 if (a[sta].x<=a[j].y&&a[j].y<=a[j].x){ 44 int fx=gf(a[j].x),fy=gf(a[j].y); 45 if (fx!=fy){ 46 ans-=1ll*s[fx]*(s[fx]-1)/2+1ll*s[fy]*(s[fy]-1)/2; 47 s[fy]+=s[fx];f[fx]=fy; 48 ans+=1ll*s[fy]*(s[fy]-1)/2; 49 } 50 } 51 for (int td=qljb[j];td;td=qe[td].next){ 52 int ll=st[l[qe[td].go]]; 53 if (ll<=sta-S||sta<ll) continue; 54 int tdans=ans,stn=0; 55 56 for (int k=ll;k<=sta;k++) if (l[qe[td].go]<=a[k].y&&a[k].y<=r[qe[td].go]){ 57 int fx=gff(a[k].x),fy=gff(a[k].y); 58 if (fx!=fy){ 59 if (s[fx]>s[fy]) swap(fx,fy); 60 stid[++stn]=fx;stf[stn]=f[fx];sts[stn]=s[fx]; 61 stid[++stn]=fy;stf[stn]=f[fy];sts[stn]=s[fy]; 62 tdans-=1ll*s[fx]*(s[fx]-1)/2+1ll*s[fy]*(s[fy]-1)/2; 63 s[fy]+=s[fx];f[fx]=fy; 64 tdans+=1ll*s[fy]*(s[fy]-1)/2; 65 } 66 } 67 pr[qe[td].go]=tdans; 68 for (int k=stn;k;k--) f[stid[k]]=stf[k],s[stid[k]]=sts[k]; 69 } 70 } 71 } 72 for (int qq=1;qq<=q;qq++) if (pr[qq]!=-1) printf("%d\n",pr[qq]); 73 else{ 74 int ans=0; 75 for (int i=l[qq];i<=r[qq];i++) f[i]=i,s[i]=1; 76 for (int i=l[qq];i<=r[qq];i++){ 77 for (int j=ljb[i];j;j=e[j].next) if (l[qq]<=e[j].go&&e[j].go<=r[qq]){ 78 int fx=gf(i),fy=gf(e[j].go); 79 if (fx!=fy){ 80 ans-=1ll*s[fx]*(s[fx]-1)/2+1ll*s[fy]*(s[fy]-1)/2; 81 s[fy]+=s[fx];f[fx]=fy; 82 ans+=1ll*s[fy]*(s[fy]-1)/2; 83 } 84 } 85 } 86 printf("%d\n",ans); 87 } 88 } 89 }