P6617

发表于 分类于
查找 Search

查找 Search

我们尝试维护 $a_i$ 的前驱，定义为 $a_i$ 之前第一个数值为 $w-a_i$ 的数的位置。

但是这样单点修改会非常的麻烦。

所以需要等价转化一下。

比如说，对于数值相同的两个数 $a_i$ 和 $a_{i+k}$，它们的前驱都为 $j$，那么我们其实可以把 $a_{i+k}$ 的前驱直接修改为 0（这样并不会影响答案）。

这样的话，我们单点修改时需要修改的前驱就会少很多。

我们发现，更改 $a_x$ 的值为 $y$，需要修改前驱的位置有这么几个：

  1. 值为 $a_x$ 且在 $x$ 后面的第一个数的位置。

  2. 值为 $w-a_x$ 且在 $x$ 后面的第一个数的位置。

  3. $x$ 这个位置。

  4. 值为 $y$ 且在 $x$ 后面的第一个数的位置。

  5. 值为 $w-y$ 且在 $x$ 后面的第一个数的位置。

很容易发现基本都是求后继，可以用一个 set 来维护。

方便修改前驱而避免一些繁琐的等价转换，我们尝试让实现变得比较整齐。

比如说，加入一个 $pre(x)$ 函数，实时求出 $x$ 的前驱。

这样我们就可以先记录要修改的位置，再直接修改 set 的结构，最后一口气统一修改它们的前驱，同时还能减少很多错误。

因为一开始在技巧性上丢失太多，暴力分类讨论导致代码冗长难以调试，非常痛苦。

时间复杂度 $O((m+n)\log n)$。

代码：

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
113
114
#include<iostream>
#include<cstdio>
#include<map>
#include<set>
#include<vector>
#define ll long long
using namespace std;

const ll N=5e5;

ll n,m,w,op,x,y,cnt;

ll a[N+5];

set<ll> s[N+5];

ll pre(ll x) {
	set<ll>::iterator it1=s[a[x]].lower_bound(x),it2=s[w-a[x]].lower_bound(x);
	if(it2==s[w-a[x]].begin()) return 0;
	else if(it1==s[a[x]].begin()) return *--it2;
	else if(*--it1>*--it2) return 0;
	else return *it2;
}

struct sgt{
	ll l,r,mp;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define mp(x) tree[x].mp
}tree[N*4+5];

void build(ll p,ll l,ll r) {
	l(p)=l;r(p)=r;
	if(l==r) {mp(p)=pre(l);return;}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	mp(p)=max(mp(p<<1),mp(p<<1|1));
}

ll ask(ll p,ll l,ll r) {
	if(l(p)>=l&&r(p)<=r) return mp(p);
	ll mid=(l(p)+r(p))>>1;
	if(l>mid) return ask(p<<1|1,l,r);
	if(r<=mid) return ask(p<<1,l,r);
	return max(ask(p<<1,l,r),ask(p<<1|1,l,r));
}

void modifypre(ll p,ll x,ll y) {
	if(l(p)==r(p)) {mp(p)=y;return;}
	ll mid=(l(p)+r(p))>>1;
	if(x<=mid) modifypre(p<<1,x,y);
	if(x>mid) modifypre(p<<1|1,x,y);
	mp(p)=max(mp(p<<1),mp(p<<1|1));
}

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

int main() {

	n=read();m=read();w=read();
	
	for(ll i=1;i<=n;i++) {
		a[i]=read();
		s[a[i]].insert(i);
	}

	build(1,1,n);

	while(m--) {
		op=read();x=read();y=read();
		if(op==1) {
			set<ll>::iterator it;
			ll res[5],cnt=-1;
			it=s[a[x]].upper_bound(x);
			if(it!=s[a[x]].end()) res[++cnt]=*it;
			it=s[w-a[x]].upper_bound(x);
			if(it!=s[w-a[x]].end()) res[++cnt]=*it;
			s[a[x]].erase(x);
			s[y].insert(x);a[x]=y;
			res[++cnt]=x;
			it=s[a[x]].upper_bound(x);
			if(it!=s[a[x]].end()) res[++cnt]=*it;
			it=s[w-a[x]].upper_bound(x);
			if(it!=s[w-a[x]].end()) res[++cnt]=*it;
			for(ll i=0;i<=cnt;i++) modifypre(1,res[i],pre(res[i]));
		}
		if(op==2) {
			x^=cnt;y^=cnt;
			if(ask(1,x,y)>=x) {
				printf("Yes\n");cnt++;
			}
			else printf("No\n");
		}
	}
	
	return 0;
}