fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Query{
  6.     int L, R, W;
  7. };
  8.  
  9. const int MAXN = 1e6 + 5;
  10. const int MAXQ = MAXN * 4;
  11.  
  12. int label[MAXQ];
  13. int find_set(int u){
  14.     return (label[u] < 0 ? u : label[u] = find_set(label[u]));
  15. }
  16. void union_set(int u, int v){
  17. //    if(label[u] > label[v]) swap(u, v);
  18. //    label[u] += label[v];
  19. //    label[v] = u;
  20.         label[u] = v;
  21. }
  22.  
  23. set<pair<int, int>> Pos;
  24. vector<Query> Queries;
  25. int Last[MAXN], arr[MAXN];
  26. int n, q;
  27.  
  28. void add_que(int l, int r, int w){
  29.     if(r < l) return;
  30.     int idx = Queries.size();
  31.     Queries.push_back({l, r, w});
  32.  
  33.     set<pair<int, int>>::iterator it = Pos.lower_bound({l, -1e9});
  34.     while(it != Pos.end()){
  35.         if(r < it->first) break;
  36.         if(it->second < 0){
  37.             Last[-it->second] = idx;
  38.         }
  39.         else{
  40.             union_set(find_set(it->second), find_set(idx));
  41.         }
  42.         Pos.erase(it++);
  43.     }
  44.     Pos.insert({w, idx});
  45. }
  46.  
  47. int main(){
  48.     cin.tie(NULL)->sync_with_stdio(false);
  49.  
  50.     if(fopen("test.inp", "r")){
  51.             freopen("test.inp", "r", stdin);
  52.             freopen("test.out", "w", stdout);
  53.     }
  54.  
  55.     cin >> n;
  56.     for(int i = 1; i <= n; ++i){
  57.         cin >> arr[i];
  58.         Last[i] = -1;
  59.         Pos.insert({arr[i], -i});
  60.     }
  61.     memset(label, 0xff, sizeof(label));
  62.  
  63.     cin >> q;
  64.     for(int i = 1; i <= q; ++i){
  65.         int t, u, v;
  66.         cin >> t;
  67.         if(t == 1){
  68.             cin >> u >> v;
  69.             Pos.erase({arr[u], -u});
  70.             arr[u] = v;
  71.             Last[u] = -1;
  72.             Pos.insert({v, -u});
  73.         }
  74.         else if(t == 2){
  75.             cin >> u;
  76.             if(Last[u] == -1) cout << arr[u] << '\n';
  77.             else cout << Queries[find_set(Last[u])].W << '\n';
  78.         }
  79.         else{
  80.             cin >> u >> v;
  81.             int m = u + v >> 1;
  82.  
  83.             add_que(u, m, u - 1);
  84.             add_que(m + 1, v, v + 1);
  85.         }
  86.     }
  87.     return 0;
  88. }
Success #stdin #stdout 0.01s 19900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/56rsjj
language:
C++14 (gcc 8.3)
created:
3 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!