题解：P12127 [蓝桥杯 2024 省 B 第二场] 最强小队

· · 题解

P12127 [蓝桥杯 2024 省 B 第二场] 最强小队

首先题目要求要保持顺序，所以问题就是在序列内选两个数，贡献为他俩之间小于他俩的 a_i 值的人数，求最大。

计算小于某个数的数的数量，很明显是树状数组，但这道题权值的判断基准需要对左右端点取最小值否则无法确定，这样做必然要枚举端点，除非我们事先知道左右端点哪个大，只考虑以这个点为基准计算。

而且我们照着这样想就会发现，在保证右端点比左端点小的情况下，我们左端点会尽量往左取，毕竟多点数加进来比较绝对不是坏事。

于是现在要解决的问题就是，如何保证每次计算时左端点是大的那个，以及如何计算它能到的最右边的区间，以及如何计算这之间小于等于左端点的值的数的数量。

第一个和第二个比较好解决，就是先只枚举右端点，每次找到左边坐标最小且大于它的数，这个把 a 数组离散化，然后弄个前缀最大值数组二分一下就行。

第二个问题可以考虑把这几个需要计算的区间记录到左端点上，即对每个 i 建一个 vector ，记录以它为左端点的右端点有哪些，建完后从左往右扫，用树状数组算小于等于它的 a_i 的数有多少个（记为 s_i ），然后再算小于等于它的 vector 里面记录的右端点的 a_i 值的数有多少个(记为 s2_{i,j} )，它能做的贡献就是 s_i-s2_{l_i,i} ，一共调用 2\times n 次查找，复杂度 O(n \log n)

然后把序列倒过来再做一遍就行了。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define lowbit(x) x&(-x)
int a[MAXN],n,s[MAXN];
int c[MAXN],m,b[MAXN];
int mx[MAXN],ans,l[MAXN];
void add(int x)
{
    for(int i=x;i<=m;i+=lowbit(i))
        c[i]++;
}
int query(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
        sum+=c[i];
    return sum;
}
vector<int>p[MAXN];
int solve()
{
    for(int i=1;i<=n;i++)
        mx[i]=max(mx[i-1],a[i]);
    for(int i=1;i<=n;i++)
    {
        l[i]=lower_bound(mx+1,mx+1+i,a[i])-mx;
        s[i]=query(a[i]-1);
        add(a[i]);
        if(l[i]!=i)p[l[i]].push_back(i);
    }
    memset(c,0,sizeof(c));
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        for(auto now:p[i])
            ans=max(ans,s[now]-query(a[now]-1)+2);
        add(a[i]);
    }
    for(int i=1;i<=n;i++)
        p[i].clear();
    memset(c,0,sizeof(c));
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),
        b[i]=a[i];
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+m,a[i])-b;
    int ans=solve();
    reverse(a+1,a+1+n);
    printf("%d\n",max(ans,solve()));
    return 0;
}