题解：

cf765f

cf671e

bzoj4184

bzoj4552

线段树分治裸题

还是介绍一下线段树分治

这个东西其实挺简单但也挺有用的

可以把删除+插入操作变成只有插入（倒着就是删除）

像这一道题，我们对时间点建立线段树

对一段区间共同有的元素依次加入到线段树中（开个队列维护一下）

发现这样是只有nlogn个点

另外这个标记显然是可以标记永久化的

apio t1是这个所以就学习了一下

为了练习一下可持久化并查集于是我就写了

然后主席树造成了它一定会mle。。nlognlog（nlogn）

其实只用带撤销的并查集就可以了

#include 
     
      using namespace std;const int N=4e7+10;const int N2=3e5+10;struct re{    int x,y;}a[N2];int cnt,now,n,m,k;int ls[N],rs[N],data[N];int ph[N2*4],pt[N2*4],count2[N2],f[N2];bool ft[N2];vector
      
        ve[N2*4];#define mid (ph[x]+pt[x])/2void change(int last,int &now,int h,int t,int goal,int goal2){    now=++cnt;    if (h==t)    {       data[now]=goal2;      return;  }    ls[now]=ls[last];    rs[now]=rs[last];    int mid2=(h+t)/2;    if (goal<=mid2) change(ls[last],ls[now],h,mid2,goal,goal2);    else change(rs[last],rs[now],mid2+1,t,goal,goal2);}int query(int x,int h,int t,int goal){    if (h==t) return(data[x]);    int mid2=(h+t)/2;    if (goal<=mid2) return(query(ls[x],h,mid2,goal));    else return(query(rs[x],mid2+1,t,goal));}void build(int x,int h,int t){    ph[x]=h; pt[x]=t;    if (h==t) return;    build(x*2,h,mid); build(x*2+1,mid+1,t);}void insert(int x,int h,int t,int goal){    if (h<=ph[x]&&pt[x]<=t)    {       ve[x].push_back(goal);      return;  }  if (h<=mid) insert(x*2,h,t,goal);  if (mid
       
         s;    int now1=now;    int len=ve[x].size();    for (int i=0;i
        
         count2[x22]) swap(x11,x22);            change(now,now,1,N,x11,x22);            s.push(re{x22,count2[x22]});            count2[x22]+=count2[x11];            ans++;        }    }    if (h==t)    {        if (ans==n-1) ft[h]=1; else ft[h]=0;    } else    {      dfs(x*2,h,(h+t)/2,ans);         dfs(x*2+1,(h+t)/2+1,t,ans);  }  while (!s.empty())  {      re x=s.top(); s.pop();    count2[x.x]=x.y;  }  now=now1;}int main(){    freopen("3237.in","r",stdin);    freopen("3237.out","w",stdout);    cin>>n>>m;    for (int i=1;i<=m;i++)    {        cin>>a[i].x>>a[i].y;    }    cin>>k;    for (int i=1;i<=n;i++) f[i]=1;    for (int i=1;i<=n;i++)    {      change(now,now,1,N,i,i);      count2[i]=1;  }  build(1,1,k);    for (int i=1;i<=k;i++)    {        int nown,x;        cin>>nown;        for (int j=1;j<=nown;j++)        {          cin>>x;          if (i-1>=f[x])          {            insert(1,f[x],i-1,x);          }          f[x]=i+1;      }    }    for (int i=1;i<=m;i++)      if (f[i]<=k)          insert(1,f[i],k,i);    dfs(1,1,k,0);    for (int i=1;i<=k;i++)      if (ft[i]==1) cout<<"Connected"<
        
       
      
     

 这个是正确的

#include 
     
      using namespace std;const int N=4e7+10;const int N2=3e5+10;#define rint register intstruct re{    int x,y,z;}a[N2];char ss[1<<24],*A=ss,*B=ss;inline char gc(){
   return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;}template
      
       void read(T&x){    rint f=1,c;while(c=gc(),c<48||57
       

ve[N2*4];#define mid (ph[x]+pt[x])/2void build(int x,int h,int t){ ph[x]=h; pt[x]=t; if (h==t) return; build(x*2,h,mid); build(x*2+1,mid+1,t);}void insert(int x,int h,int t,int goal){ if (h<=ph[x]&&pt[x]<=t) { ve[x].push_back(goal); return; } if (h<=mid) insert(x*2,h,t,goal); if (mid

s; int now1=now; int len=ve[x].size(); for (int i=0;i

count2[x22]) swap(x11,x22); fa[x11]=x22; s.push(re{x22,count2[x22],x11}); count2[x22]+=count2[x11]; ans++; } } if (h==t) { if (ans==n-1) ft[h]=1; else ft[h]=0; } else { dfs(x*2,h,(h+t)/2,ans); dfs(x*2+1,(h+t)/2+1,t,ans); } while (!s.empty()) { re x=s.top(); s.pop(); count2[x.x]=x.y; fa[x.z]=x.z; } now=now1;}int main(){ freopen("3237.in","r",stdin); freopen("3237.out","w",stdout); read(n); read(m); for (int i=1;i<=m;i++) { read(a[i].x); read(a[i].y); } read(k); for (int i=1;i<=n;i++) f[i]=1; for (int i=1;i<=n;i++) { fa[i]=i; count2[i]=1; } build(1,1,k); for (int i=1;i<=k;i++) { int nown,x; read(nown); for (int j=1;j<=nown;j++) { read(x); if (i-1>=f[x]) { insert(1,f[x],i-1,x); } f[x]=i+1; } } for (int i=1;i<=m;i++) if (f[i]<=k) insert(1,f[i],k,i); dfs(1,1,k,0); for (int i=1;i<=k;i++) if (ft[i]==1) puts("Connected"); else puts("Disconnected"); return 0;}