Mess Change Queries(线段树)

描述

传送门:CodeForces - 911G

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 $a_i = x$ you have to set $a_i$ 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 $a_1, a_2, …, a_n$ ($1 ≤ a_i ≤ 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
1
2
3
4
5
6
5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5
  • Output
1
5 2 5 4 5

思路

注意到数组中的数范围很小,所以我们可以开$100$个线段树来维护每一个数的变换。然后,区间更新打延迟标记,写个pushdown……最后所有点单点查询一下变成了啥,就没了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

#define lson rt << 1
#define rson rt << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson

const int N = 1 << 18;
int a[N];
int num[N << 2][105];
void build(int l, int r, int rt)
{
for (int i = 1; i <= 100; i++) num[rt][i] = i;
if (l == r) return;
int m = (l + r) >> 1;
build(Lson);
build(Rson);
}

void pushdown(int rt)
{
for (int i = 1; i <= 100; i++)
{
num[lson][i] = num[rt][num[lson][i]];
num[rson][i] = num[rt][num[rson][i]];
}
for (int i = 1; i <= 100; i++)
num[rt][i] = i;
}

void update(int L, int R, int x, int y, int l, int r, int rt)
{
if (L <= l && r <= R)
{
for (int i = 1; i <= 100; i++)
if (num[rt][i] == x) num[rt][i] = y;
return;
}
pushdown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, x, y, Lson);
if (m < R) update(L, R, x, y, Rson);
}

void query(int l, int r, int rt)
{
if (l == r)
{
a[l] = num[rt][a[l]];
return;
}
pushdown(rt);
int m = (l + r) >> 1;
query(Lson);
query(Rson);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, q;
while (~scanf("%d", &n))
{
build(1, n, 1);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
scanf("%d", &q);
while (q--)
{
static int l, r, x, y;
scanf("%d%d%d%d", &l, &r, &x, &y);
update(l, r, x, y, 1, n, 1);
}
query(1, n, 1);
for (int i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
return 0;
}
捐助作者