自动搬运

查看原文

来自洛谷，原作者为

	水星湖 菜

搬运于2025-08-24 23:12:56，当前版本为作者最后更新于2025-04-19 09:47:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设最终答案区间为 $[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;
}