fork download 
  1. #include <iostream>
  2. #include <queue>
  3. #include <map>
  4.  
  5. using namespace std;
  6.  
  7. typedef pair<int, int> pii;
  8.  
  9. #define maxNMQ 200007
  10. #define MAXLOG 20
  11. int a[maxNMQ];
  12. int n, m, q;
  13. map<long long, int>luu;
  14.  
  15. struct query
  16. {
  17.     string type;
  18.     int inp1, inp2;
  19. } que[maxNMQ];
  20. bool del[maxNMQ] = {false};
  21.  
  22. query newQue[maxNMQ];
  23.  
  24. int parent[maxNMQ];
  25. int sz[maxNMQ];
  26. long long sum[maxNMQ];
  27. long long ans[maxNMQ];
  28. pii edge[maxNMQ];
  29.  
  30. void readData()
  31. {
  32.     cin >> n >> m >> q;
  33.     for(int i = 1; i <= n; i++)
  34.         cin >> a[i];
  35.     int u, v;
  36.     for(int i = 1; i <= m; i++)
  37.     {
  38.         cin >> u >> v;
  39.         edge[i].first = u;
  40.         edge[i].second = v;
  41.     }
  42.     string t;
  43.     int x, y;
  44.     for(int i = 1; i <= q; i++)
  45.     {
  46.         y = -1;
  47.         cin >> t >> x;
  48.         if(t == "C")
  49.             cin >> y;
  50.         else
  51.             del[x] = true;
  52.         que[i].type = t;
  53.         que[i].inp1 = x;
  54.         que[i].inp2 = y;
  55.     }
  56. }
  57.  
  58. void make_set(int v)
  59. {
  60.     sz[v] = 1;
  61.     sum[v] = a[v];
  62.     parent[v] = v;
  63.     luu[a[v]]++;
  64. }
  65.  
  66. int get_set(int v)
  67. {
  68.     if(parent[v] == v)
  69.         return v;
  70.     int p = get_set(parent[v]);
  71.     parent[v] = p;
  72.     return p;
  73. }
  74.  
  75. void updateVal(int v, int val)
  76. {
  77.     int p = get_set(v);
  78.     luu[sum[p]]--;
  79.     if(luu[sum[p]] == 0)
  80.         luu.erase(sum[p]);
  81.     luu[sum[p]+val-a[v]]++;
  82.     sum[p] = sum[p] + val-a[v];
  83.     a[v] = val;
  84. }
  85.  
  86. void union_set(int u, int v)
  87. {
  88.     u = get_set(u);
  89.  
  90.     v = get_set(v);
  91.  
  92.     if(u != v)
  93.     {
  94.         luu[sum[u]]--;
  95.         if(luu[sum[u]] == 0)
  96.             luu.erase(sum[u]);
  97.         luu[sum[v]]--;
  98.         if(luu[sum[v]] == 0)
  99.             luu.erase(sum[v]);
  100.  
  101.         if(sz[u] < sz[v])
  102.             swap(u, v);
  103.         parent[v] = u;
  104.         sum[u] += sum[v];
  105.         sz[u] += sz[v];
  106.         luu[sum[u]]++;
  107.     }
  108. }
  109.  
  110. void preprocess()
  111. {
  112.     for(int i = 1; i <= n; i++)
  113.         make_set(i);
  114.     for(int i = 1; i <= m; i++)
  115.         if(!del[i])
  116.             union_set(edge[i].first, edge[i].second);
  117.     query temp;
  118.     for(int i = 1; i <= q; i++)
  119.     {
  120.         temp = que[i];
  121.         if(temp.type == "D")
  122.         {
  123.             newQue[i].type = 'A';
  124.             newQue[i].inp1 = temp.inp1;
  125.         }
  126.         else
  127.         {
  128.             newQue[i].type = 'C';
  129.             newQue[i].inp1 = temp.inp1;
  130.             newQue[i].inp2 = a[temp.inp1];
  131.             updateVal(temp.inp1, temp.inp2);
  132.             a[temp.inp1] = temp.inp2;
  133.         }
  134.     }
  135. }
  136.  
  137. void solve()
  138. {
  139.     map<long long, int>::iterator it;
  140.     query temp;
  141.     for(int i = q; i >= 1; i--)
  142.     {
  143.         it = luu.end();
  144.         it = prev(it);
  145.         ans[i] = it->first;
  146.         temp = newQue[i];
  147.         if(temp.type == "A")
  148.             union_set(edge[temp.inp1].first, edge[temp.inp1].second);
  149.         else
  150.             updateVal(temp.inp1, temp.inp2);
  151.     }
  152.     for(int i = 1; i <= q; i++)
  153.         cout << ans[i] << "\n";
  154. }
  155.  
  156. int main()
  157. {
  158.     ios_base::sync_with_stdio(0);
  159.     cin.tie(0);
  160.     cout.tie(0);
  161.     readData();
  162.     preprocess();
  163.     solve();
  164.     return 0;
  165. }
  166.  
Success #stdin #stdout 0.01s 24040KB
comments (?)
stdin 
4 4 6
1 1 1 1
1 2
2 4
1 4
2 3
D 4
C 3 5
C 1 4
D 2
D 1
D 3
stdout 
3
5
6
6
5
5
https://ideone.com/K0lkq8
language:
C++14 (gcc 8.3)
created:
20 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!