Statement
给出 \(n\) 个数的序列 \(\{a_i\}\),接下来 \(m\) 秒中每一秒会有一个数发生变化,然后恢复。
问最长的子序列长度,使得任意时刻这个子序列不下降。\(n\le 10^5\)
Solution
设 \(b_i\) 为 \(i\) 最小能变成的数,\(c_i\) 为 \(i\) 最大能变成的数
\[ f(i)=\max_{j<i\land c_j\le a_i\land a_j\le b_i}\{f(j)\}+1 \]分治即可,\(O(n\log^2 n)\)
Code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 2e5 + 10;
int n, m, ans;
struct Item {
int a, b, c, f, id;
} a[N];
struct BIT {
int mx[N];
void Upd(int x, int v) {
for (; x <= 100000; x += x & -x) mx[x] = max(mx[x], v);
}
int Qry(int x) {
int res = 0;
for (; x; x -= x & -x) res = max(res, mx[x]);
return res;
}
void Clear(int x) {
for (; x <= 100000; x += x & -x) mx[x] = 0;
}
} bit;
void Solve(int l, int r) {
if (l == r) return (void)(ans = max(ans, a[l].f));
int mid = (l + r) >> 1;
Solve(l, mid);
sort(a + l, a + mid + 1, [&](Item l, Item r) { return l.c < r.c; });
sort(a + mid + 1, a + r + 1, [&](Item l, Item r) { return l.a < r.a; });
for (int j = l, i = mid + 1; j <= mid || i <= r; ) {
if (j <= mid && (a[j].c <= a[i].a || i > r)) {
bit.Upd(a[j].a, a[j].f), ++j;
} else {
a[i].f = max(a[i].f, bit.Qry(a[i].b) + 1), ++i;
}
}
rep(i, l, mid) bit.Clear(a[i].a);
sort(a + l, a + r + 1, [&](Item l, Item r) { return l.id < r.id; });
Solve(mid + 1, r);
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> m;
rep(i, 1, n) {
cin >> a[i].a, a[i].b = a[i].c = a[i].a, a[i].f = 1, a[i].id = i;
}
rep(i, 1, m) {
int x, y;
cin >> x >> y;
a[x].b = min(a[x].b, y), a[x].c = max(a[x].c, y);
}
Solve(1, n);
cout << ans << '\n';
return 0;
}
标签:P4093,int,题解,rep,mid,cin,Item,序列,id
From: https://www.cnblogs.com/laijinyi/p/18449765