【线段树】算术天才⑨与等差数列

传送门:BZOJ4373


这道题思路还是比较简单的,不过和数学关系比较多,主要就是维护几个判定等差数列的条件

思路一

标准的方法貌似是:

  • 特判两种情况(k=0 或 l=r)
  • 维护区间最大最小值
  • 维护区间差分后的GCD值
  • 维护每一个数的前缀

然后由于已知的公差k:GCD=k,pre<l(意思是区间内没有重复),MAX-MIN=k(r-l)。

判断一下就好了

然后由于本渣写代码较菜,所以没写成(GG)

思路二

这个利用了一点hash的思想(或许可以证明,反正我不会)

  • 特判不能少

  • 维护区间最大最小值

  • 维护区间和

  • 维护区间平方和

然后,知道MIN和公差k,应该可以求出理想等差数列的区间最大值、区间和、区间平方和(不用long long,直接除法改乘法然后自然溢出即可)

然后如果这几项都一样(相当于hash的特征值一样),已知序列应该是等差数列。

另附等差数列平方和公式:

$\sum\limits_{i=1}^{n}{a_i}^2=(a_1)^2+(a_1+k)^2+(a_1+2k)^2+\ldots+(a_1+(n-1)\times k)^2=n\times(a_1)^2+a_1\times k\times n\times (n-1)+\frac{1}{6}\times k^2\times(n-1)\times n\times(n\times2-1)$

希望没有抄错


附上思路二的代码:

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
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
#define INF 2000000030
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
int n,m,op,x,y,l,r,k,tot,yes;
int a[1200030];
int ssum[1200030],Max[1200030],Min[1200030],sum[1200030];
char buf[40000020];
int bufpos;
inline void init(){
buf[fread(buf,1,40000020,stdin)]='\0';
bufpos=0;
}
inline int read(){
int p=0;
for(;!isdigit(buf[bufpos]);bufpos++);
for(;isdigit(buf[bufpos]);bufpos++)
p=p*10+buf[bufpos]-'0';
return p;
}
inline void update(int cur){
Max[cur]=max(Max[cur<<1],Max[cur<<1|1]);
Min[cur]=min(Min[cur<<1],Min[cur<<1|1]);
sum[cur]=sum[cur<<1]+sum[cur<<1|1];
ssum[cur]=ssum[cur<<1]+ssum[cur<<1|1];
}
void modify(int x,int y,int l,int r,int cur){
if (l==r){
Max[cur]=y; Min[cur]=y; sum[cur]=y; ssum[cur]=y*y;
return;
}
int mid=(l+r)>>1;
if (x<=mid) modify(x,y,l,mid,cur<<1);
if (x>mid) modify(x,y,mid+1,r,cur<<1|1);
update(cur);
}
void build(int l,int r,int cur){
if (l==r){
Max[cur]=a[l]; Min[cur]=a[l]; sum[cur]=a[l]; ssum[cur]=a[l]*a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
update(cur);
}
void q_all(int L,int R,int l,int r,int cur,int &MAX,int &MIN,int &SUM,int &SSUM){
if (L<=l && R>=r){
MAX=max(MAX,Max[cur]); MIN=min(MIN,Min[cur]); SUM+=sum[cur]; SSUM+=ssum[cur]; return;
}
int mid=(l+r)>>1;
if (L<=mid) q_all(L,R,l,mid,cur<<1,MAX,MIN,SUM,SSUM);
if (R>mid) q_all(L,R,mid+1,r,cur<<1|1,MAX,MIN,SUM,SSUM);
}
bool query(int L,int R,int k){
if (L==R) return 1;
int MAX=0,MIN=INF,SUM=0,SSUM=0,N=r-l+1;
q_all(L,R,1,n,1,MAX,MIN,SUM,SSUM);
if (k==0) return MAX==MIN;
return (MAX-MIN==k*(r-l)) && (SUM*2==(MIN+MAX)*N) && (SSUM*6==6*MIN*MIN*N+6*MIN*k*N*(N-1)+k*k*(N-1)*N*(N*2-1));
}
int main(){
init();
n=read(); m=read();
for (int i=1;i<=n;i++) a[i]=read();
build(1,n,1);
for (int i=1;i<=m;i++){
op=read();
if (op==1){
x=read()^yes; y=read()^yes;
a[x]=y;
modify(x,y,1,n,1);
}
if (op==2){
l=read()^yes; r=read()^yes; k=read()^yes;
if (query(l,r,k)){
puts("Yes");
yes++;
}
else puts("No");
}
}
return 0;
}