Codeforces #602 Div1 B2. Optimal Subsequences

問題文が長くて読み返すのも疲れる。
http://codeforces.com/contest/1261/problem/B2

問題

整数列Aが与えられる。
クエリ(k,p)が与えられるので、順次以下を答えよ。
Aの部分列の中で長さkのうち、総和が最大で、かつその中で辞書順最小のものを考える。
その数列のp番目の要素を求めよ。

解法

クエリをkごとにまとめて処理する。
まずkに対して生成される数列がどうなるかを考える。
k=0から始めて、「Aの部分列に含まれてない要素のうち最大値(タイなら手前に登場するもの)が順次追加される」という形になる。
後はBITを二分探索するなどして、選択済みの要素のうちp番目のものを求めていけばよい。

int N,M;
int A[201010];
pair<int,int> P[202020];
vector<pair<int,int>> Q[202020];
int ret[202020];


template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bit;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[i]={-A[i],i};
	}
	sort(P,P+N);
	cin>>M;
	FOR(i,M) {
		cin>>k>>x;
		Q[k].push_back({i,x});
	}
	for(k=1;k<=N;k++) {
		x=P[k-1].second;
		bit.add(x,1);
		FORR(q,Q[k]) {
			y=bit.lower_bound(q.second);
			
			ret[q.first]=A[y];
		}
		
	}
	FOR(i,M) cout<<ret[i]<<endl;
	
	
	
}

まとめ

AといいBといいDiv1に来るぐらいの人には自明の内容をわざわざ説明してるので問題文長いんだな…。