题目描述

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可 。

注意：每种变化最多只有一个值发生变化。在样例输入1中，所有的变化是：

1 2 3

2 2 3

1 3 3

1 1 3

1 2 4

选择子序列为原序列，即在任意一种变化中均为不降子序列在样例输入2中，所有的变化是:

3 3 3

3 2 3

选择子序列为第一个元素和第三个元素，或者第二个元素和第三个元素，均可满足要

输入输出格式

输入格式：

输入的第一行有两个正整数n, m，分别表示序列的长度和变化的个数。接下来一行有n个数，表示这个数列原始的状态。接下来m行，每行有2个数x, y，表示数列的第x项可以变化成y这个值。1 <= x <= n。

输出格式：

输出一个整数，表示对应的答案

输入输出样例

输入样例#1：

3 4

1 2 3

1 2

2 3

2 1

3 4

输出样例#1：

3

说明

对于20%数据所有数字均为正整数，且小于等于300

对于50%数据所有数字均为正整数，且小于等于3,000

对于100%数据所有数字均为正整数，且小于等于100,000

---

我们设\(maxv_i\)为第\(i\)个数变化的最大值;\(minv_i\)为第\(i\)个数变化的最小值,\(a_i\)位原来的数值

则题目要求转化为,求一个最长的序列,使一下条件满足

• \(j<i\)
• \(max(a_j,maxv_j) \le a_i\)
• \(a_j\le min(a_i,minv_i)\)

那这种不等式问题就能转化为二维数点问题

对于每一个j,我们每一次就可以在平面内加一个坐标为\((maxv_j,a_j)\)的权值为\(dp_j\)点,对于每一次转移,可以从\((0,0)\)到\((a_i,minv_i)\)中找到一个点权最大的点,当前点答案就是找到点的权值+1。

找点就能用很多数据结构维护,cdq分制树套树,k-d tree都可以,这里我用了树状数组套treap,相比于套动态开点线段树,平衡树比线段树空间更小,空间复杂度\(O(nlogn)\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int maxn=150000+23333;typedef long long ll;inline int read(){ int an=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){an=an*10+(ch^48);ch=getchar();} return an*f;}/*j
             
              
               
                
                 x)k=l[k]; else re=max(re,max(ma[l[k]],w[k])),k=r[k]; } return re; }\\前驱最大}t;struct BIT{ int root[maxn]; inline int query(int k,int x){ int re=0; for(;k;k-=k&-k) re=max(re,t.query(root[k],x)); return re; } inline void add(int k,int x,int val){ for(;k<=maxv;k+=k&-k)t.insert(root[k],x,val); }}T;int ans;int main(){ srand(233333); n=read();m=read(); for(int i=1;i<=n;i++)b[i]=c[i]=a[i]=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(); b[x]=min(b[x],y);c[x]=max(c[x],y); } for(int i=1;i<=n;i++)maxv=max(maxv,c[i]); for(int i=1;i<=n;i++){ int x=T.query(b[i],a[i]); dp[i]=x+1; T.add(a[i],c[i],dp[i]); ans=max(ans,dp[i]); } cout<
                
               
              
             
            
           
          
         
        
       
      
     
    

树套树就是一中思想,具体实现要靠自己领悟

---