蓝桥杯省赛题目选解

[蓝桥杯 2022 省 A] 最长不下降子序列

Tag：dp,树状数组，离散化

题意

可以修改最多连续 \(k\) 个数为同一个数，求\(LIS\)长度。\(10^5\)。

题解

分别求出以 \(i\) 开头和结尾的 \(LIS\) 长度\(g[i],f[i]\)

最后拼接 \(g[i] + k + \max\limits_{a[j] \le a[i]}{f[j]}\)即可

//
// Created by blackbird on 2023/4/4.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, k, a[N], f[N], g[N];

struct Fenwick_Tree {   //树状数组维护前缀最大值
    int c[N];
    int add(int i, int x) {
        for (; i <= n; i += i & -i)
            c[i] = max(c[i], x);
    }
    int ask(int i) {
        int res = 0;
        for (; i; i -= i & -i)
            res = max(res, c[i]);
        return res;
    }
} F, G, T;

int work() { //离散化
    vector<int> vec;
    for (int i = 1; i <= n; i++) vec.push_back(a[i]);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for (int i = 1; i <= n; i++) a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
}



int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    work();
    a[0] = 1; a[n + 1] = n + 1;//注意：树状数组不能用下标0

    for (int i = 1; i <= n; i++) {
        f[i] = F.ask(a[i]) + 1;
        F.add(a[i], f[i]);
    }

    for (int i = n; i >= 1; i--) {
        g[i] = G.ask(n - a[i] + 1) + 1;
        G.add(n - a[i] + 1, g[i]);
    }
    int ans = 0;
    for (int i = k + 1; i <= n + 1; i++) {
        T.add(a[i - k - 1], f[i - k - 1]);
        ans = max(ans, T.ask(a[i]) + k + g[i]);
    }
    cout << ans << "\n";
    return 0;
}

[蓝桥杯 2013 省 B] 连号区间数

Tag: 线段树，单调栈

题意

给定一个排列，求满足\(\max\limits_{l\le i\le r} p_i-\min\limits_{l\le i\le r} p_i=r-l\)的子区间数量。\(5\times 10^4\)。

题解

设\(f_l=\max-\min + l-r\),显然 \(f\) 的最小值是 \(0\)。

考虑右端点 \(r\) 从 \(1\) 到 \(n\) 移动，维护区间 \([1,r]\) 的 \(f_l\) ，并查询最小值数量。

//
// Created by blackbird on 2023/4/4.
//
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int n, a[N];

struct tree {
    int min, add, cnt;
} tr[N << 2];

#define mid (l+r>>1)
#define ls (u<<1)
#define rs (u<<1|1)

void pushup(int u) {
    tr[u].min = min(tr[ls].min, tr[rs].min);
    tr[u].cnt = 0;
    if (tr[ls].min == tr[u].min) tr[u].cnt += tr[ls].cnt;
    if (tr[rs].min == tr[u].min) tr[u].cnt += tr[rs].cnt;
}
void pushdown(int u) {
    if (!tr[u].add) return;
    tr[ls].min += tr[u].add; tr[ls].add += tr[u].add;
    tr[rs].min += tr[u].add; tr[rs].add += tr[u].add;
    tr[u].add = 0;
}

void build(int l, int r, int u) {
    if (l == r) {
        tr[u].cnt = 1;
        return;
    }
    build(l, mid, ls); build(mid + 1, r, rs);
    pushup(u);
}

void add(int s, int t, int l, int r, int u, int k) {
    if (s > t) return;
    if (s <= l && t >= r) {
        tr[u].min += k;
        tr[u].add += k;
        return;
    }
    pushdown(u);
    if (s <= mid) add(s, t, l, mid, ls, k);
    if (t >= mid + 1) add(s, t, mid + 1, r, rs, k);
    pushup(u);
}

int query_cnt(int s, int t, int l, int r, int u) {
    if (s > t) return 0;
    if (s <= l && t >= r) {
        return tr[u].min == 0 ? tr[u].cnt : 0;
    }
    pushdown(u);
    int res = 0;
    if (s <= mid) res += query_cnt(s, t, l, mid, ls);
    if (t >= mid + 1) res += query_cnt(s, t, mid + 1, r, rs);
    return res;
}

int smx[N], smn[N], cmx, cmn;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, n, 1);

    int ans = 0;
    stack<int> mx, mn;//单调减/增栈
    for (int i = 1; i <= n; i++) {
        // mx - mn + l - r
        // r : += 1
        add(1, i - 1, 1, n, 1, -1);
        // mx: a[tp] -> a[i]
        while (!mx.empty() && a[mx.top()] <= a[i]) {
            int tp = mx.top(); mx.pop();
            int pre = mx.empty() ? 0 : mx.top();
            add(pre + 1, tp, 1, n, 1, a[i] - a[tp]);
        }
        mx.push(i);
        // mn: a[tp] -> a[i]
        while (!mn.empty() && a[mn.top()] >= a[i]) {
            int tp = mn.top(); mn.pop();
            int pre = mn.empty() ? 0 : mn.top();
            add(pre + 1, tp, 1, n, 1, a[tp] - a[i]);
        }
        mn.push(i);
        ans += query_cnt(1, i, 1, n, 1);
    }
    cout << ans << "\n";
    return 0;
}