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
| #include <iostream>
#include <cstdio>
#define maxn 1000010
#define ll long long
#define INF 1000000000
using namespace std;
const int p = 998244353;
const int base = 1919810;
int n, m, a[maxn];
int Pow[maxn];
void init_pow(int n) {
Pow[0] = 1; for (int i = 1; i <= n; ++i) Pow[i] = 1ll * Pow[i - 1] * base % p;
}
#define lc i << 1
#define rc i << 1 | 1
struct Seg {
int v, sum;
} T[maxn * 4];
inline Seg maintain(const Seg &ls, const Seg &rs) {
Seg o;
o.v = min(ls.v, rs.v);
o.sum = (ls.sum + rs.sum) % p;
return o;
}
void build(int i, int l, int r) {
if (l == r) return (void) (T[i] = { a[l], Pow[a[l]] });
int m = l + r >> 1;
build(lc, l, m); build(rc, m + 1, r);
T[i] = maintain(T[lc], T[rc]);
}
void update(int i, int l, int r, int k, int v) {
if (l == r) return (void) (T[i] = { v, Pow[v] });
int m = l + r >> 1;
if (k <= m) update(lc, l, m, k, v);
else update(rc, m + 1, r, k, v);
T[i] = maintain(T[lc], T[rc]);
}
Seg query(int i, int l, int r, int L, int R) {
if (l > R || r < L) return { INF, 0 } ;
if (L <= l && r <= R) return T[i];
int m = l + r >> 1;
return maintain(query(lc, l, m, L, R), query(rc, m + 1, r, L, R));
}
inline void solve_1() {
int x, y; cin >> x >> y;
update(1, 1, n, x, y);
}
inline void solve_2() {
int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
Seg t1 = query(1, 1, n, l1, r1), t2 = query(1, 1, n, l2, r2);
if (t1.v > t2.v) swap(t1, t2);
cout << (1ll * t1.sum * Pow[t2.v - t1.v] % p == t2.sum ? "YES\n" : "NO\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; init_pow(1000000);
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int opt; cin >> opt;
if (!opt) solve_1();
else solve_2();
}
return 0;
}
|