VP 场切。
题意分析
二分答案
显然，条件 $b_j\geq p-\vert i-j\vert$ 成立的 $p$ 具有单调性。即若 $p=p_0$ 时该条件成立，则 $p<p_0$ 时也成立。
因此可以二分答案 $p$，取最大值即可。
线段树维护
$p$ 已经确定，那么便是判断条件。显然绝对值并不好处理，考虑拆开。
即需要满足条件：
\[\begin{cases} b_j+i-j\geq p&j<i\\ b_j\geq p &j=i\\ b_j-i+j\geq p&j>i \end{cases}\]容易发现 $j<i$ 的部分和 $i<j$ 的部分无关，因此考虑分开处理。对于每一个 $i$，包含 $a_i$ 的 $b$ 一定是左边一段，右边一段。两边可以分别求解一个最长的满足条件的子序列。如果这两个子序列加上 $a_i$ 本身合起来，长度大于等于 $n-k$，则说明这是一种合法的解。
问题就来到如何求解子序列。
先考虑左边的，设 $\textit{dp}_i$ 表示 $a_1,a_2,\cdots,a_i$ 中最长的合法子序列，且钦定此处的 $a_i$ 为上文限制条件中的 $i$。
为了与代码保持一致，记 $\textit{mid}$ 表示当前二分得到的 $p$。
线段树维护，初始时节点 $[i,i]$ 的值为 $\textit{mid}-i+1$。
求解 $\textit{dp}_i$ 时：
- 在线段树上二分，找到 $p$ 表示最左侧的小于等于 $\min(a_i,\textit{mid})$ 的位置。特别地，若不存在则记为 $+\infty$。
- 将线段树上的 $[p,n]$ 都增加 $1$，表示 $\textit{dp}_i$ 能够递推到这些位置。
- 此时：
- 若 $a_i<\textit{mid}$，表明 $i$ 不可能是上文限制条件中的 $i$，$\textit{dp}_i\leftarrow-\infty$。（其实任意值都可以。）
- 若 $a_i\geq\textit{mid}$，则 $\textit{dp}_i$ 即最右侧的最大值为 $\textit{mid}+1$ 的位置。特别地，若不存在则记为 $-\infty$。
反向再做一遍即可。最后判断相加是否大于等于 $n-k$ 即可。
AC 代码
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e5,K=2e5,V=1e9,inf=0x3f3f3f3f;
int n,k,a[N+1];
int Mid;
struct segTree{
struct node{
int l,r;
int tag,max,min;
}t[N<<2|1];
void up(int p){
t[p].max=max(t[p<<1].max,t[p<<1|1].max);
t[p].min=min(t[p<<1].min,t[p<<1|1].min);
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r){
t[p].max=t[p].min=Mid-l+1;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void down(int p){
if(t[p].tag){
t[p<<1].max+=t[p].tag;
t[p<<1].min+=t[p].tag;
t[p<<1].tag+=t[p].tag;
t[p<<1|1].max+=t[p].tag;
t[p<<1|1].min+=t[p].tag;
t[p<<1|1].tag+=t[p].tag;
t[p].tag=0;
}
}
void add(int p,int l,int r,int k){
if(l<=t[p].l&&t[p].r<=r){
t[p].max+=k;
t[p].min+=k;
t[p].tag+=k;
return;
}
down(p);
if(l<=t[p<<1].r){
add(p<<1,l,r,k);
}
if(t[p<<1|1].l<=r){
add(p<<1|1,l,r,k);
}
up(p);
}
int findL(int p,int x){
if(t[p].l==t[p].r){
if(t[p].min<=x){
return t[p].l;
}else{
return inf;
}
}
down(p);
if(t[p<<1].min<=x){
return findL(p<<1,x);
}else{
return findL(p<<1|1,x);
}
}
int findR(int p){
if(t[p].l==t[p].r){
if(t[p].max==Mid+1){
return t[p].l;
}else{
return -inf;
}
}
down(p);
if(t[p<<1|1].max==Mid+1){
return findR(p<<1|1);
}else{
return findR(p<<1);
}
}
}t;
bool check(int mid){
Mid=mid;
t.build(1,1,n);
static int dp[N+1];
for(int i=1;i<=n;i++){
int p=t.findL(1,min(a[i],mid));
if(p<=n){
t.add(1,p,n,1);
}
if(a[i]>=mid){
dp[i]=t.findR(1);
}
}
t.build(1,1,n);
for(int i=n;i>=1;i--){
int p=t.findL(1,min(a[i],mid));
if(p<=n){
t.add(1,p,n,1);
}
if(a[i]>=mid && t.findR(1)+dp[i]>=n-k){
return true;
}
}
return false;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int l=0,r=V;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout<<l<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
