Codeforces ECR #061 : G. Greedy Subsequences

割とめんどかった問題。　
https://codeforces.com/contest/1132/problem/G

問題

ある数列Cに対し、そのSubsequenceがGreedyであるとは、Subsequenceを抜き出す要素番号の列をPとしたとき、P[i]に対し、P[i+1]はP[i+1]＞P[i]かつC[P[i+1]]＞C[P[i]]である最小の物である、という条件を満たすものとする。

ここで長さNの数列Aが与えられる。
ここでは長さKの連続した部分列は(N-K+1)通りある。
それぞれに対し、最長のGreedyなSubsequenceの長さを求めよ。

解法

まず、P[i]を定めたときP[i+1]にくる値は一意に決まる。
これはRange Minimum Queryを用いてまず前処理として求めておこう。

次に、Aのうち部分列に対するGreedyなSubSequence長を求めていくわけだが、Sliding Windowの要領で値を更新していこう。
まず、各要素を初項とする最長のGreedyなSubSequence長を管理するSegTreeを持とう。
このSegTreeに対し、範囲加算・範囲最大値を求めることで、順次問題の解を得る。

今A[n...(n+k-1)]がSliding Windowであるとき、末尾を伸ばしA[n+k]を追加することを考えよう。
これにより、「各要素を初項とする最長のGreedyなSubSequence長」が1大きくなるものがあり得る。
とはいえ、こうなる要素は数列中で連続しているとは限らない。

ただ、この影響を与える関係を辺で結んでみると、この関係は木を成していることがわかる。
木の部分に対し一括で加算をしたい、となるとオイラーツアーを先行っておくことが考えられる。
よって、先にオイラーツアー順に頂点を並べ替えておくと、範囲加算・範囲最大値を求められるようになり、この問題に対応できる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;

static ll const def=-1<<20;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

SegTree_3<int,1<<20> st3;

int N,K;
int A[1010101];
int nex[1010101];
vector<int> E[1010101];
int L[1010101],R[1010101],id;

void dfs(int cur) {
	L[cur]=id++;
	FORR(e,E[cur]) dfs(e);
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&K);
	FOR(i,N) scanf("%d",&A[i]);
	st.update(1000001,N);
	for(i=N-1;i>=0;i--) {
		nex[i]=st.getval(A[i]+1,1000002);
		E[nex[i]].push_back(i);
		st.update(A[i],i);
	}
	dfs(N);
	FOR(i,N) {
		st3.update(L[i],R[i],1);
		if(i>=K) {
			st3.update(L[i-K],L[i-K]+1,-1<<20);
		}
		if(i>=K-1) {
			cout<<st3.ma[1]<<" ";
		}
	}
	
}

まとめ

思いつけて良かった。