2019杭电多校二 B Beauty Of Unimodal Sequence

大意: 给定序列, 求满足先增后减的最长的子序列, 输出字典序最大和最小的.

 

先求出以$i$开头递减的子序列最大长度$dp_0$以及以$i$开头先增后减的最长子序列$dp_1$.

这个可以很容易用树状数组优化到$O(nlogn)$.

然后分字典序最小和最大两问来求.

对于字典序最小的情况比较容易处理, 直接贪心, 从前往后遍历判断是否能选择当前位即可.

字典序最大的话就要判断当前位之后是否有能使答案不减的位置.

我的做法是把每一个$dp$值位置存进一个$vector$中, 并且维护一个前缀最大值以及前缀最小值, 具体看代码吧.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define pb push_back
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;

const int N = 1e6+10;
int n, a[N],b[N],dp[N][2];
int c0[N],c1[N],ANS;
void add0(int x, int v) {
	for (; x<=*b; x+=x&-x) c0[x]=max(c0[x],v);
}
int qry0(int x) {
	int r = 0;
	for (; x; x^=x&-x) r=max(r,c0[x]);
	return r;
}
void add1(int x, int v) {
	for (; x; x^=x&-x) c1[x]=max(c1[x],v);
}
int qry1(int x) {
	int r = 0;
	for (; x<=*b; x+=x&-x) r=max(r,c1[x]);
	return r;
}
int ans[N];
void solve1() {
	int mx = ANS, len = 0, pos = -1;
	int f = 0;
	REP(i,1,n) {
		if (!len) {
			if (dp[i][1]==mx) len=1,pos=i,ans[len]=i;
			continue;
		}
		if (a[i]==a[pos]) continue;
		if (a[i]>a[pos]) {
			if (!f&&dp[i][1]==mx-len||f&&dp[i][0]==mx-len) { 
				++len,pos=i,ans[len]=i;
			}
			continue;
		}
		if (dp[i][0]==mx-len) { 
			f = 1, ++len,pos=i,ans[len]=i;
		}
	}
	REP(i,1,len) { 
		if (i!=len) printf("%d ", ans[i]);
		else printf("%d\n",ans[i]);
	}
}
vector<pii> g0[N],g1[N];

int chk0(int L, int lst, int len) {
	if (g0[len].empty()) return 0;
	auto t = g0[len].back();
	if (g0[len].back().x==L) {
		g0[len].pop_back();
		if (g0[len].empty()) {
			g0[len].push_back(t);
			return 0;
		}
		if (g0[len].back().y<lst) {
			g0[len].push_back(t);
			return 1;
		}
		else {
			g0[len].push_back(t);
			return 0;
		}
	}
	if (g0[len].back().y<lst) return 1;
	return 0;
}
int chk1(int L, int lst, int len) {
	if (g1[len].empty()) return 0;
	auto t = g1[len].back();
	if (g1[len].back().x==L) {
		g1[len].pop_back();
		if (g1[len].empty()) {
			g1[len].push_back(t);
			return 0;
		}
		if (g1[len].back().y>lst) {
			g1[len].push_back(t);
			return 1;
		}
		else {
			g1[len].push_back(t);
			return 0;
		}
	}
	if (g1[len].back().y>lst) return 1;
	return 0;
}
void solve2() {
	REP(i,1,n) g0[i].clear(),g1[i].clear();
	PER(i,1,n) { 
		g0[dp[i][0]].pb(pii(i,a[i]));
		g1[dp[i][1]].pb(pii(i,a[i]));
	}
	int mx = ANS, len = 0, pos = -1;
	REP(i,1,mx) {
		for (int j=1; j<g0[i].size(); ++j) {
			g0[i][j].y = min(g0[i][j].y,g0[i][j-1].y);
		}
		for (int j=1; j<g1[i].size(); ++j) {
			g1[i][j].y = max(g1[i][j].y,g1[i][j-1].y);
		}
	}
	int f = 0;
	REP(i,1,n) {
		while (g1[mx-len].size()&&g1[mx-len].back().x<i) {
			g1[mx-len].pop_back();
		}
		while (g0[mx-len].size()&&g0[mx-len].back().x<i) {
			g0[mx-len].pop_back();
		}
		if (!len) {
			if (g1[mx].size()==1&&g1[mx].back().x==i) len=1,pos=i,ans[len]=i;
			continue;
		}
		if (a[i]==a[pos]) continue;
		if (f) {
			if (chk0(i,a[pos],mx-len)) continue;
		}
		else {
			if (chk1(i,a[pos],mx-len)) continue;
			if (chk0(i,a[pos],mx-len)) continue;
		}
		if (a[i]<a[pos]) f=1;
		++len,pos=i,ans[len]=i;
		if (len==mx) break;
	}
	REP(i,1,len) { 
        if (i!=len) printf("%d ", ans[i]);
        else printf("%d\n",ans[i]);
    } 
}

int main() {
	while (~scanf("%d", &n)) {
		REP(i,1,n) scanf("%d", a+i);
		REP(i,1,n) b[i]=a[i];
		sort(b+1,b+1+n);
		*b=unique(b+1,b+1+n)-b-1;
		REP(i,0,*b+5) c0[i]=c1[i]=0;
		REP(i,0,n+5) dp[i][0]=dp[i][1]=0;
		REP(i,1,n) a[i]=lower_bound(b+1,b+1+*b,a[i])-b;
		//dp[0] 为全递减
		//dp[1] 为递增再递减
		ANS = 0;
		PER(i,1,n) {
			if (a[i]!=1) dp[i][0] = qry0(a[i]-1);
			++dp[i][0];
			dp[i][1] = max(dp[i][0], qry1(a[i]+1)+1);
			add0(a[i],dp[i][0]);
			add1(a[i],dp[i][1]);
			ANS = max(ANS, dp[i][1]);
		}
		solve1();
		solve2();
	}
}
相关文章
相关标签/搜索