给你一个序列,每个数可能变化为另一个数,每次最多有一个数变化
求最长的子序列,无论如何变化,这个子序列都不下降
\(n \le 10^5\)
没想到是dp
设f[i]表示以i结尾的最长长度,有:
然后cdq直接搞一波,注意排序那里要魔改一下
#include #include #include #include #include #include #include #include #include #include #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=2e5+5,inf=1e9; int n,m,cnt,f[mxn],tr[mxn],hd[mxn]; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(int &x,int y) {if(xy) x=y;} struct ed { int to,nxt; }t[mxn<<1]; inline void add(int u,int v) { t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt; } struct Q { int val,mx,mi,id; }T[mxn]; int cmpv(Q x,Q y) { return x.val>1; cdq(l,mid); sort(T+l,T+mid+1,cmpm); sort(T+mid+1,T+r+1,cmpv); int pos=l; //这里写错了几次 for(int i=mid+1;i<=r;++i) { while(T[pos].mx<=T[i].val&&pos<=mid) mod(T[pos].val,f[T[pos].id],1),++pos; chkmax(f[T[i].id],query(T[i].mi)+1); } for(int i=l;i