[蓝桥杯 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;
}