P5278 算术天才⑨与等差数列

发表于

闲扯

这道题 $JKLover$ 讲过，然后补课的时候老师也提到了，想了想还是做了吧，顺便写篇题解纪念一下。

题面

P5278 算术天才⑨与等差数列

Solution

对于一个序列，如果它排序后能构成一个公差为 $d$ 等差数列，一定满足一下几点：

  1. $max-min=d\cdot(len-1)$ 。
  2. $gcd_{k=i}^{j-1}(val_{k+1}-val_k)=d$ 。
  3. 序列中没有重复元素。

前两个条件很好维护，直接上线段树即可，所以我们需要着重解决的是第 $3$ 个条件。

有一个很巧妙的方法，我们可以求出每一个元素，它在序列中上一次出现的位置，如果这一个区间中所有元素上一次出现位置的最大值小于 $l$ ，那么一定没有重复元素。

因为数据范围很大，而且是强制在线，所以我们用 $map$ 套 $set$ 存一下，单点修改时注意下边界条件即可。

需要注意的是一个数的数列也算是等差数列，还有在 $d=0$ 时我们直接判断最大值是否等于最小值即可。

Code

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
152
153
154
155
#include<bits/stdc++.h>
#include<unordered_map>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 3e5+5;
int n,m,val[MAXN],opt,x,y,k,cnt,pre[MAXN];
unordered_map<int,set<int> > mp;
set<int>::iterator ite;
it gcd(int x,int y){return y==0?x:gcd(y,x%y);}
it max(int x,int y){return x>y?x:y;}
it min(int x,int y){return x<y?x:y;}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
	int mx,mn,mx_pre;
}T[MAXN<<2];
il pushup(int cur){
	T[cur].mn=min(T[lc].mn,T[rc].mn);
	T[cur].mx=max(T[lc].mx,T[rc].mx);
	T[cur].mx_pre=max(T[lc].mx_pre,T[rc].mx_pre);
}
il build_tree(int cur,int l,int r){
	if(l==r) return T[cur].mn=T[cur].mx=val[l],T[cur].mx_pre=pre[l],void();
	build_tree(lc,l,mid),build_tree(rc,mid+1,r);
	pushup(cur);
}
il updata(int cur,int l,int r,int pos,int k){
	if(l==r) return T[cur].mn=T[cur].mx=k,T[cur].mx_pre=pre[l],void();
	if(mid>=pos) updata(lc,l,mid,pos,k);
	else updata(rc,mid+1,r,pos,k);
	pushup(cur);
}
it query_mx(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[cur].mx;
	ri res=0;
	if(mid>=L) res=max(res,query_mx(lc,l,mid,L,R));
	if(R>mid) res=max(res,query_mx(rc,mid+1,r,L,R));
	return res;
}
it query_mn(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[cur].mn;
	ri res=INT_MAX;
	if(mid>=L) res=min(res,query_mn(lc,l,mid,L,R));
	if(R>mid) res=min(res,query_mn(rc,mid+1,r,L,R));
	return res;
}
it query_pre(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[cur].mx_pre;
	ri res=-1;
	if(mid>=L) res=max(res,query_pre(lc,l,mid,L,R));
	if(R>mid) res=max(res,query_pre(rc,mid+1,r,L,R));
	return res;
}
struct Tree{
	int d;
}T1[MAXN<<2];
int c[MAXN];
il build(int cur,int l,int r){
	if(l==r) return T1[cur].d=c[l],void();
	build(lc,l,mid),build(rc,mid+1,r);
	T1[cur].d=gcd(T1[lc].d,T1[rc].d);
}
il updata_d(int cur,int l,int r,int pos){
	if(l==r) return T1[cur].d=c[pos],void();
	if(mid>=pos) updata_d(lc,l,mid,pos);
	else updata_d(rc,mid+1,r,pos);
	T1[cur].d=gcd(T1[lc].d,T1[rc].d);
}
it query_d(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T1[cur].d;
	ri res=0;
	if(mid>=L) res=gcd(res,query_d(lc,l,mid,L,R));
	if(R>mid) res=gcd(res,query_d(rc,mid+1,r,L,R));
	return res;
}
it solve(int l,int r,int k){
	if(l==r) return 1;
	ri mx=query_mx(1,1,n,l,r),mn=query_mn(1,1,n,l,r),d=query_d(1,1,n-1,l,r-1),mx_pre=query_pre(1,1,n,l,r);
	if(mx-mn!=1ll*(r-l)*k) return 0;
	if(k&&mx_pre>=l) return 0;
	if(d!=k) return 0;
	return 1;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i) read(val[i]);
	for(ri i=1;i<n;++i) c[i]=abs(val[i+1]-val[i]);
	for(ri i=1;i<=n;++i){
		if(!mp[val[i]].size()) pre[i]=-1;
		else{
			ite=mp[val[i]].end();--ite;
			pre[i]=*ite;
		}
		mp[val[i]].insert(i);
	}
	build_tree(1,1,n),build(1,1,n-1);
	for(ri i=1;i<=m;++i){
		read(opt),read(x),read(y);
		x^=cnt,y^=cnt;
		if(opt==1){
			ite=mp[val[x]].find(x);
			if(ite!=mp[val[x]].end()) ++ite,pre[*ite]=pre[x],updata(1,1,n,*ite,val[*ite]);
			mp[val[x]].erase(x),val[x]=y;
			ite=mp[val[x]].lower_bound(x);
			if(ite!=mp[val[x]].end()) pre[*ite]=x,updata(1,1,n,*ite,val[*ite]);
			if(ite==mp[val[x]].begin()) pre[x]=-1;
			else --ite,pre[x]=*ite,mp[val[x]].insert(x);
			c[x]=abs(val[x+1]-val[x]),c[x-1]=abs(val[x]-val[x-1]);
			updata(1,1,n,x,y),updata_d(1,1,n-1,x);
			if(x-1) updata_d(1,1,n-1,x-1);
		}
		if(opt==2){
			read(k),k^=cnt;
			if(solve(x,y,k)) puts("Yes"),++cnt;
			else puts("No");
		}
	}
	return 0;
}

总结

这道题需要考虑到能构成等差数列的多种条件，而且边界需要特别注意，但是好像能用 $hash$ 乱搞过去。

就直接存一下区间最大，最小，区间和，元素的平方和，立方和，然后对于 $d$ ，我们根据最大值和最小值，算出以上的 $3$ 个值的 $hash$ 值，然后判断相等即可。