fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int N=6e5+5;
  5. int n,m,q,ans[N];vector<int>adj[N];vector<array<int,2>>ed;vector<vector<int>>seg,add(N),cut(N);
  6. struct dsu
  7. {
  8.     int parent[N],group[N],res;stack<array<int,4>>st;
  9.     dsu()
  10.     {
  11.         for(int i=0;i<N;i++)
  12.         {
  13.             parent[i]=i;
  14.             group[i]=1;
  15.         }
  16.     }
  17.     void set(int x){
  18.         res=x;
  19.     }
  20.     int find(int i)
  21.     {
  22.         if(parent[i]==i)
  23.         {
  24.             return i;
  25.         }
  26.         return find(parent[i]);
  27.     }
  28.     bool samegroup(int x,int y)
  29.     {
  30.         return find(x)==find(y);
  31.     }
  32.     void merge(int x,int y)
  33.     {
  34.         int leader1=find(x);
  35.         int leader2=find(y);
  36.         if(group[leader1]>group[leader2])
  37.         {
  38.             swap(leader1,leader2);
  39.         }
  40.         array<int,4>p={0,0,0,0};
  41.         p[0]=leader2,p[1]=group[leader2];
  42.         p[2]=leader1,p[3]=parent[leader1];
  43.         st.push(p);
  44.         if(leader1==leader2)
  45.         {
  46.             return;
  47.         }
  48.         res--;
  49.         group[leader2]+=group[leader1];
  50.         parent[leader1]=leader2;
  51.     }
  52.     int getsize(int x)
  53.     {
  54.         return group[find(x)];
  55.     }
  56.     int getans()
  57.     {
  58.         return res;
  59.     }
  60.     void rollBack()
  61.     {
  62.         if(st.empty())return;
  63.         auto &[a,b,c,d]=st.top();
  64.         st.pop();
  65.         group[a]=b;
  66.         parent[c]=d;
  67.         res+=!samegroup(a,c);
  68.     }
  69. }d;
  70. void update(int l,int r,int node,int lx,int rx,int idx)
  71. {
  72.     if(r<lx||l>rx) return;
  73.     if(l>=lx&&r<=rx)
  74.     {
  75.         seg[node].push_back(idx);
  76.         return;
  77.     }
  78.     int mid=l+r>>1;
  79.     update(l,mid,2*node+1,lx,rx,idx);
  80.     update(mid+1,r,2*node+2,lx,rx,idx);
  81. }
  82. void build(int l,int r,int node)
  83. {
  84.     for(auto it:seg[node])
  85.     {
  86.         d.merge(ed[it][0],ed[it][1]);
  87.     }
  88.     if(l==r)
  89.     {
  90.         ans[l]=d.getans();
  91.         for(auto it:seg[node]) d.rollBack();
  92.         return;
  93.     }
  94.     int mid=l+r>>1;
  95.     build(l,mid,2*node+1);
  96.     build(mid+1,r,2*node+2);
  97.     for(auto it:seg[node]) d.rollBack();
  98. }
  99. signed main()
  100. {
  101.     freopen("connect.in","r",stdin);
  102.     freopen("connect.out","w",stdout);
  103.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  104.     cin>>n>>q;
  105.     map<array<int,2>,int>mp;
  106.     ed.push_back({0,0});
  107.     vector<int>queries;
  108.     for(int i=1;i<=q;i++)
  109.     {
  110.         char op;cin>>op;
  111.         if(op=='?') queries.push_back(i);
  112.         else
  113.         {
  114.             int a,b;cin>>a>>b;
  115.             if(b>a)swap(a,b);
  116.             if(op=='+')
  117.             {
  118.                 if(mp.find({a,b})==mp.end()) ed.push_back({a,b}),mp[ed.back()]=ed.size()-1;
  119.                 int idx=mp[{a,b}];
  120.                 add[idx].push_back(i);
  121.             }
  122.             else
  123.             {
  124.                 int idx=mp[{a,b}];
  125.                 cut[idx].push_back(i);
  126.             }
  127.         }
  128.     }
  129.     for(int i=1;i<ed.size();i++) cut[i].push_back(q+1);
  130.     int sz=1;
  131.     while(sz<=q+5)sz<<=1;
  132.     seg=vector<vector<int>>(sz<<1);
  133.     for(int i=1;i<ed.size();i++)
  134.     {
  135.         for(auto it:add[i])
  136.         {
  137.             update(0,sz-1,0,it,*lower_bound(cut[i].begin(),cut[i].end(),it)-1,i);
  138.         }
  139.     }
  140.     d.set(n);
  141.     build(0,sz-1,0);
  142.     for(auto it:queries) cout<<ans[it]<<'\n';
  143.     return 0;
  144. }
Success #stdin #stdout 0.02s 50256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/imLqUf
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!