fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 500500
  7. #define fi first
  8. #define se second
  9. #define int long long
  10.  
  11.  
  12. using namespace std;
  13.  
  14. vector<pair<int,int>> seg[4*maxn];
  15. int val[maxn];
  16. pair<int,int> edge[maxn];
  17.  
  18. struct node {
  19.   int u,v,sz_u,numedge_u,Min_u,sum_u,ans;
  20. };
  21.  
  22. int m;
  23.  
  24. struct DSU {
  25.    vector<int> par,sz,numedge,Min,sum;
  26.    vector<node> st;
  27.    int ans=0;
  28.    int n;
  29.    int is_bipar;
  30.  
  31.    DSU(int _n=0){
  32.       n=_n;
  33.       par.assign(n+5,0);
  34.       sz.assign(n+5,1);
  35.       numedge.assign(n+5,0);
  36.       Min.assign(n+5,0);
  37.       sum.assign(n+5,0);
  38.  
  39.  
  40.       for(int i=1;i<=n;i++) {
  41.           par[i]=i;
  42.           Min[i]=val[i];
  43.           sum[i]=val[i];
  44.       }
  45.       ans=0;
  46.    }
  47.  
  48.    int find_par(int u){
  49.       while(u!=par[u]){
  50.          u=par[u];
  51.       }
  52.       return u;
  53.    }
  54.  
  55.    int get(int r) {
  56.       if(numedge[r] < sz[r]) return sum[r] - Min[r];
  57.       return sum[r];
  58.    }
  59.  
  60.    void join(int u,int v){
  61.       int ru =find_par(u);
  62.       int rv =find_par(v);
  63.  
  64.       if(ru==rv){
  65.          st.push_back({ru,-1,sz[ru],numedge[ru],Min[ru],sum[ru],ans});
  66.          ans -= get(ru);
  67.          numedge[ru]++;
  68.          ans += get(ru);
  69.          return;
  70.       }
  71.  
  72.       if(sz[ru]<sz[rv]){
  73.          swap(ru,rv);
  74.       }
  75.  
  76.       st.push_back({ru,rv,sz[ru],numedge[ru],Min[ru],sum[ru],ans});
  77.       ans -= get(ru);
  78.       ans -= get(rv);
  79.       par[rv]=ru;
  80.       sz[ru]+=sz[rv];
  81.       numedge[ru] += numedge[rv]+1;
  82.       Min[ru] = min(Min[ru],Min[rv]);
  83.       sum[ru] += sum[rv];
  84.  
  85.       ans += get(ru);
  86.    }
  87.  
  88.    void rollback(int Time){
  89.       while((int)st.size()>Time){
  90.          auto [u,v,sz_u,numedge_u,Min_ru,Sum_ru,old_ans]=st.back();
  91.          st.pop_back();
  92.  
  93.          ans = old_ans;
  94.  
  95.          if(v==-1) {
  96.              numedge[u] = numedge_u;
  97.          } else {
  98.              par[v]=v;
  99.              sz[u]=sz_u;
  100.              numedge[u] = numedge_u;
  101.              Min[u] = Min_ru;
  102.              sum[u] = Sum_ru;
  103.          }
  104.       }
  105.    }
  106. };
  107.  
  108. void update(int id,int l,int r,int u,int v,pair<int,int> edge){
  109.    if(l>r || u>v || l>v || r<u) return ;
  110.    if(u<=l && r<=v){
  111.       seg[id].push_back(edge);
  112.       return ;
  113.    }
  114.    int m=(l+r)/2;
  115.    update(id*2,l,m,u,v,edge);
  116.    update(id*2+1,m+1,r,u,v,edge);
  117. }
  118.  
  119. struct Query {
  120.    int opt;
  121.    int u, v;
  122. };
  123.  
  124. DSU dsu ;
  125. vector<int> ans;
  126. Query que[maxn];
  127. int n,k;
  128.  
  129. void dfs(int id, int l, int r) {
  130.     int snap = dsu.st.size();
  131.     for(auto [u,v] : seg[id]) dsu.join(u,v);
  132.     if(l == r) {
  133.         if(l>1) ans.push_back(dsu.ans);
  134.     }
  135.     else {
  136.         int mid = (l + r) >> 1;
  137.         dfs(id << 1, l, mid);
  138.         dfs(id << 1 | 1, mid + 1, r);
  139.     }
  140.     dsu.rollback(snap);
  141. }
  142.  
  143. map<pair<int,int>,int> start;
  144.  
  145. signed main()
  146. {
  147.     itachi
  148.     cin>>n>>m>>k;
  149.     for(int i=1;i<=n;i++) cin>>val[i];
  150.     for(int i=1;i<=m;i++){
  151.         int u,v;
  152.         cin>>u>>v;
  153.         if(u>v) swap(u,v);
  154.         edge[i]={u,v};
  155.         start[{u,v}]=1;
  156.     }
  157.     dsu = DSU(n);
  158.     int idans=1;
  159.     for(int i = 2; i <= k+1; i++) {
  160.         int c,id;
  161.         cin>>c>>id;
  162.         int u = edge[id].fi;
  163.         int v = edge[id].se;
  164.         if(u > v) swap(u, v);
  165.         if(c == 2) {
  166.             start[{u, v}] = i ;
  167.         }
  168.         else {
  169.             int L = start[{u, v}];
  170.             start.erase({u, v});
  171.  
  172.             update(1, 1, k+1 ,L, i-1 ,{u, v});
  173.             start[{u,v}] = 0;
  174.         }
  175.     }
  176.  
  177.     for(auto &it : start) {
  178.         auto [e, L] = it;
  179.        if(start[e] > 0 ) update(1, 1, k+1 ,L, k+1,{e.fi, e.se});
  180.     }
  181.  
  182.     dfs(1, 1, k+1 );
  183.     for(int x : ans)
  184.         cout << x << '\n';
  185.     return 0;
  186. }
  187.  
Success #stdin #stdout 0.02s 53032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NdGkDx
language:
C++14 (gcc 8.3)
created:
13 hours 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!