【BZOJ4553】[HAOI2016&TJOI2016]序列

时间：2023-03-09 09:04:03
【BZOJ4553】[HAOI2016&TJOI2016]序列

【BZOJ4553】[HAOI2016&TJOI2016]序列

题面

bzoj

洛谷

题解

一定要仔细看题啊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\n", ans);

	return 0;

}

相关文章