jzoj6270. 【省赛模拟8.10】序列（吉司机线段树）_吉司机线段树复杂度

题目描述

Description

Input

Output

Sample Input
3
2 6 3

Sample Output
6

Data Constraint

题解

考虑一个数d的所有倍数，设为a[1]…a[k]
当k≥2时，在区间[1,a[k-1]-1]、[a[2]+1,n]、[a[1],a[k]]之间的区间的贡献都会对d取max
这个可以枚举d及其倍数来算，时间约为O(n ln n)（小于n log n）
证明${\sum }_{i=1}^n\frac{1}{i}\approx \ln (n)$，可见https://blog.csdn.net/gmh77/article/details/98226712

然后可以枚举左端点，同时维护区间和、支持区间取max
但是这样的话一般的线段树搞不了（增加量未知），所以要用吉司机线段树（%%%）

吉司机线段树

O(n log n)的时间复杂度是假的实际是O(n log²n)
http://jiry-2.blog.uoj.ac/blog/1404

基本思想：
对于每个区间（区间取max），维护最小值、最小值出现次数和次小值（初始为严格次小）
初始最小值为0，次小值为inf（因为不存在，若不为inf则时间会挂）
对于每次修改：
①修改值≤最小值
显然不用修改
②最小值<修改值≤次小值
把最小值修改即可
③次小值<修改值
暴力向下递归修改

中途修改时可能会出现最小值=次小值，则可以等到递归完子树（或者不递归）后再更新当前区间，正确性不变（前提是不要加奇怪的特判）

时间复杂度：O(n log²n)
（在实际操作中递归次数约为n log n级别，但由于常数较大，所以近似n log²n）
那么也就是可以卡成O(n log³n)
也可以当成O(玄)

code

注释部分及不需要加上的地方
因为如果最小=次小，那么新的区间也依然需要最小=次小，以便于向下求出真正的值

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define inf 2133333333
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;

struct type{
	int x,y,s;
} a[600001];
int A[200001][2];
int B[200001][2];
int sum[200001];
int S[200001][4];
int Sum[200001];
int tr[800001][4]; //0:1st minimal 1:number 2:2nd minimal 3:tag
long long Tr[800001]; //sum
int n,i,j,k,l,tot;
long long ans;

bool cmp(type a,type b)
{
	return a.x<b.x;
}

void add(int k,int i)
{
	++sum[k];
	
	if (i<A[k][0])
	{
		A[k][1]=A[k][0];
		A[k][0]=i;
	}
	else
	if (i<A[k][1])
	A[k][1]=i;
	
	if (i>B[k][0])
	{
		B[k][1]=B[k][0];
		B[k][0]=i;
	}
	else
	if (i>B[k][1])
	B[k][1]=i;
}

void Add(int x,int y,int s)
{
	++tot;
	a[tot].x=x;
	a[tot].y=y;
	a[tot].s=s;
}

void down(int t,int len)
{
	if (tr[t][3])
	{
		if (len>1)
		{
			tr[t*2][3]=max(tr[t*2][3],tr[t][3]);
			tr[t*2+1][3]=max(tr[t*2+1][3],tr[t][3]);
		}
		
		if (tr[t][3]>tr[t][0])
		{
			Tr[t]+=(long long)(tr[t][3]-tr[t][0])*tr[t][1];
			tr[t][0]=tr[t][3];
		}
		tr[t][3]=0;
	}
}

void up(int t)
{
	if (tr[t*2][0]<tr[t*2+1][0])
	{
		tr[t][0]=tr[t*2][0];
		tr[t][1]=tr[t*2][1];
		
//		if (tr[t*2][2]>tr[t*2][0])
		tr[t][2]=min(tr[t*2][2],tr[t*2+1][0]);
//		else
//		tr[t][2]=tr[t*2+1][0];
	}
	else
	if (tr[t*2][0]>tr[t*2+1][0])
	{
		tr[t][0]=tr[t*2+1][0];
		tr[t][1]=tr[t*2+1][1];
		
//		if (tr[t*2+1][2]>tr[t*2+1][0])
		tr[t][2]=min(tr[t*2][0],tr[t*2+1][2]);
//		else
//		tr[t][2]=tr[t*2][0];
	}
	else
	{
		tr[t][0]=tr[t*2][0];
		tr[t][1]=tr[t*2][1]+tr[t*2+1][1];
		
//		if (tr[t*2][2]>tr[t*2][0] && tr[t*2+1][2]>tr[t*2+1][0])
		tr[t][2]=min(tr[t*2][2],tr[t*2+1][2]);
//		else
//		if (tr[t*2][2]>tr[t*2][0])
//		tr[t][2]=tr[t*2][2];
//		else
//		if (tr[t*2+1][2]>tr[t*2+1][0])
//		tr[t][2]=tr[t*2+1][2];
//		else
//		tr[t][2]=inf;
	}
	
	Tr[t]=Tr[t*2]+Tr[t*2+1];
}

void change(int t,int l,int r,int x,int y,int s)
{
	int mid=(l+r)/2;
	
	if (t==1)
	down(t,r-l+1);
	
	if (x<=l && r<=y)
	{
		if (l==r)
		{
			tr[t][0]=max(tr[t][0],s);
			tr[t][1]=1;
			
			Tr[t]=max(Tr[t],s);
			
			down(t,r-l+1);
			return;
		}
		
		down(t*2,mid-l+1);
		down(t*2+1,r-(mid+1)+1);
		
		if (s>tr[t][0] && s<=tr[t][2])
		{
			tr[t][3]=max(tr[t][3],s);
			down(t,r-l+1);
		}
		else
		if (s>tr[t][2])
		{
			if (s>tr[t*2][0])
			change(t*2,l,mid,x,y,s);
			if (s>tr[t*2+1][0])
			change(t*2+1,mid+1,r,x,y,s);
			
			up(t);
		}
		
		return;
	}
	
	down(t*2,mid-l+1);
	down(t*2+1,r-(mid+1)+1);
	
	if (x<=mid && s>tr[t*2][0])
	change(t*2,l,mid,x,y,s);
	if (mid<y && s>tr[t*2+1][0])
	change(t*2+1,mid+1,r,x,y,s);
	
	up(t);
}

void mt(int t,int l,int r)
{
	int mid=(l+r)/2;
	
	tr[t][1]=r-l+1;
	tr[t][2]=inf;
	
	if (l==r)
	return;
	
	mt(t*2,l,mid);
	mt(t*2+1,mid+1,r);
}

long long find(int t,int l,int r,int x,int y)
{
	long long s=0;
	int mid=(l+r)/2;
	
	down(t,r-l+1);
	
	if (x<=l && r<=y)
	return Tr[t];
	
	if (x<=mid)
	s+=find(t*2,l,mid,x,y);
	if (mid<y)
	s+=find(t*2+1,mid+1,r,x,y);
	
	return s;
}

int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	
	fo(i,1,200000)
	{
		A[i][0]=200001;
		A[i][1]=200001;
	}
	
	scanf("%d",&n);
	fo(i,1,n)
	{
		scanf("%d",&j);
		
		++Sum[j];
		
		if (!S[j][0])
		S[j][0]=i;
		else
		if (!S[j][1])
		S[j][1]=i;
		
		S[j][3]=S[j][2];
		S[j][2]=i;
	}
	
	mt(1,1,n);
	
	fo(i,1,200000)
	{
		for (j=i; j<=200000; j+=i)
		if (Sum[j])
		{
			switch (Sum[j])
			{
				case 1:{
					add(i,S[j][0]);
					break;
				}
				case 2:{
					add(i,S[j][0]);
					add(i,S[j][2]);
					break;
				}
				case 3:{
					add(i,S[j][0]);
					add(i,S[j][1]);
					add(i,S[j][2]);
					break;
				}
				default:{
					add(i,S[j][0]);
					add(i,S[j][1]);
					add(i,S[j][2]);
					add(i,S[j][3]);
					break;
				}
			}
		}
	}
	
	fo(i,1,200000)
	if (sum[i]>=2)
	{
		if (B[i][1]>1)
		Add(1,B[i][1]-1,i);
		
		if (A[i][0]+1<B[i][0])
		Add(A[i][0]+1,B[i][0]-1,i);
		
		if (A[i][1]<n)
		Add(A[i][1]+1,n,i);
	}
	
	sort(a+1,a+tot+1,cmp);
	
	j=1;
	fo(i,1,n)
	{
		while (j<=tot && a[j].x==i)
		{
			change(1,1,n,a[j].x,a[j].y,a[j].s);
			++j;
		}
		
		if (i==1)
		ans+=find(1,1,n,i,n-2);
		else
		if (i==2)
		ans+=find(1,1,n,i,n-1);
		else
		ans+=find(1,1,n,i,n);
	}
	
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312