CF1530H Turing's Award

, ,

Turing’s Award

7.13 模拟赛 T4

https://www.luogu.com.cn/problem/CF1530H

Solution

覆盖很恶心，考虑倒序做。覆盖变成如果这个位置为空就一定要填，这个位置不为空则不操作。则加数操作一定在头尾。

则第一个限制是 $a_n$ 一定在序列里。

发现当前序列只需要维护 LIS。但是 $a_n$ 一定要在序列里，所以要讨论一下 $a_n$ 在不在 LIS 中。码到最后别忘了！！！

考虑如果当前已经有 $k$ 个数，上一个数加在序列的头部，如果再加一个数在头部没有限制；如果在尾部，则要满足 $j-i\ge k$。这是显然的。所以就可以转移了。

注意到序列是随机的，而一个经典结论是：随机序列的 LIS 长度为 $O(\sqrt n)$。可以把 LIS 长度放在状态之中。

令 $fl_{k,i}$ 表示当前 LIS 长度为 $k$，第 $k$ 个数为 $a_i$，$a_i$ 在 LIS 头部，尾部的最小值为 $fl_{k,i}$。$fr_{k,i}$ 表示 $a_i$ 在尾部，LIS 头部的最大值为 $fr_{k,i}$。

有转移:
$$
fl_{l+1,i}=\min{[a_i<a_j]f_{k,j},[fr_{k,j}>a_i,j-i\ge k]a_j}
$$
$fr_{k,i}$ 同理。发现操作是前后缀最小值最大值，用树状数组优化一下。

复杂度 $O(n\sqrt n \log n)$。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 20005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
const int base=300,inf=1e9;
int fl[base+5][maxn],fr[base+5][maxn];
int a[maxn],ans,n;
struct BITmin {
	#define lowbit(x) ((x)&(-x))
	int f[maxn];
	void clear(void) {memset(f,0x3f,sizeof(f));}
	void add(int x,int y) {for (;x<=n;x+=lowbit(x)) f[x]=min(f[x],y);}
	int query(int x) {int sum=inf;for (;x;x-=lowbit(x)) sum=min(sum,f[x]);return sum;}
}t1,t2;
struct BITmax {
	#define lowbit(x) ((x)&(-x))
	int f[maxn];
	void clear(void) {memset(f,0,sizeof(f));}
	void add(int x,int y) {for (;x<=n;x+=lowbit(x)) f[x]=max(f[x],y);}
	int query(int x) {int sum=0;for (;x;x-=lowbit(x)) sum=max(sum,f[x]);return sum;}
}t3,t4;
void solve(void) {
	int i,j,k;ans=0;
	read(n);
	for (i=1;i<=n;i++) read(a[i]);
	
	for (i=0;i<=n;i++) for (j=1;j<=base;j++) fl[j][i]=inf,fr[j][i]=0;
	for (i=1;i<=n;i++) fl[2][i]=fr[2][i]=a[i];
	for (k=2;k<=base;k++) {
		t1.clear(),t2.clear(),t3.clear(),t4.clear();
		for (i=n-1;i>=1;i--) {
			if (fl[k][i+1]<=n) t1.add(n-a[i+1]+1,fl[k][i+1]);
			if (n-i>=k&&fr[k][i+k]>=1) t1.add(n-fr[k][i+k]+1,a[i+k]);
			if (fr[k][i+1]>=1) t3.add(a[i+1],fr[k][i+1]);
			if (n-i>=k&&fl[k][i+k]<=n) t3.add(fl[k][i+k],a[i+k]);
			
			fl[k+1][i]=min(t1.query(n-a[i]),t2.query(n-a[i]));
			fr[k+1][i]=max(t3.query(a[i]-1),t4.query(a[i]-1));
		} 
		for (i=1;i<=n;i++) {
			if (1<=fl[k][i]&&fl[k][i]<=n) {
				ans=max(ans,k);
			}
			if (1<=fr[k][i]&&fr[k][i]<=n) {
				ans=max(ans,k);
			}
		}
	}
	ans--;
	for (i=0;i<=n;i++) for (j=1;j<=base;j++) fl[j][i]=inf,fr[j][i]=0;
	fl[1][n]=fr[1][n]=a[n];
	for (k=1;k<=base;k++) {
		t1.clear(),t2.clear(),t3.clear(),t4.clear();
		for (i=n-1;i>=1;i--) {
			if (fl[k][i+1]<=n) t1.add(n-a[i+1]+1,fl[k][i+1]);
			if (n-i>=k&&fr[k][i+k]>=1) t1.add(n-fr[k][i+k]+1,a[i+k]);
			if (fr[k][i+1]>=1) t3.add(a[i+1],fr[k][i+1]);
			if (n-i>=k&&fl[k][i+k]<=n) t3.add(fl[k][i+k],a[i+k]);
			
			fl[k+1][i]=min(t1.query(n-a[i]),t2.query(n-a[i]));
			fr[k+1][i]=max(t3.query(a[i]-1),t4.query(a[i]-1));
		} 
		for (i=1;i<=n;i++) {
			if (1<=fl[k][i]&&fl[k][i]<=n) {
				ans=max(ans,k);
			}
			if (1<=fr[k][i]&&fr[k][i]<=n) {
				ans=max(ans,k);
			}
		}
	}
	printf("%d\n",ans);
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}