【BZOJ4553】[HAOI2016&TJOI2016]序列
题面
题解
一定要仔细看题啊qwq。。。
我们设$mn[i],mx[i]$表示第$i$个位置上最小出现、最大出现的值。
则选出的序列要满足
$ i<j\ a[i]leq mn[j]\ mx[i]leq a[j] $
这™不就是个三维偏序吗？
一边$CDQ$一边$dp$就好了
注意分治时注意清空
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e5 + 5;
void chkmin(int &x, int y) { if (x > y) x = y; }
void chkmax(int &x, int y) { if (x < y) x = y; }
int N, a[MAX_N], mx[MAX_N], mn[MAX_N], f[MAX_N];
struct Node { int x, y, z, id; } t[MAX_N];
bool cmp_id (Node a, Node b) { return a.id < b.id; }
bool cmp_x (Node a, Node b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmp_y (Node a, Node b) { return a.y == b.y ? a.z < b.z : a.y < b.y; }
int c[MAX_N], M;
inline int lb(int x) { return x & -x; }
void add(int x, int v) { while (x <= M) chkmax(c[x], v), x += lb(x); }
int sum(int x) { int res = 0; while (x > 0) chkmax(res, c[x]), x -= lb(x); return res; }
void Set(int x) { while (x <= M) c[x] = 0, x += lb(x); }
void Div(int l, int r) {
if (l == r) return (void)chkmax(f[t[l].id], 1);
int mid = (l + r) >> 1;
Div(l, mid);
sort(&t[l], &t[mid + 1], cmp_x);
sort(&t[mid + 1], &t[r + 1], cmp_y);
for (int i = mid + 1, j = l; i <= r; i++) {
while (t[j].x <= t[i].y && j <= mid) add(t[j].z, f[t[j].id]), ++j;
chkmax(f[t[i].id], sum(t[i].x) + 1);
}
for (int i = l; i <= mid; i++) Set(t[i].z);
sort(&t[l], &t[r + 1], cmp_id);
Div(mid + 1, r);
}
int main () {
N = gi(), M = gi();
for (int i = 1; i <= N; i++) a[i] = mn[i] = mx[i] = gi();
while (M--) {
int x = gi(), y = gi();
chkmax(mx[x], y), chkmin(mn[x], y);
}
for (int i = 1; i <= N; i++) t[i] = (Node){a[i], mn[i], mx[i], i}, chkmax(M, mx[i]);
Div(1, N);
int ans = 0;
for (int i = 1; i <= N; i++) chkmax(ans, f[i]);
printf("%d
", ans);
return 0;
}