fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = (int)1e18 + 462010;
  17. const int MAX_A = 100;
  18. const int MAX_N = 2e5;
  19. const int BS = 450;
  20.  
  21. struct Disjoint_Set_Union {
  22.     int parent[MAX_A + 5];
  23.     int root[MAX_A + 5];
  24.     int color[MAX_A + 5];
  25.  
  26.     void build() {
  27.         FOR(i, 1, MAX_A) {
  28.             parent[i] = i;
  29.             root[i] = i;
  30.             color[i] = i;
  31.         }
  32.     }
  33.  
  34.     int get(int u) {
  35.         if (u == parent[u]) return u;
  36.         return parent[u] = get(parent[u]);
  37.     }
  38.  
  39.     void unite(int x, int y) {
  40.         if (x == y || root[x] == 0) return;
  41.  
  42.         if (root[y] == 0) {
  43.             root[y] = root[x];
  44.             color[root[y]] = y;
  45.             root[x] = 0;
  46.         } else {
  47.             parent[root[x]] = root[y];
  48.             root[x] = 0;
  49.         }
  50.     }
  51.  
  52.     int value(int u) {
  53.         return color[get(u)];
  54.     }
  55. }dsu[MAX_N / BS + 5];
  56.  
  57. int a[MAX_N + 5];
  58. int n, q;
  59.  
  60. void Input(){
  61.     cin >> n >> q;
  62.     FOR(i, 1, n) cin >> a[i];
  63. }
  64.  
  65. void re_build(int l, int r, int x, int y){
  66.     int block = l / BS;
  67.     FOR(i, max(1LL, block * BS), min(n, (block + 1) * BS - 1)){
  68.         a[i] = dsu[block].value(a[i]);
  69.         if(l <= i && i <= r && a[i] == x) a[i] = y;
  70.     }
  71.     dsu[block].build();
  72. }
  73.  
  74. void process(int l, int r, int x, int y){
  75.     int bl = l / BS, br = r / BS;
  76.  
  77.     if(bl == br){
  78.         re_build(l, r, x, y);
  79.         return;
  80.     }
  81.  
  82.     FOR(i, bl + 1, br - 1) dsu[i].unite(x, y);
  83.     re_build(l, (bl + 1) * BS - 1, x, y);
  84.     re_build(br * BS, r, x, y);
  85. }
  86.  
  87. void Prepare(){
  88.     FOR(i, 0, n / BS) dsu[i].build();
  89. }
  90.  
  91. void Solve(){
  92.     while(q--){
  93.         int l, r, x, y;
  94.         cin >> l >> r >> x >> y;
  95.         process(l, r, x, y);
  96.     }
  97.     FOR(i, 1, n) cout << dsu[i / BS].value(a[i]) << " ";
  98. }
  99.  
  100. signed main(){
  101.     freopen("rangeset.INP", "r", stdin);
  102.     freopen("rangeset.OUT", "w", stdout);
  103.     ios_base::sync_with_stdio(0);
  104.     cin.tie(0);
  105.  
  106.     Input();
  107.     Prepare();
  108.     Solve();
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0s 5920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zf1mC5
language:
C++ (gcc 8.3)
created:
1 day 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!