回归第二题

求最长上升子序列并输出字典序最大
如果只求LIS的话，直接dp＋lower_bound即可
但是如果要记录字典序最大，那么就不能用dp了
重新引入两个数组
low[len]表示长度为len的LIS的结尾的数a[]
pos[i]表示以a[i]为结尾的LIS的长度

#include<bits/stdc++.h>
using namespace std;
int a[200005],pos[200005],low[200005],ans[200005];
int main(){
	int n,m,len=1,cnt=0;	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	pos[1]=1;low[1]=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]>low[len]){
			low[++len]=a[i];
			pos[i]=len;
		}
		else {
		int id=lower_bound(low+1,low+1+len,a[i])-low;
	   low[id]=a[i];
	   pos[i]=id;
		}
	}
	int maxx=1e9,tem=len;
//	cout<<len<<endl;
	for(int i=n;i>=1;i--){
		if(tem==0)break;
		if(pos[i]==tem&&maxx>a[i]){
			tem--,maxx=a[i];
			ans[++cnt]=i;
			m+=a[i];
			//cout<<a[i]<<endl;
		}
	}
	cout<<m<<endl<<len<<endl;
	for(int i=cnt;i>=1;i--)
	cout<<ans[i]<<endl;
	//cout<<maxx<<endl;
	return 0;
}