Codeforces #567 Div2 D. Irrigation

まずいこれ３か月以上前の問題じゃないか。
https://codeforces.com/contest/1181/problem/D

問題

N個の町があり、過去コンテストの開催回数が与えられる。
これから何度もコンテストを行うわけだが、今後コンテストの開催地は以下の通り選ばれる。

• 今まで行った回数が最小の町のうち、最小の番号の町

Q個のクエリが与えられる。
各クエリでは、今からK回目のコンテストがどの町で行われるかを求めよ。

解法

過去の開催回数は各町500000以下である。
よって、全町の開催回数が500000に到達するまで、シミュレートしよう。
開催がx回目に並ぶタイミングでは、過去の開催回数がx回未満のものが開催対象になる。
その間に実行対象となるクエリに対しては、対象の町の数をBITやSegTreeで管理しておき、2分探索することで答えることができる。

それ以降は全町で順番に開催される。

int N,M,Q;
int C[505050];
vector<int> A[505050];
set<pair<ll,int>> S;

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> bt;

int ret[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&Q);
	FOR(i,N) {
		scanf("%d",&x);
		C[x]++;
	}
	for(i=1;i<=M;i++) A[C[i]].push_back(i);
	FOR(i,Q) {
		ll d;
		scanf("%" PRId64 ,&d);
		S.insert({d,i});
	}
	ll did=N;
	int tot=0;
	for(i=1;i<=500001;i++) {
		FORR(v,A[i-1]) bt.add(v,1), tot++;
		if(S.empty()) break;
		while(S.size() && S.begin()->first<=did+tot) {
			auto p=*S.begin();
			S.erase(S.begin());
			ret[p.second]=bt.lower_bound(p.first-did);
		}
		did+=tot;
	}
	while(S.size()) {
		auto p=*S.begin();
		S.erase(S.begin());
		ret[p.second]=(p.first-1-did)%M+1;
	}
	
	FOR(i,Q) _P("%d\n",ret[i]);
	
	
}

まとめ

CodeforcesのDiv2はこれ系の問題多い気がする。