66 lines
1.6 KiB
C++
66 lines
1.6 KiB
C++
#include <algorithm>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
const int kMaxn = 1e5 + 10;
|
|
const int kMaxv = 1e5;
|
|
int n, m;
|
|
int a[kMaxn], max_d[kMaxn], min_d[kMaxn];
|
|
int f[kMaxn], res, pos[kMaxn];
|
|
bool cmp_max_d(int a, int b) { return max_d[a] < max_d[b]; }
|
|
bool cmp_a(int x, int y) { return a[x] < a[y]; }
|
|
int val[kMaxn];
|
|
void Modify(int p, int v) {
|
|
for (; p <= kMaxv; p += p & (-p)) val[p] = max(val[p], v);
|
|
}
|
|
int Query(int p) {
|
|
int res = 0;
|
|
for (; p > 0; p -= p & (-p)) res = max(res, val[p]);
|
|
return res;
|
|
}
|
|
void Clear(int p) {
|
|
for (; p <= kMaxv; p += p & (-p)) val[p] = 0;
|
|
}
|
|
void CDQ(int L, int R) {
|
|
if (L == R) {
|
|
f[L] = max(f[L], 1);
|
|
return;
|
|
}
|
|
int M = (L + R) >> 1;
|
|
CDQ(L, M);
|
|
for (int i = L; i <= R; i++) pos[i] = i;
|
|
sort(pos + L, pos + M + 1, cmp_max_d);
|
|
sort(pos + M + 1, pos + R + 1, cmp_a);
|
|
int pl = L;
|
|
for (int pr = M + 1; pr <= R; pr++) {
|
|
while (pl <= M && max_d[pos[pl]] <= a[pos[pr]]) {
|
|
Modify(a[pos[pl]], f[pos[pl]]);
|
|
pl++;
|
|
}
|
|
f[pos[pr]] = max(f[pos[pr]], Query(min_d[pos[pr]]) + 1);
|
|
}
|
|
for (int i = L; i <= M; i++) Clear(a[i]);
|
|
CDQ(M + 1, R);
|
|
}
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
scanf("%d%d", &n, &m);
|
|
for (int i = 1; i <= n; i++) {
|
|
scanf("%d", &a[i]);
|
|
max_d[i] = a[i];
|
|
min_d[i] = a[i];
|
|
}
|
|
for (int i = 1; i <= m; i++) {
|
|
int x, y;
|
|
scanf("%d%d", &x, &y);
|
|
max_d[x] = max(max_d[x], y);
|
|
min_d[x] = min(min_d[x], y);
|
|
}
|
|
CDQ(1, n);
|
|
for (int i = 1; i <= n; i++) res = max(res, f[i]);
|
|
printf("%d\n", res);
|
|
return 0;
|
|
} |