P3792

发表于 更新于 分类于
由乃与大母神原型和偶像崇拜

由乃与大母神原型和偶像崇拜

神奇的做法。

一个比较好想的正解是维护序列的最大值、最小值，再用带修主席树维护值域，查询每个区间内的数是否都仅出现一次。但估计空间承受不下。

这个的复杂度大概是 $O(n\log^2 n)$ 的。但是考虑到维护的细节其实不少，所以有一种奇技淫巧：Hash。

我们将序列的和与平方和作为键值与我们想要的值比较即可。

因为卡了 Hash，所以要精心构造一些模数才能通过（并且还需要精心处理逆元）。

当然也有更省事的办法：__int128 。

据说维护区间异或和的 Hash 也可以。

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

正解可以记录一个数的前驱，具体需要用 map 和 set 来实现。然后就可以用这个来判断区间内是否有重复的数。

这个题对我这种人傻自带大常数的非常不友好，调了一节晚自习才搞过去。

代码（记录前驱）：

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#define ll int
using namespace std;

const ll N=5e5,M=6e5;

ll n,m,op,x,y,tot,top;

ll a[N+5],pre[N+5],st[N+5];

set<ll> s[M+5];

map<ll,ll> ss,mp;

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

void build(ll p,ll l,ll r) {
	l(p)=l;r(p)=r;
	if(l==r) {
		ma(p)=a[l];mi(p)=a[l];mpre(p)=pre[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	ma(p)=max(ma(p<<1),ma(p<<1|1));
	mi(p)=min(mi(p<<1),mi(p<<1|1));
	mpre(p)=max(mpre(p<<1),mpre(p<<1|1));
}

void modifypre(ll p,ll x,ll y) {
	if(l(p)==r(p)) {
		mpre(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);
	mpre(p)=max(mpre(p<<1),mpre(p<<1|1));
}

void modifyval(ll p,ll x,ll y) {
	if(l(p)==r(p)) {
		ma(p)=y;mi(p)=y;return;
	}
	ll mid=(l(p)+r(p))>>1;
	if(x<=mid) modifyval(p<<1,x,y);
	if(x>mid) modifyval(p<<1|1,x,y);
	ma(p)=max(ma(p<<1),ma(p<<1|1));
	mi(p)=min(mi(p<<1),mi(p<<1|1));
}

sgt get(ll p,ll l,ll r) {
	if(l(p)>=l&&r(p)<=r) return tree[p];
	ll mid=(l(p)+r(p))>>1;
	if(l>mid) return get(p<<1|1,l,r);
	if(r<=mid) return get(p<<1,l,r);
	sgt L=get(p<<1,l,r),R=get(p<<1|1,l,r),res;
	res.ma=max(L.ma,R.ma);
	res.mi=min(L.mi,R.mi);
	res.mpre=max(L.mpre,R.mpre);
	return res;
}

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 {
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

int main() {

	n=read();m=read();

	for(ll i=1;i<=n;i++) {
		a[i]=read();
		if(ss.find(a[i])==ss.end()) pre[i]=0;
		else pre[i]=ss[a[i]];
		ss[a[i]]=i;
		if(mp.find(a[i])==mp.end()) mp[a[i]]=++tot;
		s[mp[a[i]]].insert(i);
	}

	build(1,1,n);

	while(m--) {
		op=read();x=read();y=read();
		if(op==1) {
			ll temp1=mp[a[x]],temp2=0,tmppre=0,pos=0;
			if(mp.find(y)!=mp.end()) temp2=mp[y];
			else temp2=mp[y]=++tot;
			set<ll>::iterator it1,it2,it0;
			it0=it1=it2=s[temp1].find(x);
			if(it1!=s[temp1].begin()) tmppre=*--it1;
			if(++it2!=s[temp1].end()) pos=*it2;
			if(pos>0) modifypre(1,pos,tmppre);
			s[temp1].erase(it0);
			s[temp2].insert(x);
			it1=it2=s[temp2].find(x);
			if(it1==s[temp2].begin()) modifypre(1,x,0);
			else modifypre(1,x,*--it1);
			if(++it2!=s[temp2].end()) modifypre(1,*it2,x);
			modifyval(1,x,y);a[x]=y;
		}
		if(op==2) {
			sgt tmp=get(1,x,y);
			if(tmp.mpre<x&&tmp.ma-tmp.mi==y-x) printf("damushen\n");
			else printf("yuanxing\n");
		}
	}

	return 0;
}

代码（Hash）：

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll __int128
using namespace std;

const ll N=5e5;

ll n,m,op,x,y;

ll a[N+5];

struct sgt{
	ll l,r,hash1,hash2,hash3,ma,mi;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define hash1(x) tree[x].hash1
	#define hash2(x) tree[x].hash2
	#define ma(x) tree[x].ma
	#define mi(x) tree[x].mi
}tree[N*4+5];

void build(ll p,ll l,ll r) {
	l(p)=l;r(p)=r;
	if(l==r) {
		ma(p)=a[l];mi(p)=a[l];
		hash1(p)=a[l];hash2(p)=a[l]*a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	ma(p)=max(ma(p<<1),ma(p<<1|1));
	mi(p)=min(mi(p<<1),mi(p<<1|1));
	hash1(p)=hash1(p<<1)+hash1(p<<1|1);
	hash2(p)=hash2(p<<1)+hash2(p<<1|1);
}

void modify(ll p,ll x,ll y) {
	if(l(p)==r(p)) {
		ma(p)=y;mi(p)=y;
		hash1(p)=y;hash2(p)=y*y;
		return;
	}
	ll mid=(l(p)+r(p))>>1;
	if(x<=mid) modify(p<<1,x,y);
	if(x>mid) modify(p<<1|1,x,y);
	ma(p)=max(ma(p<<1),ma(p<<1|1));
	mi(p)=min(mi(p<<1),mi(p<<1|1));
	hash1(p)=hash1(p<<1)+hash1(p<<1|1);
	hash2(p)=hash2(p<<1)+hash2(p<<1|1);
}

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

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

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

ll getmin(ll p,ll l,ll r) {
	if(l(p)>=l&&r(p)<=r) {
		return mi(p);
	}
	ll mid=(l(p)+r(p))>>1;
	if(l>mid) return getmin(p<<1|1,l,r);
	if(r<=mid) return getmin(p<<1,l,r);
	return min(getmin(p<<1,l,r),getmin(p<<1|1,l,r));
}

ll sum(ll l,ll r) {
	return (l+r)*(r-l+1)/2;
}

ll sqsum(ll x) {
	return x*(x+1)*(2*x+1)/6;
}

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 {
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

int main() {

	n=read();m=read();

	for(ll i=1;i<=n;i++) {
		a[i]=read();
	}

	build(1,1,n);

	while(m--) {
		op=read();x=read();y=read();
		if(op==1) {
			modify(1,x,y);
		}
		if(op==2) {
			ll maxx=getmax(1,x,y),minn=getmin(1,x,y);
			if(maxx-minn+1!=y-x+1) {
				printf("yuanxing\n");
			}
			else {
				ll key1=ask1(1,x,y),key2=ask2(1,x,y);
				ll tmp1=sum(minn,maxx),tmp2=sqsum(maxx)-sqsum(minn-1);
				if(tmp1==key1&&tmp2==key2) {
					printf("damushen\n");
				}
				else printf("yuanxing\n");
			}
		}
	}

	return 0;
}