fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. struct Rec{
  7.     int type;
  8.     int ru, rv;
  9.     int prev_sz;
  10.     ll prev_sum;
  11.     ll prev_min;
  12.     int prev_edges;
  13.     ll prev_total;
  14. };
  15.  
  16. int n, k, Qn;
  17. vector<ll> cval;
  18. vector<int> U, V;
  19.  
  20. vector<vector<int>> seg;
  21. vector<int> qt, qx;
  22.  
  23. vector<int> parent_, sz_, edges_;
  24. vector<ll> sum_, mn_;
  25. ll total_ans = 0;
  26. vector<Rec> stck;
  27.  
  28. int find_root(int x){
  29.     while(parent_[x]!=x) x=parent_[x];
  30.     return x;
  31. }
  32.  
  33. ll contrib(int r){
  34.     return sum_[r] - ((edges_[r] < sz_[r]) ? mn_[r] : 0LL);
  35. }
  36.  
  37. void add_edge_union(int a,int b){
  38.     int ra=find_root(a), rb=find_root(b);
  39.     if(ra==rb){
  40.         Rec rec;
  41.         rec.type=0; rec.ru=ra; rec.prev_edges=edges_[ra]; rec.prev_total=total_ans;
  42.         total_ans -= contrib(ra);
  43.         edges_[ra] += 1;
  44.         total_ans += contrib(ra);
  45.         stck.push_back(rec);
  46.         return;
  47.     }
  48.     if(sz_[ra] < sz_[rb]) swap(ra,rb);
  49.     Rec rec;
  50.     rec.type=1; rec.ru=ra; rec.rv=rb;
  51.     rec.prev_sz=sz_[ra]; rec.prev_sum=sum_[ra]; rec.prev_min=mn_[ra]; rec.prev_edges=edges_[ra];
  52.     rec.prev_total=total_ans;
  53.     total_ans -= contrib(ra);
  54.     total_ans -= contrib(rb);
  55.     parent_[rb]=ra;
  56.     sz_[ra] += sz_[rb];
  57.     sum_[ra] += sum_[rb];
  58.     mn_[ra] = min(mn_[ra], mn_[rb]);
  59.     edges_[ra] += edges_[rb] + 1;
  60.     total_ans += contrib(ra);
  61.     stck.push_back(rec);
  62. }
  63.  
  64. void rollback(int snap){
  65.     while((int)stck.size() > snap){
  66.         Rec rec = stck.back(); stck.pop_back();
  67.         total_ans = rec.prev_total;
  68.         if(rec.type==0){
  69.             edges_[rec.ru] = rec.prev_edges;
  70.         }else{
  71.             parent_[rec.rv]=rec.rv;
  72.             sz_[rec.ru]=rec.prev_sz;
  73.             sum_[rec.ru]=rec.prev_sum;
  74.             mn_[rec.ru]=rec.prev_min;
  75.             edges_[rec.ru]=rec.prev_edges;
  76.         }
  77.     }
  78. }
  79.  
  80. void add_interval(int node,int l,int r,int ql,int qr,int id){
  81.     if(qr<=l || r<=ql) return;
  82.     if(ql<=l && r<=qr){ seg[node].push_back(id); return; }
  83.     int m=(l+r)>>1;
  84.     add_interval(node<<1,l,m,ql,qr,id);
  85.     add_interval(node<<1|1,m,r,ql,qr,id);
  86. }
  87.  
  88. vector<ll> outv;
  89.  
  90. void dfs_seg(int node,int l,int r){
  91.     int snap = stck.size();
  92.     for(int id: seg[node]) add_edge_union(U[id], V[id]);
  93.     if(l+1==r){
  94.         if(l>=1 && l<=Qn) outv[l]=total_ans;
  95.     }else{
  96.         int m=(l+r)>>1;
  97.         dfs_seg(node<<1,l,m);
  98.         dfs_seg(node<<1|1,m,r);
  99.     }
  100.     rollback(snap);
  101. }
  102.  
  103. int main(){
  104.     ios::sync_with_stdio(false);
  105.     cin.tie(nullptr);
  106.     cin>>n>>k>>Qn;
  107.     cval.assign(n+1,0);
  108.     for(int i=1;i<=n;i++) cin>>cval[i];
  109.     U.assign(k+1,0); V.assign(k+1,0);
  110.     for(int i=1;i<=k;i++) cin>>U[i]>>V[i];
  111.     qt.resize(Qn+1); qx.resize(Qn+1);
  112.     for(int i=1;i<=Qn;i++){ cin>>qt[i]>>qx[i]; }
  113.     vector<int> on(k+1,1), last(k+1,1);
  114.     vector<vector<pair<int,int>>> intervals(k+1);
  115.     for(int i=1;i<=Qn;i++){
  116.         int t=qt[i], p=qx[i];
  117.         if(t==1){
  118.             if(on[p]){ intervals[p].push_back({last[p],i}); on[p]=0; }
  119.         }else{
  120.             if(!on[p]){ last[p]=i; on[p]=1; }
  121.         }
  122.     }
  123.     for(int e=1;e<=k;e++){
  124.         if(on[e]) intervals[e].push_back({last[e],Qn+1});
  125.     }
  126.     seg.assign(4*(Qn+2),{});
  127.     for(int e=1;e<=k;e++){
  128.         for(auto iv: intervals[e]){
  129.             if(iv.first<iv.second) add_interval(1,1,Qn+1,iv.first,iv.second,e);
  130.         }
  131.     }
  132.     parent_.resize(n+1);
  133.     sz_.resize(n+1,1);
  134.     sum_.resize(n+1);
  135.     mn_.resize(n+1);
  136.     edges_.resize(n+1,0);
  137.     for(int i=1;i<=n;i++){
  138.         parent_[i]=i;
  139.         sum_[i]=cval[i];
  140.         mn_[i]=cval[i];
  141.     }
  142.     total_ans=0;
  143.     outv.assign(Qn+1,0);
  144.     dfs_seg(1,1,Qn+1);
  145.     for(int i=1;i<=Qn;i++) cout<<outv[i]<<"\n";
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 4 4
9 5 7 2
1 2
2 3
3 1
1 4
1 4
1 1
2 1
1 2
stdout
copy 
21
16
21
16
https://ideone.com/XWuODw
language:
C++14 (gcc 8.3)
created:
15 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!