Description

有n个数，每个数有若干取值，但是只能在原数列的一个位置变换取值，求一个最长上升子序列，满足无论数列如何变化，这都是一个最长上升子序列。

Solution

记录 \(l[i],r[i]\) 分别表示 \(i\) 能取到的最大最小值，\(val[i]\) 为原数列。

我们来看看满足条件的二元组 \(i,j\) 满足什么条件。

1. \(i<j\)
2. \(val[i]<val[j]\)
3. \(r[i]<val[j]\)
4. \(val[i]<l[j]\)

观察到条件2包含在条件3，4里。

二维偏序问题，上CDQ就行。

Code

#include
    
     #include
     
      #include
      
       #include
       
        #define N 100005#define min(A,B) ((A)<(B)?(A):(B))#define max(A,B) ((A)>(B)?(A):(B))#define swap(A,B) ((A)^=(B)^=(A)^=(B))int f[N];int ans[N];int n,m,len;int last[N];struct Node{    int val,l,r,idx;}node[N];bool cmp(Node x,Node y){    return x.l
        
         =r) return;    int mid=l+r>>1;    cdq(l,mid);    std::sort(node+l,node+mid+1,cmp3);    std::sort(node+mid+1,node+r+1,cmp);    int a=l; memset(f,0,sizeof f);    for(int j=mid+1;j<=r;j++){        while(a<=mid and node[a].val<=node[j].l){            add(node[a].r,ans[node[a].idx]);            a++;        }        int p=query(node[j].val);        ans[node[j].idx]=max(ans[node[j].idx],p+1);    }    std::sort(node+l,node+r+1,cmp2);    cdq(mid+1,r);}signed main(){    n=getint(),m=getint();    for(int i=1;i<=n;i++){        ans[i]=1;        node[i].val=node[i].l=node[i].r=getint();        len=max(len,node[i].l);        node[i].idx=i;    }    for(int i=1;i<=m;i++){        int x=getint(),y=getint();        len=max(len,y);        node[x].r=max(node[x].r,y);        node[x].l=min(node[x].l,y);    }    cdq(1,n);    int maxn=0;    for(int i=1;i<=n;i++)        maxn=max(maxn,ans[i]);    printf("%d\n",maxn);    return 0;}