本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-23 21:21:19

题目

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

• $1\le t,n,\sum n\le 2\times 10^5$
• $\forall i\in[1,n],1\le a_i\le 10^9$

我们都知道，最长上升子序列应该用 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$，若它在最长上升子序列里，有以下可能：

• $f_i=\max_{j=1}^n(f_j)$。
• $\max_{j=i+1}^n([f_j=f_i+1\land a_j>a_i])=1$

按上述模拟即可。
代码：

#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;
}