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

线段树

传送门：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;
}