RT，用最长上升子序列做的：

#include<bits/stdc++.h>
using namespace std;
string s[1000005],d[1000005],ans[1000005];
int pos[1000005];
int main(){
	int cnt=0;
	string S;
	cin>>S;
	for(int i=0;i<S.length();i++){
		if(S[i]>='A'&&S[i]<='Z'){
			cnt++;
		}
		s[cnt]+=S[i];
	}
	int len=1;
	d[len]=s[1];
	for(long long i=2;i<=cnt;i++){
		if(s[i]>d[len]){
			len++; 
			d[len]=s[i];
			pos[i]=len;
		}else{
			int qwq=lower_bound(d+1,d+1+len,s[i])-d;
			d[qwq]=s[i];
			pos[i]=qwq;
		}
	}
	string mx="";
	for(int i=cnt;i>=1;i--){
		if(len==0){
			break;
		}
		if(pos[i]==len){
			ans[len]=s[i];
			len--;
		}
	}
	for(int i=1;i<=cnt;i++){
		cout<<ans[i];
	}
}

WA on 4