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

· · 题解

设最终答案区间为 [l,r]，不妨设 a_l\le a_r，另一种情况把 a 反转一下就行了。

值域线段树维护考虑到第 i 个数时，a_j 后面小于 a_j 的数的个数，记作 f_j，对于每个 i 查询 \max_{a_j \le a_i} f_j，做完了。

#include <bits/stdc++.h>
using namespace std;

namespace z {

#define int long long
const int N = 1e5 + 5;
int a[N], b[N], n, ans = 1, vis[N];
struct SGT {
    #define lc (p<<1)
    #define rc (p<<1|1)
    #define mid ((l+r)>>1)
    int t[N << 2], mx[N << 2];
    void clear() { memset(t, 0, sizeof t), memset(mx, -0x3f, sizeof mx); }
    void pd(int p) {
        if(t[p]) {
            mx[lc] += t[p], mx[rc] += t[p];
            t[lc] += t[p], t[rc] += t[p];
            t[p] = 0;
        }
    }
    void pu(int p) { mx[p] = max(mx[lc], mx[rc]); }
    void upd(int p, int l, int r, int L, int R, int v) {
        if(l >= L && r <= R) {
            t[p] += v, mx[p] += v;
            return;
        }
        pd(p);
        if(mid >= L) upd(lc, l, mid, L, R, v);
        if(mid < R) upd(rc, mid + 1, r, L, R, v);
        pu(p);
    }
    int query(int p, int l, int r, int L, int R) {
        if(l >= L && r <= R) return mx[p];
        pd(p);
        int res = -0x3f3f3f3f3f3f3f3f;
        if(mid >= L) res = max(res, query(lc, l, mid, L, R));
        if(mid < R) res = max(res, query(rc, mid + 1, r, L, R));
        return res;
    }
} sgt;
void main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1); auto ed = unique(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, ed, a[i]) - b;
    sgt.clear();
    for(int i = 1; i <= n; i++) {
        int x = sgt.query(1, 1, n, 1, a[i]);
        ans = max(ans, x + 2);
        if(!vis[a[i]]) {
            vis[a[i]] = 1;
            sgt.upd(1, 1, n, a[i], a[i], -sgt.query(1, 1, n, a[i], a[i]));
        }
        sgt.upd(1, 1, n, a[i] + 1, n, 1);
    }
    memcpy(b, a, sizeof a);
    memset(vis, 0, sizeof vis);
    sgt.clear();
    for(int i = 1; i <= n; i++) a[i] = b[n - i + 1];
    for(int i = 1; i <= n; i++) {
        int x = sgt.query(1, 1, n, 1, a[i]);
        ans = max(ans, x + 2);
        if(!vis[a[i]]) {
            vis[a[i]] = 1;
            sgt.upd(1, 1, n, a[i], a[i], -sgt.query(1, 1, n, a[i], a[i]));
        }
        sgt.upd(1, 1, n, a[i] + 1, n, 1);
    }
    cout << ans << '\n';
}

#undef int

}

int main()
{
    z::main();
    return 0;
}