[HEOI2016/TJOI2016]序列
\(\text{Solution}\)
明显有 \(DP\)
\[f_i = f_j + 1(j < i,Mx_j \le a_i,a_j \le Mn_i) \]然后 \(CDQ\) 分治即可
注意分治顺序
\(\text{Code}\)
#include
#include
#include
#define re register
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], Mx[N], Mn[N], f[N], p[N], len;
inline bool cmp_mx(int x, int y){return Mx[x] < Mx[y];}
inline bool cmp_a(int x, int y){return a[x] < a[y];}
struct BIT{
int c[N];
inline int lowbit(int x){return x & (-x);}
inline void add(int x, int v){for(; x <= len; x += lowbit(x)) c[x] = max(c[x], v);}
inline int query(int x){int res = 0; for(; x; x -= lowbit(x)) res = max(res, c[x]); return res;}
inline void clear(int x){for(; x <= len; x += lowbit(x)) c[x] = 0;}
}T;
void CDQ(int l, int r)
{
if (l == r) return void(f[l] = max(f[l], 1));
int mid = l + r >> 1;
CDQ(l, mid);
for(re int i = l; i <= r; i++) p[i] = i;
sort(p + l, p + mid + 1, cmp_mx), sort(p + mid + 1, p + r + 1, cmp_a);
int j = l - 1;
for(re int i = mid + 1; i <= r; i++)
{
for(; j < mid && Mx[p[j + 1]] <= a[p[i]]; ++j, T.add(a[p[j]], f[p[j]]));
f[p[i]] = max(f[p[i]], T.query(Mn[p[i]]) + 1);
}
for(re int i = l; i <= j; i++) T.clear(a[p[i]]);
CDQ(mid + 1, r);
}
int main()
{
scanf("%d%d", &n, &m);
for(re int i = 1, x; i <= n; i++) scanf("%d", &x), a[i] = Mn[i] = Mx[i] = x, len = max(len, x);
for(re int i = 1, x, y; i <= m; i++) scanf("%d%d", &x, &y), Mn[x] = min(Mn[x], y), Mx[x] = max(Mx[x], y);
CDQ(1, n); int ans = 1;
for(re int i = 1; i <= n; i++) ans = max(ans, f[i]);
printf("%d\n", ans);
}