题面
题解
(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
", 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
", ans);
return 0;
}