专栏文章

题解：P12127

qqinsishi
P12127题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minillp2
此快照首次捕获于
2025/12/02 03:00
3 个月前
此快照最后确认于
2025/12/02 03:00
3 个月前
查看原文
不妨设选出最强小队序列序列左端点 ll 和右端点 rr，有 al≤ara_l \le a_r。
考虑枚举右端点 rr，在 rr 左侧找到一个 ll，对答案的贡献为：
g(l,r)=max⁡l<r∑i=l+1r−1[ai<al]g(l, r) = \max_{l<r}\sum_{i=l+1}^{r-1}[a_i< a_l]
我们对原序列进行离散化，然后开一颗值域线段树 TT。令：
T[x]=max⁡l<r, al=xg(l,r)T[x] = \max_{l<r,\, a_l=x} {g(l, r)}
对于一个 rr，我们就要查询：
max⁡T[1,ar]\max T[1, a_r]
当枚举的 rr 右移时，对于 al>ara_l > a_r，有：
g(l,r+1)←g(l,r)+1g(l, r+1) \leftarrow g(l, r) + 1
所以，我们要进行线段树区间加。
综上，我们枚举右端点 rr，对线段树进行 区间加 和 查询区间最大值。
然后对原序列进行翻转再计算一遍，求最大值即为答案。
CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10, inf = 1e9;
int raw[N], a[N];
int n, tot;
int t[N<<2], tag[N<<2];


void apply(int p, int v) {
    t[p] += v;
    tag[p] += v; 
}

void down(int p) {
    if (tag[p]) {
        apply(p<<1, tag[p]);
        apply(p<<1|1, tag[p]);
        tag[p] = 0;
    }
}

void build(int p, int l, int r) {
    t[p] = -inf; tag[p] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
}

void update(int p, int l, int r, int x, int v) {
    if (l == r) return t[p] = max(t[p], v), void();
    int mid = (l + r) >> 1; down(p);
    if (x <= mid) update(p<<1, l, mid, x, v);
    else update(p<<1|1, mid+1, r, x, v);
    t[p] = max(t[p<<1], t[p<<1|1]);
}

void update(int p, int l, int r, int L, int R, int v) {
    if (L > R) return;
    if (L <= l && r <= R) return apply(p, v), void();
    int mid = (l + r) >> 1; down(p);
    if (L <= mid) update(p<<1, l, mid, L, R, v);
    if (mid < R) update(p<<1|1, mid+1, r, L, R, v);
    t[p] = max(t[p<<1], t[p<<1|1]);
}

int query(int p, int l, int r, int L, int R) {
    if (L > R) return -inf;
    if (L <= l && r <= R) return t[p];
    int mid = (l + r) >> 1, res{-inf}; down(p);
    if (L <= mid) res = max(res, query(p<<1, l, mid, L, R));
    if (mid < R) res = max(res, query(p<<1|1, mid+1, r, L, R));
    return res;
}

int solve() {
    int res = 1;
    build(1, 1, n);
    for (int i=1; i<=n; ++i) {
        res = max(res, query(1, 1, n, 1, a[i])+2);
        update(1, 1, n, a[i]+1, n, 1);
        update(1, 1, n, a[i], 0);
    }
    return res;
}
 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i=1; i<=n; ++i) cin >> a[i], raw[++tot] = a[i];
    sort(raw+1, raw+tot+1);
    tot = unique(raw+1, raw+tot+1) - raw - 1;
    for (int i=1; i<=n; ++i) 
        a[i] = lower_bound(raw+1, raw+tot+1, a[i]) - raw;
    int t1 = solve();
    reverse(a+1, a+n+1);
    int t2 = solve();
    cout << max(t1, t2) << '\n';
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...