【线段树 单调栈】2021牛客暑期多校训练营2 A Arithmetic Progression
2021-08-27 15:02:00 # ACM

题链

题目解析

给定长度为 $n$ 的数组，问有多少个子区间排序后是等差数列，即条件 $\forall i \in (1,n),2a_i=a_{i-1}+a_{i+1},$ 为真 ；

对于序列 $b_i$，若其排序后是等差数列，则必有公差 $d = gcd(b_2-b_1,b_3-b_2,\dots )$；

于是问题转化为统计区间 $[L,R]$ 满足：
$$max(a[L\dots R]) - min(a[L\dots R]) = (r-l)*\vert gcd(\dots )\vert$$
枚举 $R$，结合单调栈维护 $max$ 以及 $min$，做区间修改；
对于不同的 $L$，$gcd$ 不同的分段只有 $log$ 段，在 $L$ 每次 $gcd$ 改变时做单点修改；
又
$$max(l,r) - min(l,r) - (r-l)*\vert gcd(\dots )\vert >= 0$$
于是统计线段树上的最小值以及出现的次数，就能得到枚举的这个 $R$ 下，满足条件的区间个数；

代码实现

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 1e18
	#define MS 100005

LL n,m;
LL a[MS];
struct node{
	LL mn;
	LL cnt;
	LL gcd;
	LL la;
}p[MS<<2];
LL sta[2][MS], tp[2];
LL ans;

void push_up(LL rt){
	if(p[ls].mn < p[rs].mn) p[rt].mn = p[ls].mn, p[rt].cnt = p[ls].cnt;
	else if(p[ls].mn > p[rs].mn) p[rt].mn = p[rs].mn, p[rt].cnt = p[rs].cnt;
	else p[rt].mn = p[ls].mn, p[rt].cnt = p[ls].cnt + p[rs].cnt;
	if(p[ls].gcd == p[rs].gcd) p[rt].gcd = p[ls].gcd;
	else p[rt].gcd = 0;
}

void push_down(LL rt){
	if(p[rt].la){
		p[ls].mn += p[rt].la; p[rs].mn += p[rt].la;
		p[ls].la += p[rt].la; p[rs].la += p[rt].la;
		p[rt].la = 0;
	}
}

void build(LL l,LL r,LL rt){
	p[rt] = {0,0,0,0};
	if(l == r){
		p[rt].cnt = 1;
		return;
	}
	LL m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
}

void modify_add(LL L,LL R,LL l,LL r,LL rt,LL val){
	if(L <= l && r <= R){
		p[rt].mn += val;
		p[rt].la += val;
		return;
	}
	LL m = l+r>>1;
	push_down(rt);
	if(m >= L) modify_add(L,R,l,m,ls,val);
	if(m <  R) modify_add(L,R,m+1,r,rs,val);
	push_up(rt);
}

void modify_gcd(LL L,LL R,LL l,LL r,LL rt,LL val){
	if(L <= l && r <= R && p[rt].gcd && (val%p[rt].gcd == 0)){
		p[rt].mn -= p[rt].gcd;
		p[rt].la -= p[rt].gcd;
		return;
	}
	if(l == r){
		LL t = p[rt].gcd;
		p[rt].gcd = __gcd(t,val);
		p[rt].mn += ( t*(R-l) - p[rt].gcd*(R-l+1) );
		return;
	}
	LL m = l+r>>1;
	push_down(rt);
	if(m >= L) modify_gcd(L,R,l,m,ls,val);
	if(m <  R) modify_gcd(L,R,m+1,r,rs,val);
	push_up(rt);
}

LL query(LL L,LL R,LL l,LL r,LL rt){
	if(L <= l && r <= R){
		if(p[rt].mn == 0) return p[rt].cnt;
		else return 0;
	}
	LL m = l+r>>1;
	push_down(rt);
	LL ans = 0;
	if(m >= L) ans += query(L,R,l,m,ls);
	if(m <  R) ans += query(L,R,m+1,r,rs);
	return ans;
}

void clear(){
	ans = 0;
	tp[0] = tp[1] = 0;
}

void solve(){
	cin >> n;
	build(1,n,1);
	for(LL i=1;i<=n;i++){
		cin >> a[i];
		// max 
		while(tp[0] && a[ sta[0][tp[0]] ] <= a[i]){
			modify_add(sta[0][tp[0]-1]+1,sta[0][tp[0]],1,n,1,-a[ sta[0][tp[0]] ]);
			tp[0]--;
		}
		modify_add(sta[0][tp[0]]+1,i,1,n,1, a[i]);
		sta[0][++tp[0]] = i;
		// min
		while(tp[1] && a[ sta[1][tp[1]] ] >= a[i]){
			modify_add(sta[1][tp[1]-1]+1,sta[1][tp[1]],1,n,1, a[ sta[1][tp[1]] ]);
			tp[1]--;
		} 
		modify_add(sta[1][tp[1]]+1,i,1,n,1,-a[i]);
		sta[1][++tp[1]] = i;
		// gcd
		if(i > 1) modify_gcd(1,i-1,1,n,1,abs(a[i]-a[i-1]));
		ans += query(1,i,1,n,1);
	}
	cout << ans << "\n";
	clear();
} 

int main() {
	ios::sync_with_stdio(false);
	LL ce;
	ce = 1;
	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/

Prev
2021-08-27 15:02:00 # ACM
Next