https://agc001.contest.atcoder.jp/tasks/agc001_f
わりと自然な考察で解けるからそんな難しくはないけど…でもおもしろいのは確か。
解説にあるとおりトポロジカル順を求めれば良いんですが以下はその具体的な方法です。
(i,A[i])のようにplotします。
[i,i+k)でyvに辺を張ります。こうしてできたグラフをGとします。
[i,v)でy<=A[i]を満たす点の個数をB[i]として、C[i]:=(B[i]+ΣD[child of i])として、CをG上で求めます。
あとは簡単です。bool値の配列Dを用意します。
i番目について、
Dを0から順番に見ていって、C[i]番目のfalseが入っているidxを出力する。
D[idx]をtrueにする。
を繰り返せば答えが得られます。配列DはBITで代用できて、C[i]番目を見つけるのもBIT特有の二分探索で合計O(NlogN)でできます。
コード中のBITは普通のBIT(0-origin)
BITBは二分探索機能付きBIT(1-origin)です。ややこしい。
int N, K; int G[MAX_N]; int A[MAX_N]; int D[MAX_N], F[MAX_N]; pi Q[MAX_N]; int loop(int v) { if(F[v] != -1) return F[v]; int res = D[v]; if(G[v] != v) { res += loop(G[v]); } return F[v] = res; } void solve() { cin >> N >> K; rep(i, 0, N) { cin >> A[i]; A[i]--; } set<pi> S; rep(i, 0, K) S.insert(pi(-A[i], i)); rep(i, 0, N) { auto it = S.upper_bound(pi(-A[i], i)); if(it == S.end()) { G[i] = i; Q[A[i]] = pi(i, i + 1); } else { G[i] = (*it).sec; Q[A[i]] = pi(i, G[i]); } S.erase(pi(-A[i], i)); if(i + K < N) S.insert(pi(-A[i + K], i + K)); } BIT bit(N); rep(i, 0, N) { bit.update(Q[i].fst, Q[i].fst + 1, 1); D[Q[i].fst] = bit.get(Q[i].fst, Q[i].sec); } memset(F, -1, sizeof(F)); rep(i, 0, N) loop(i); BITB bb(N); rep(i, 0, N) bb.update(i + 1, 1); rep(i, 0, N) { int a = bb.get_index(F[i]); cout << a << "\n"; bb.update(a, -1); } }