题目描述：

地理课上，老师给出了一个巨大的地图，由于世界日新月异，会有一些道路在某一时刻被删除，也会有一些道路在某一时刻被修建。这里的道路均为双向的。

老师认为，有一些城市被分在了一个连通块中可以相互到达，而有一些城市不能够相互到达。而他想知道，每个时刻所有连通块大小的乘积是多少？

wzy看到这个地图的时候就蒙了，还好那只上天的喵及时帮助了他。现在他把这个毒瘤的地图拿过来给你，想试试看你能不能求出来。由于答案可能很大，输出乘积mod109+7即可。

输入：

第一行两个数$\mathrm{n,m，表示有n个点，m个时刻。接下来m行每行三个数，要么是1uv，要么是2uv，分别表示添加一条无向边和删除一条无向边。}$

subtask1：30pts，n≤1,000,m≤2,000

subtask2：20pts，满足没有删除操作。

subtask3：50pts，n,m≤100,000保证没有重边自环，不会删除不存在的边。

算法标签：线段树

思路：

这题是离线算法，因为对于一条边有加入和删除的操作，所以一条边存在的时间是一段区间，把这段区间存入线段树，每次层层修改，关键是返回时要怎么回到这层的初始状态。首先是在并查集的时候不能路径压缩，然后每次记录下这层修改过的值，然后运用启发式合并，所以效率期望是log(nlog²n)。

以下代码：

#include
      
       #define il inline#define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int p=1e9+7,N=1000000;int n,m,fa[N];int res[N],ny[N],sz[N];struct data{
    int l,r,op;}t[N+5];struct node{
    int x,x1,num;};map
       
         ma;vector
        
          b[N<<2];vector
         
           v[N<<2];il int read(){
    int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}il int getfa(int x){
    if(fa[x]==x)return x;return getfa(fa[x]);}il int ksm(int a,int y){
    int b=1;while(y){
    if(y&1)b=(LL)b*(LL)a%p;a=(LL)a*(LL)a%p;y>>=1;}return b;}il void insert(int x,int l,int r,int ql,int qr,LL v){    if(ql<=l&&r<=qr){        b[x].push_back(v);        return;    }    int mid=(l+r)>>1;    if(ql<=mid)insert(x<<1,l,mid,ql,qr,v);    if(mid
          
           <<1|1,mid+1,r,ql,qr,v);}void work(int x,int l,int r,int sum){    if(l==r){        int tmp=sum;        for(int i=0;i
           
            =0;i--){ int kk=v[x][i].x;int ss=v[x][i].num; int k1=v[x][i].x1; fa[k1]=k1;sz[kk]=ss; } return; } int mid=(l+r)>>1;int tmp=sum; for(int i=0;i
            
             =0;i--){ int kk=v[x][i].x;int ss=v[x][i].num; int k1=v[x][i].x1; fa[k1]=k1;sz[kk]=ss; }}int main(){ n=read();m=read();ny[1]=1;for(int i=2;i<=n;i++)ny[i]=ksm(i,p-2); for(int i=1;i<=m;i++){ t[i].op=read(); int x=read(),y=read(); if(x>y)swap(x,y); t[i].l=x;t[i].r=y; LL kk=(LL)x*(LL)N+y; if(ma[kk]==0)ma[kk]=i; else{ insert(1,1,m,ma[kk],i-1,kk); ma[kk]=0; } } for(int i=1;i<=m;i++){ if(t[i].op==1){ int x=t[i].l,y=t[i].r; LL kk=(LL)x*(LL)N+y; if(ma[kk]>0){ insert(1,1,m,ma[kk],m,kk),ma[kk]=0; } } } for(int i=1;i<=n;i++)sz[i]=1,fa[i]=i; work(1,1,m,1); return 0;}
            
           
          
         
        
       
      

此代码跑了30s，慢的一b，仅供参考把