[ABC354F] Useless for LIS

· · 题解

题目

题目考察：树状数组，线段树，动态规划。
题意简述： 给你一个序列 \{a_n\}，求序列内有哪些数可能成为最长上升子序列的其一个元素。
注：最长上升子序列：\forall i\in[1,n),a_i<a_{i+1}。
数据范围：

我们都知道，最长上升子序列应该用 dp 写，设 \forall i\in[1,n]，f_i 表示以第 i 个数结尾的最长上升子序列的长度，那么：

f_i=\max_{j=0,a_j<a_i}^{i-1}(f_i)+1

这样复杂度是 O(n^2) 的，考虑优化。

我们知道树状数组（设其为 t）可以维护前缀极值，那么我们可以每算完一个 f_i 后，就把他存进对应的 t_{a_i} 中，我们就可以在 O(n\log_2n) 的复杂度中处理 f_i。
当然 a_i 是很大的，那么我们将其离散化，结果不变。

那么，我们得到了 f_i，若它在最长上升子序列里，有以下可能：

按上述模拟即可。
代码： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(int i=x;i<=y;++i) 
#define per(i,x,y) for(int i=x;i>=y;--i)
#define endl '\n'
#define fi first
#define se second
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int t,n,a[N],b[N],cnt,dp[N],mx[N],tot,ans[N],mxx;
struct BIT{
    int f[N];
    inl void init(){
        rep(i,1,cnt) f[i]=0;  
    }
    inl int lowbit(int x){
        return x&-x;
    }
    inl void add(int x,int k){
        while(x<=cnt){
            f[x]=max(f[x],k);
            x+=lowbit(x); 
        }
    }
    inl int getmax(int x){
        int mx=0;
        while(x){
            mx=max(mx,f[x]);
            x-=lowbit(x);
        }
        return mx;
    }
}bit; 
inl void solve(){
    bit.init();
    rep(i,1,mxx) mx[i]=0;
    rep(i,1,n) dp[i]=0;
    mxx=tot=0;
    cin>>n;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) b[i]=a[i];
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-b-1;
    rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    rep(i,1,n){
        dp[i]=bit.getmax(a[i]-1)+1;
        bit.add(a[i],dp[i]);
    }
    rep(i,1,n) mxx=max(mxx,dp[i]);
    per(i,n,1)
        if(dp[i]==mxx||mx[dp[i]+1]>a[i]){
            ans[++tot]=i;
            mx[dp[i]]=max(mx[dp[i]],a[i]);
        }
    sort(ans+1,ans+tot+1);
    cout<<tot<<endl;
    rep(i,1,tot) cout<<ans[i]<<' ';
    cout<<endl;
}
signed main(){
    fst;
    cin>>t;
    while(t--) solve();
    return 0;
}