Algorithm

G. Mass Change Queries
time limit per test
3 seconds
memory limit per test
512 megabytes
Problem link- https://codeforces.com/contest/911/problem/G
input
standard input
output
standard output

You are given an array a consisting of n integers. You have to process q queries to this array; each query is given as four numbers l, r, x and y, denoting that for every i such that l ≤ i ≤ r and ai = x you have to set ai equal to y.

Print the array after all queries are processed.

Input

The first line contains one integer n (1 ≤ n ≤ 200000) — the size of array a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the elements of array a.

The third line contains one integer q (1 ≤ q ≤ 200000) — the number of queries you have to process.

Then q lines follow. i-th line contains four integers l, r, x and y denoting i-th query (1 ≤ l ≤ r ≤ n, 1 ≤ x, y ≤ 100).

Output

Print n integers — elements of array a after all changes are made.

Example
input
Copy
5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5
output
Copy
5 2 5 4 5

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1, M = 1e2 + 1;
int n, q, s, e, x, y, tar, a[N], seg[4 * N][M], lazy[4 * N];

void build(int at, int l, int r) {
  for(int i = 1; i < M; ++i)
    seg[at][i] = i;

  if(l == r)
    return;

  int mid = (l + r) >> 1;
  build(at << 1, l, mid);
  build(at << 1 | 1, mid + 1, r);
}

void pro(int at, int l, int r) {
  if(l != r) {
    lazy[at << 1] = lazy[at << 1 | 1] = 1;

    for(int i = 1; i < M; ++i)
      seg[at << 1][i] = seg[at][seg[at << 1][i]],
      seg[at << 1 | 1][i] = seg[at][seg[at << 1 | 1][i]];

    lazy[at] = 0;
    for(int i = 1; i < M; ++i)
      seg[at][i] = i;
  }
}

void update(int at, int l, int r) {
  if(lazy[at] != 0)
    pro(at, l, r);

  if(l > e || r < s)
    return;

  if(l >= s && r <= e) {
    lazy[at] = 1;
    for(int i = 1; i < M; ++i)
      if(seg[at][i] == x)
        seg[at][i] = y;
    pro(at, l, r);
    return;
  }

  int mid = (l + r) >> 1;
  update(at << 1, l, mid);
  update(at << 1 | 1, mid + 1, r);
}

int get(int at, int l, int r) {
  if(lazy[at] != 0)
    pro(at, l, r);

  if(l > e || r < s)
    return 0;

  if(l >= s && r <= e)
    return seg[at][tar];

  int mid = (l + r) >> 1;
  return get(at << 1, l, mid) + get(at << 1 | 1, mid + 1, r);
}

int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)
    scanf("%d", a + i);

  build(1, 1, n);

  scanf("%d", &q);
  for(int i = 0; i < q; ++i) {
    scanf("%d %d %d %d", &s, &e, &x, &y);
    update(1, 1, n);
  }

  for(int i = 1; i <= n; ++i) {
    s = e = i;
    tar = a[i];
    printf("%s%d", i == 1 ? "" : " ", get(1, 1, n));
  }
  puts("");

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5

Output

x
–
+
cmd
5 2 5 4 5
Advertisements

Demonstration

Codeforces Solution-Mass Change Queries-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+