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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int N = 300005;
int n, m, ans, a[N], mn[N<<2], mx[N<<2], g[N<<2], pre[N<<2];
map<int,set<int> > f;
inline int gcd(int x, int y){ return y?gcd(y, x%y):x;}
void build(int l, int r, int t){
if(l==r) return (void)( mn[t]=mx[t]=a[l], g[t]=a[l]-a[l-1]);
int mid=l+r>>1, k=t<<1;
build(l, mid, k), build(mid+1, r, k|1);
mn[t]=min(mn[k], mn[k|1]), mx[t]=max(mx[k], mx[k|1]), g[t]=gcd(g[k], g[k|1]);
}
void modify1(int l, int r, int t, int x, int y){
if(l==r) return (void)(mn[t]=mx[t]=y);
int mid=l+r>>1, k=t<<1;
if(x<=mid) modify1(l, mid, k, x, y); else modify1(mid+1, r, k|1, x, y);
mn[t]=min(mn[k], mn[k|1]), mx[t]=max(mx[k], mx[k|1]);
}
void modify2(int l, int r, int t, int x, int y){
if(l==r) return (void)(g[t]=y);
int mid=l+r>>1, k=t<<1;
if(x<=mid) modify2(l, mid, k, x, y); else modify2(mid+1, r, k|1, x, y);
g[t]=gcd(g[k], g[k|1]);
}
void modify3(int l, int r, int t, int x, int y){
if(l==r) return (void)(pre[t]=y);
int mid=l+r>>1, k=t<<1;
if(x<=mid) modify3(l, mid, k, x, y); else modify3(mid+1, r, k|1, x, y);
pre[t]=max(pre[k], pre[k|1]);
}
pair<int,int> query1(int l, int r, int t, int L, int R){
if(L<=l && r<=R) return make_pair(mn[t], mx[t]);
int mid=l+r>>1, k=t<<1;
if(R<=mid) return query1(l, mid, k, L, R);
if(L>mid) return query1(mid+1, r, k|1, L, R);
pair<int,int> x=query1(l, mid, k, L, R), y=query1(mid+1, r, k|1, L, R);
return make_pair(min(x.first, y.first), max(x.second, y.second));
}
int query2(int l, int r, int t, int L, int R){
if(L<=l && r<=R) return g[t];
int mid=l+r>>1, k=t<<1;
if(R<=mid) return query2(l, mid, k, L, R);
if(L>mid) return query2(mid+1, r, k|1, L, R);
return gcd(query2(l, mid, k, L, R), query2(mid+1, r, k|1, L, R));
}
int query3(int l, int r, int t, int L, int R){
if(L<=l && r<=R) return pre[t];
int mid=l+r>>1, k=t<<1;
return max(L<=mid?query3(l, mid, k, L, R):0, R>mid?query3(mid+1, r, k|1, L, R):0);
}
int main() {
read(n), read(m);
for(int i=1; i<=n; ++i){
read(a[i]);
set<int> *s=&f[a[i]];
set<int>::iterator it=s->end();
if(it!=s->begin()) modify3(1, n, 1, i, *--it);
s->insert(i);
}
build(1, n, 1);
while(m--){
static int opt, x, y, k;
read(opt), read(x), read(y), x^=ans, y^=ans;
if(opt==1){
modify1(1, n, 1, x, y);
modify2(1, n, 1, x, y-a[x-1]);
modify2(1, n, 1, x+1, a[x+1]-y);
set<int> *s=&f[a[x]];
set<int>::iterator it=s->find(x);
if(++it!=s->end()) k=*it, modify3(1, n, 1, k, (--it==s->begin()?0:*--it));
s->erase(x);
s=&f[a[x]=y];
it=s->lower_bound(x);
if(it!=s->end()) modify3(1, n, 1, *it, x);
if(it!=s->begin()) modify3(1, n, 1, x, *--it); else modify3(1, n, 1, x, 0);
s->insert(x);
}
else{
read(k), k^=ans;
pair<int,int> tmp=query1(1, n, 1, x, y);
if(x==y) puts("Yes"), ++ans;
else if(k==0 && tmp.second==tmp.first) puts("Yes"), ++ans;
else if(tmp.second-tmp.first==(ll)(y-x)*k && query3(1, n, 1, x, y)<x && abs(query2(1, n, 1, x+1, y))==k) puts("Yes"), ++ans; else puts("No");
}
}
return 0;
}
|