前置知识 https://www.cnblogs.com/Jackpei/p/12064564.html
那么这道题, 对于这种修改形式, 我们大致是要分块 or 套莫队.
然后我选择了写分块 \ 哭了
由于边表的信息是可以重复合并的, 那么类似 \(ST\) 表, 我们可以预处理出 \(f[t][i]\) 表示 加入边 \([i,i+2^t-1]\) 后的边表 (邻接矩阵), 然后散块暴力合并边表即可.
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #define R register int
- using namespace std;
- namespace Luitaryi {
- inline int g() { R x=0,f=1;
- register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
- do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
- } const int N=160,M=300010,T=300,B=31,D=5;
- const int K=M/T+10;
- #define u32 unsigned
- int n,m,q,num,L,lg[K],s[N+10],top;
- struct node {int u,v;}G[M];
- struct bitset {
- u32 v[5];
- inline void reset() {memset(v,0,20);}
- inline void set() {memset(v,0xff,20);}
- inline void set(int x) {v[x>>D]|=1u<<(x&B);}
- inline void flip(int x) {v[x>>D]^=1u<<(x&B);}
- inline bool test(int x) {return v[x>>D]>>(x&B)&1;}
- }vis,e[N],re[N],f[15][K][N],rf[15][K][N];
- inline void add(int i) {
- e[G[i].u].set(G[i].v);
- re[G[i].v].set(G[i].u);
- }
- inline void dfs0(int u) {
- vis.flip(u);
- for(R i=0;i<D;++i) while(20040109) {
- register u32 tmp=vis.v[i]&e[u].v[i];
- if(!tmp) break;
- dfs0(i<<D|__builtin_ctz(tmp));
- } s[++top]=u;
- }
- inline void dfs1(int u) {
- vis.flip(u),++num;
- for(R i=0;i<D;++i) while(20021204) {
- register u32 tmp=vis.v[i]&re[u].v[i];
- if(!tmp) break;
- dfs1(i<<D|__builtin_ctz(tmp));
- }
- }
- inline void main() {
- n=g(),m=g(),q=g();
- for(R i=1;i<=m;++i) G[i].u=g()-1,G[i].v=g()-1;
- L=m/T+(m%T!=0); for(R i=2;i<=L;++i) lg[i]=lg[i>>1]+1;
- for(R i=1,l,r;i<=L;++i) {
- l=(i-1)*T+1,r=min(i*T,m);
- for(;l<=r;++l)
- f[0][i][G[l].u].set(G[l].v),
- rf[0][i][G[l].v].set(G[l].u);
- }
- for(R t=1;t<10;++t) for(R i=1,lim=L-(1<<t)+1;i<=lim;++i)
- for(R j=0;j<n;++j) for(R k=0;k<D;++k)
- f[t][i][j].v[k]=f[t-1][i][j].v[k]|f[t-1][i+(1<<t-1)][j].v[k];
- for(R t=1;t<10;++t) for(R i=1,lim=L-(1<<t)+1;i<=lim;++i)
- for(R j=0;j<n;++j) for(R k=0;k<D;++k)
- rf[t][i][j].v[k]=rf[t-1][i][j].v[k]|rf[t-1][i+(1<<t-1)][j].v[k];
- while(q--) {
- R LL=g(),RR=g(); R l=(LL-1)/T+1,r=(RR-1)/T+1;
- for(R i=0;i<n;++i) e[i].reset(),re[i].reset();
- if(l==r) for(R i=LL;i<=RR;++i) add(i);
- else {
- for(R i=LL,lim=l*T;i<=lim;++i) add(i);
- for(R i=(r-1)*T+1;i<=RR;++i) add(i);
- ++l,--r;
- if(l<=r) { R t=lg[r-l+1]; R p=r-(1<<t)+1;
- for(R j=0;j<n;++j) for(R k=0;k<D;++k)
- e[j].v[k]|=f[t][l][j].v[k]|f[t][p][j].v[k];
- for(R j=0;j<n;++j) for(R k=0;k<D;++k)
- re[j].v[k]|=rf[t][l][j].v[k]|rf[t][p][j].v[k];
- }
- } R ans=0; top=0;
- vis.set(); for(R i=0;i<n;++i) if(vis.test(i)) dfs0(i);
- vis.set(); for(R i=n;i;--i) if(vis.test(s[i])) {
- num=0,dfs1(s[i]),ans+=num*(num-1)/2;
- } printf("%d\n",ans);
- }
- }
- } signed main() {Luitaryi::main(); return 0;}
- 2019.12.18
来源: http://www.bubuko.com/infodetail-3338657.html