fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  6. #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define ALL(a) (a).begin(), (a).end()
  11. #define task "kingdom"
  12.  
  13. typedef vector<int> vi;
  14. typedef pair<int, int> ii;
  15. typedef pair<int, ii> pii;
  16.  
  17. const int N = 3e5 + 5;
  18. const int INF = 0x3f3f3f3f;
  19. const int MOD = 1e9 + 2277;
  20.  
  21. int n, m, q, a[N], nxt[N], pos[N], block[N];
  22. ii edges[N], T[4 * N];
  23.  
  24. struct DSU{
  25.     vi lab, foot, head;
  26.     DSU(int n) : lab(n, -1), foot(n),  head(n) {};
  27.     void make_set(int u){
  28.         foot[u] = head[u] = u;
  29.     }
  30.  
  31.     int Find(int u){
  32.         return lab[u] < 0 ? u : lab[u] = Find(lab[u]);
  33.     }
  34.  
  35.     void Union(int u, int v){
  36.         if ((u = Find(u)) == (v = Find(v))) return;
  37.         if (lab[u] < lab[v]) swap(u, v);
  38.         lab[u] += lab[v];
  39.         lab[v] = u;
  40.         nxt[foot[u]] = head[v];
  41.         foot[u] = foot[v];
  42.  
  43.     }
  44.  
  45. };
  46.  
  47. void update(int id, int l, int r, int pos, int val){
  48.     if(l == r){
  49.         T[id] = {val, l};
  50.         return;
  51.     }
  52.     int m = (l + r)/2;
  53.     if (pos <= m) update(id*2, l, m, pos, val);
  54.     else update(id*2+1, m+1, r, pos, val);
  55.     T[id] = max(T[id*2], T[id * 2 + 1]);
  56. }
  57.  
  58. ii get(int id, int l, int r, int u, int v){
  59.     if (l > v || r < u) return {0, 0};
  60.     if (u <= l && r <= v) return T[id];
  61.     int m = (l +r )/2;
  62.     return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
  63. }
  64.  
  65. signed main(){
  66.     ios_base::sync_with_stdio(0);
  67.     cin.tie(0); cout.tie(0);
  68.     if (fopen(task".inp", "r")){
  69.         freopen(task".inp", "r", stdin);
  70.         freopen(task".out", "w", stdout);
  71.     }
  72.     cin >> n >> m >> q;
  73.     FOR (i, 1, n) cin >> a[i];
  74.     FOR (i, 1, m){
  75.         int u, v; cin >> u >> v;
  76.         edges[i] = {u, v};
  77.     }
  78.  
  79.     vector<ii> queries;
  80.     DSU dsu(n +5 );
  81.     FOR (i, 1, n) dsu.make_set(i);
  82.  
  83.     FOR (i, 1, q){
  84.         int x, k; cin >> x >> k;
  85.         queries.pb({x, k});
  86.         if (x == 2) block[k]++;
  87.     }
  88.  
  89.     FOR (i, 1, m){
  90.         if (block[i]) continue;
  91.         dsu.Union(edges[i].fi, edges[i].se);
  92.     }
  93.  
  94.     DSU dsu2 = dsu;
  95.     FORD(i, q - 1, 0){
  96.         if (queries[i].fi == 1) continue;
  97.         block[queries[i].se]--;
  98.         if (!block[queries[i].se]) dsu2.Union(edges[queries[i].se].fi, edges[queries[i].se].se);
  99.     }
  100.  
  101.  
  102.     for (ii &x : queries) if (x.fi == 2) block[x.se]++;
  103.     FOR (i, 1, n){
  104.         if (pos[i]) continue;
  105.         int u = dsu2.head[dsu2.Find(i)];
  106.         while (u){
  107.             pos[u] = ++pos[0];
  108.             update(1, 1, n, pos[u], a[u]);
  109.             u = nxt[u];
  110.         }
  111.     }
  112.  
  113.     vector<ii> vec;
  114.     FORD(i, q - 1, 0){
  115.         ii x = queries[i];
  116.         if (x.fi == 2){
  117.             block[x.se]--;
  118.             if (block[x.se] == 0) dsu.Union(edges[x.se].fi, edges[x.se].se);
  119.         } else {
  120.             int u = dsu.Find(x.se);
  121.             vec.pb({pos[dsu.head[u]], pos[dsu.foot[u]]});
  122.         }
  123.     }
  124.     reverse(ALL(vec));
  125.     for (ii &x : vec){
  126.         ii tmp = get(1, 1, n, x.fi, x.se);
  127.         cout << tmp.fi << '\n';
  128.         update(1, 1, n, tmp.se, 0);
  129.     }
  130.  
  131.     return 0;
  132. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UDZ29e
language:
C++14 (gcc 8.3)
created:
9 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!