洛谷 P4093 [HEOI2016/TJOI2016]序列（Cdq+dp）

题面

luogu

题解

\(Cdq分治+dp\)

\(mx[i],mn[i]\)分别表示第\(i\)位最大，最小能取到多少

那么有

\(j < i\)

\(mx[j] \le a[i]\)

\(a[j] \le mn[i]\)

然后就有了50分 \(O(n^2)\)的\(dp\)

上面那个东西是个三维偏序，

\(Cdq\)优化一下即可。

Code

50pts

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 100010;

int a[N];

int mx[N], mn[N], f[N];

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	int n, m; read(n); read(m);

	for (int i = 1; i <= n; i++) read(a[i]), mx[i] = mn[i] = a[i], f[i] = 1;

	for (int i = 1; i <= m; i++) {

		int x, y; read(x), read(y);

		mx[x] = max(mx[x], y);

		mn[x] = min(mn[x], y);

	}

	int ans = 0;

	for (int i = 2; i <= n; i++)

		for (int j = 1; j < i; j++)

			if (a[i] >= mx[j] && mn[i] >= a[j])

				f[i] = max(f[i], f[j]+1), ans = max(ans, f[i]);

	printf("%d\n", ans);

	return 0;

}

100pts

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 100010;

int a[N], b[N*4], tot, mx[N], mn[N];

int f[N], n, m;

int t[N], p[N];

#define lowbit(x) (x&(-x))

void add(int x, int k) {

	while (x <= tot) {

		t[x] = max(t[x], k);

		x += lowbit(x);

	}

	return ;

}

void clr(int x) {

	while (x <= tot) {

		t[x] = 0;

		x += lowbit(x);

	}

	return ;

}

int query(int x) {

	int s = 0;

	while (x) {

		s = max(s, t[x]);

		x -= lowbit(x);

	}

	return s;

}

inline bool cmp1(int i, int j) { return mx[i] < mx[j]; }

inline bool cmp2(int i, int j) { return a[i] < a[j]; }

void solve(int l, int r) {

	if (l == r) {

		f[l] = max(1, f[l]);

		return ;

	}

	int mid = (l + r) >> 1;

	solve(l, mid);

	for (int i = l; i <= r; i++)

		p[i] = i;

	sort(p+l, p+mid+1, cmp1); sort(p+mid+1, p+r+1, cmp2);

	for (int i = mid+1, j = l; i <= r; i++) {

		while (j <= mid && mx[p[j]] <= a[p[i]]) {

			add(a[p[j]], f[p[j]]);

			j++;

		}

		f[p[i]] = max(f[p[i]], query(mn[p[i]])+1);

	}

	for (int i = l; i <= mid; i++)

		clr(a[i]);

	solve(mid+1, r);

	return ;

}

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	read(n); read(m);

	for (int i = 1; i <= n; i++) {

		read(a[i]), mx[i] = mn[i] = a[i];

		b[++tot] = a[i];

	}

	for (int i = 1; i <= m; i++) {

		int x, y; read(x), read(y);

		mx[x] = max(mx[x], y);

		mn[x] = min(mn[x], y);

	}

	for (int i = 1; i <= n; i++) b[++tot] = mx[i], b[++tot] = mn[i];

	sort(b+1, b+1+tot);

	tot = unique(b+1, b+1+tot)-b-1;

	for (int i = 1; i <= n; i++) {

		a[i] = lower_bound(b+1, b+1+tot, a[i])-b;

		mx[i] = lower_bound(b+1, b+1+tot, mx[i])-b;

		mn[i] = lower_bound(b+1, b+1+tot, mn[i])-b;

	}

	solve(1, n);

	int ans = 0;

	for (int i = 1; i <= n; i++)

		ans = max(ans, f[i]);

	printf("%d\n", ans);

	return 0;

}

巴特西

洛谷 P4093 [HEOI2016/TJOI2016]序列（Cdq+dp）

题面

题解

Code

50pts

100pts

最新文章

热门文章