题解：P15278 [MCO 2025] Subsequence
Little_Cake_qwq
·
·
题解
笑点解析：由于取整问题 WA 了 12 次。
但也至少是我第一次独立切蓝。
思路
设 f_i 表示以 a_i 为结尾的最长有效子序列长度，很明显有转移：
f_i=\max_{j=1}^{i-1}f_j+1
其中满足 a_i\times a_j\le x。时间复杂度 O(n^2)，需要优化。
考虑将状态变为：f_p 表示以 p 为结尾的最长有效子序列长度，则有转移：
f_{a_i}=\max f_j+1
其中 j\times a_i\le x。不难发现这个等价于 j\le 或 \ge\frac{x}{a_i}，所以假设我们把 \left[1,i-1\right] 按 a_i 排好序后，这个在区间 \left[1,i-1\right] 中出现的 j 的下标 pos 一定在一段区间中，具体在哪段区间分讨一下就可以了。
你刚刚提到了区间是吧！那咱们就可以用线段树维护 f_j，即可做到 O(n\log n) 的时间复杂度。
## 代码
```
const int N=1e5+8;
int n,x,ans,m;
int a[N],b[N];
struct seg_tree
{
int mx;
}t[N<<2];
void update(int o,int l,int r,int idx,int val)
{
if(l==r&&l==idx)
{
t[o].mx=max(t[o].mx,val);
return ;
}
int mid=(l+r)>>1;
if(mid>=idx) update(ls,l,mid,idx,val);
else update(rs,mid+1,r,idx,val);
t[o].mx=max(t[ls].mx,t[rs].mx);
}
int query(int o,int l,int r,int L,int R)
{
if(L>R) return 0;
if(L<=l&&r<=R) return t[o].mx;
int mid=(l+r)>>1;
int res=0;
if(mid>=L) res=max(res,query(ls,l,mid,L,R));
if(mid<R) res=max(res,query(rs,mid+1,r,L,R));
return res;
}
signed main()
{
n=read();x=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
{
int tmp,f=0;
if(a[i]>0)
{
tmp=upper_bound(b+1,b+m+1,x/a[i]-(x<0&&x%a[i]?1:0))-b-1;
f=query(1,1,m,1,tmp)+1;
}
else
{
tmp=lower_bound(b+1,b+m+1,x/a[i]+(x<0&&x%a[i]?1:0))-b;
f=query(1,1,m,tmp,m)+1;
}
int cur=lower_bound(b+1,b+m+1,a[i])-b;
update(1,1,m,cur,f);
ans=max(ans,f);
}
cout<<ans;
return 0;
}
```