题解：P12127 [蓝桥杯 2024 省 B 第二场] 最强小队
dyc2022
·
·
题解
更好的阅读体验
感觉比较无脑的一道题，是为了锻炼代码能力才来的。
首先我们知道，如果确定了左右端点 l,r，那么我们就可以得出选出队伍的长度，即 (l,r) 区间中 < \min(l,r) 的数字个数加 2。
那么区间左右端点无非就两种情况，a_l < a_r 或 a_l \ge a_r，为了方便可以给第一种情况取个等号。
那么先考虑 a_l \ge a_r 的情况。我们可以枚举右端点，那么区间中的数字要满足的要求就仅和 a_r 的值有关。所以我们就想要让这个区间尽可能大，即找到最小的 i 使 a_i \ge a_r，线段树上二分即可。
对于实现，只需要写一个普通线段树维护区间最小值，再写一个主席树求区间中小于给定数的元素数量。那么就 $O(n \log^2 n)$ 的复杂度做完了，如果把二分搬到线段树上可以轻松一只 $\log$，但懒得写。
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 100006
using namespace std;
int n,a[N],b[N],bn,ans;
struct Segtree{int tree[N<<2];
void build(int p,int l,int r)
{
if(l==r)return tree[p]=a[l],(void)0;
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
tree[p]=max(tree[p<<1],tree[p<<1|1]);
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tree[p];
int mid=l+r>>1,ret=-1e15;
if(L<=mid)ret=max(ret,query(p<<1,l,mid,L,R));
if(R>mid)ret=max(ret,query(p<<1|1,mid+1,r,L,R));
return ret;
}}T1;
struct HJTtree{int tot,rt[N];
struct Node{int ls,rs,sum;}tree[N<<5];
void update(int &p,int q,int l,int r,int k)
{
tree[p=++tot]=tree[q],tree[p].sum++;
if(l==r)return;int mid=l+r>>1;
if(k<=mid)update(tree[p].ls,tree[q].ls,l,mid,k);
else update(tree[p].rs,tree[q].rs,mid+1,r,k);
}
int query(int p,int q,int l,int r,int L,int R)
{
if(L>R)return 0;
if(L<=l&&r<=R)return tree[p].sum-tree[q].sum;
int mid=l+r>>1,ret=0;
if(L<=mid)ret+=query(tree[p].ls,tree[q].ls,l,mid,L,R);
if(R>mid)ret+=query(tree[p].rs,tree[q].rs,mid+1,r,L,R);
return ret;
}}T2;
main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),b[++bn]=a[i];
if(n==1)return printf("1\n"),0;
sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+bn,a[i])-b;
T1.build(1,1,n);
for(int i=1;i<=n;i++)
T2.update(T2.rt[i],T2.rt[i-1],1,bn,a[i]);
for(int i=2;i<=n;i++)
{
int l=1,r=i-1,pos=0;
while(l<=r)
{
int mid=l+r>>1;
if(T1.query(1,1,n,1,mid)<a[i])
pos=mid,l=mid+1;
else r=mid-1;
}
pos++,ans=max(ans,T2.query(T2.rt[i-1],T2.rt[pos],1,bn,1,a[i]-1)+2);
}
for(int i=1;i<n;i++)
{
int l=i+1,r=n,pos=n+1;
while(l<=r)
{
int mid=l+r>>1;
if(T1.query(1,1,n,mid,n)<a[i])
pos=mid,r=mid-1;
else l=mid+1;
}
pos--,ans=max(ans,T2.query(T2.rt[pos-1],T2.rt[i],1,bn,1,a[i]-1)+2);
}
printf("%lld\n",ans);
return 0;
}
```