[AGC038] B - Sorting a Segment
[Q] https://atcoder.jp/contests/agc038/tasks/agc038_b
考察
1. K要素をsetに入れておく。
2. indexを1個進めるときに、先頭をerase + 末端insertで遷移する。
遷移時にソートが発生するかどうかを見る。確認するのは2点。
a) 先頭をeraseしたときに、先頭要素に変化があるか
b) 新しいindexをinsertしたときに、末端要素に変化があるか
いずれかで変化するなら、ユニークなパターン。
3. もともと昇順に並んでいる組み合わせだけは、重複カウントを除く必要がある。
1, 2, 3, 6, 5, 4, 7, 8, 9
~~~~~~~ ~~~~~~~
123 を選んだ時と 789 を選んだ時は、同じパターン。
すでに昇順になっている箇所を選んだ回数を数えておく。
2回目以降をカウントしてはいけない。Q. 選んだK要素が昇順かどうかを知りたい
A. 増減データを押さえておけばいい
index:0 1 2 3 4 5 6 7 8 9
P[] = 2 0 1 3 7 5 4 6 8 9
dif: - + + + - - + + +
D[] = 0-1 0 1 2 1 0 1 2 3
P[1] ~ P[4] = 0 < 1 < 3 < 7 で昇順。
これは、D[4] - D[1] = 2 - (-1) = 3 == K - 1 // 4 - 1
[L, L+K) について、D[L+K] - D[L] == K - 1 なら昇順箇所とわかる。実装
ll P[200020];
ll D[200020]{};
int main() {
cincout();
ll N, K;
cin >> N >> K;
rep(i, N) cin >> P[i];
/*
2 0 1 3 7 5 4 6 8 9
- + + + - - + + +
0-1 0 1 2 1 0 1 2 3
*/
// 増減データDをinit
{
ll pre = P[0];
ll cur = 0;
for (ll i = 1; i < N; ++i) {
if (P[i] < pre)
--cur;
else if (P[i] > pre)
++cur;
pre = P[i];
D[i] = cur;
}
}
set<ll> S;
rep(i, K) { S.insert(P[i]); }
// 入れ替えに変化がなければ、未変化。
// 昇順だけの重複カウントはnatural
ll ans = 1;
// 最初に採用したものが昇順かどうか判定
ll natural = 0; // もともと昇順になっている箇所の数
if (D[K - 1] - D[0] == K - 1) ++natural;
for (ll i = K; i < N; ++i) {
bool is_change = false;
// 先頭の入れ替え。差異があるなら新パターン
if (*S.begin() != P[i - K]) is_change = true;
S.erase(S.find(P[i - K]));
S.insert(P[i]);
// 新入り。差異があるなら新パターン
if (*S.rbegin() != P[i]) is_change = true;
if (is_change) {
// すでに昇順になっているか
if (D[i] - D[i - K + 1] == K - 1) ++natural;
++ans;
}
}
// 昇順箇所が2回以上なら、重複パターンなのでのぞく
if (natural > 1) ans -= (natural - 1);
cout << ans << endl;
}