题解

这个我们处理出来每一位能变化到的最大值和最小值，包括自身

然后我们发现

\(f[i] = max(f[i],f[j] + 1) (mx[j] <= a[i] && a[j] <= mi[i])\)

喜闻乐见的三维偏序转移法

还写树套树？？？

直接CDQ分治就好啦

为啥他们的代码就1.xK？？？？？？

我就3.1K

代码

#include 
    
     #define enter putchar('\n')#define space putchar(' ')#define pii pair
     
      #define fi first#define se second#define MAXN 100005#define pb push_back#define mp make_pair#define eps 1e-8//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 + c - '0';        c = getchar();    }}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) out(x / 10);    putchar('0' + x % 10);}vector
        
          tr[MAXN * 4];int mx[MAXN],mi[MAXN],a[MAXN],N,M,f[MAXN],p[MAXN],tmp[MAXN],g[MAXN];int BIT[MAXN * 2];int lowbit(int u) {return u & -u;}void Insert(int u,int v) {    while(u <= 100000) {        BIT[u] = max(BIT[u],v);        u += lowbit(u);    }}int Query(int u) {    int res = 0;    while(u > 0) {        res = max(res,BIT[u]);        u -= lowbit(u);    }    return res;}void Clear(int u) {    while(u <= 100000) {        BIT[u] = 0;        u += lowbit(u);    }}bool cmp(int c,int d) {    return a[c] < a[d];}void build(int u,int l,int r) {    if(l == r) {tr[u].pb(l);return;}    int mid = (l + r) >> 1;    build(u << 1,l,mid);build(u << 1 | 1,mid + 1,r);    int s1 = 0,s2 = 0;    while(s1 < tr[u << 1].size() || s2 < tr[u << 1 | 1].size()) {        if(s2 >= tr[u << 1 | 1].size()) tr[u].pb(tr[u << 1][s1++]);        else if(s1 >= tr[u << 1].size() || a[tr[u << 1 | 1][s2]] < a[tr[u << 1][s1]]) tr[u].pb(tr[u << 1 | 1][s2++]);        else tr[u].pb(tr[u << 1][s1++]);    }}void Solve(int u,int l,int r) {    if(l == r) {return ;}    int mid = (l + r) >> 1;    Solve(u << 1,l,mid);    int s1 = l,s2 = 0,t;    while(s1 <= mid || s2 < tr[u << 1 | 1].size()) {        if(s2 >= tr[u << 1 | 1].size()) break;        if(s1 > mid || a[tr[u << 1 | 1][s2]] < mx[p[s1]]) {            t = tr[u << 1 | 1][s2];++s2;            f[t] = max(f[t],Query(mi[t]) + 1);        }        else {            Insert(a[p[s1]],f[p[s1]]);            ++s1;        }    }    for(int i = l ; i <= mid ; ++i) Clear(a[i]);    Solve(u << 1 | 1,mid + 1,r);    s1 = l,s2 = mid + 1,t = l;    while(s1 <= mid || s2 <= r) {        if(s2 > r) tmp[t++] = p[s1++];        else if(s1 > mid || mx[p[s1]] > mx[p[s2]]) tmp[t++] = p[s2++];        else tmp[t++] = p[s1++];    }    for(int i = l ; i <= r ; ++i) p[i] = tmp[i];    return;}void Init() {    read(N);read(M);    for(int i = 1 ; i <= N ; ++i) {read(a[i]);mi[i] = mx[i] = a[i];p[i] = i;f[i] = 1;}    int u,v;    for(int i = 1 ; i <= M ; ++i) {        read(u);read(v);        mi[u] = min(mi[u],v);        mx[u] = max(mx[u],v);    }    build(1,1,N);}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Init();    Solve(1,1,N);    int ans = 0;    for(int i = 1 ; i <= N ; ++i) ans = max(ans,f[i]);    out(ans);enter;    return 0;}