[AGC063] B - Insert 1, 2, 3, ...

[Q] https://atcoder.jp/contests/agc063/tasks/agc063_b

考察
・生成可能なパターンの始まりはいつも"1"から。
・なので1をもとにグルーピングしていく。

問題文サンプルを考える。
      10
      1 2 1 1 2 1 3 4 2 3 

 cnt: 1 0 2 3 0 4 0 0 0 0 
 pos: 0 0 2 3 3 5 3 3 2 2 
 add: 1 1 2 3 3 4 3 3 2 2 

pos: どの1と同じグループかを示す。
cnt: 値が1の時にだけ入れる。この1をとると、どれだけ全体の組み合わせ数が増えるかを示す。
add: この時点で解答にどれだけ追加したかを示す。

pos[val] = {index}とすると、この問題文サンプルは、次のようにグループわけできる。
pos[0] = {0, 1}
pos[2] = {2, 8, 9}
pos[3] = {3, 4, 6, 7}
pos[5] = {5}

・先頭から探索する。
A[i]を必ず使うとみなした場合、成立するパターン数を解答に加算する。

・A[i] = 1の場合を考える
{pair0}, {pair1}, 1
ときたら、このとき解答は+3される。
自分より前に、固まったグループがいくつあるかが分かればいい。
処理は、
1を{pair2}の先頭として
{pair0}, {pair1}, {pair2}
の集団とみなしていく。

・A[i] >= 2の場合を考える。

1. 
{1, 2, 3} {1}, 2
の場合。
{1, 2, 3},{1, 2}として統合される。
このとき解答は+2される。
自分を含めたグループの数が分かればいい。

2.
{1, 2} {1, 2, 3, 4}, 3
の場合。
{1, 2, 1, 2, 3, 4, 3}
の1つのグループに統合する必要がある。
この時解答は+1される。

3がどの時点の1とグルーピングされるか探索する必要がある。
セグ木で求まる。

Q. なぜ俺は11WAもしたのか？
A. 問題文にあるサンプルを網羅できていないことが、5分前に判明した。

問題文サンプルを考える。
      10
  A[]:1 2 1 1 2 1 3 4 2 3 
index:0 1 2 3 4 5 6 7 8 9

 cnt: 1 0 2 3 0 4 0 0 0 0 
 pos: 0 0 2 3 3 5 3 3 2 2 
 add: 1 1 2 3 3 4 3 3 2 2
                      ~~~ この、A[8] = 2 が、pos[8] = 2と結びついていることが大事。
A[8] = 2 について。
この2は、
A[2] = 1と結びつく必要がある。
しかし、
「最寄りの1と結びつける」というアルゴリズムにした場合、
A[5] = 1と結びついてしまう。
その場合、
A[3]以降を抜粋すると
1 2 1 3 4 2
a a b a a b
2つの連続部分列が絡み合っている数列とみなされて、NG文字列として扱ってしまう。
実際には正しい生成可能な文字列を得ることはできるはずなので、ペアリングの仕方が悪い。


どうやってA[5]とのマッチングを避けるか。

A[8]を探索しているときの、値1のindexリストは、
B[1] = {0, 2, 3, 5}

だが、ここでいくつかペア済みのindexがある。
A[0]はA[1]と{1,2}を形成しているので使用済み。
A[3]はA[4,6,7]と{1,2,3,4}を形成しているので使用済み。
そのため、
B[1] = {2, 5}
となっていてほしい。

indexの後ろからマッチングを試行する。

・index = 5のとき。
pos[5, 8)において、もっとも小さい値を見ると、
index: 5 6 7
  pos: 5 3 3
minIndex = 3となっている。
これは、A[8] = 2を、A[5] = 1と結びつけた場合、
その中間にA[3] = 1と結びついているグループが存在していることになる。
これは、2つの文字列を入り組ませたNG文字列と判定する。

どうなればいいかというと、
index == minIndexが成立すれば、正しい生成可能な文字列といえる。

まだB[1]の候補はあるので、次を調べる。
・index = 2 のとき。
pos[2, 8)において、もっとも小さい値を見ると、
index: 2 3 4 5 6 7
       2 3 3 5 3 3
minIndex = 2となっている。

これは、index == minIndexが成立するので、
index:0 1 2 3 4 5 6 7 8 9
  A[]:1 2{1 1 2 1 3 4 2}3 

[2, 8]のグルーピングを形成すればいい。

解答への加算は+2で、
{1 2}, {1 1 2 1 3 4 2} の2グループの取り方があるとみなせる。
cnt[2] = 2を加算すればいい。

実装

ll cnt0[500050]{};  // 値1の場所。この時点で完結している組み合わせ数
ll pos0[500050]{};  // どの値1と仲間か
ll add[500050]; // デバッグ用
vector<vector<ll>> B(500050, vector<ll>()); // B[val] = posindex

int main() {
  cincout();

  ll N;
  cin >> N;
  vector<ll> A(N);
  rep(i, N) cin >> A[i];

  RangeMin Z; // セグ木。範囲の最小indexを探す
  Z.init(500050);

  ll ans = 0; // 解答
  ll precnt = 0; // 1手前に解答をいくつ増やしたか。
  ll ng = -1; // 生成可能でない文字列が作られた場合、リセットする
  rep(i, N) {
    ll a = A[i];
    if (a == 1) {
      ++precnt;
      cnt0[i] = precnt;
      pos0[i] = i;
      ans += precnt;
      Z.update(i, i);  // id, val
    } else {
      auto failure = [&]() { // 生成可能でない数値が来た場合、リセットする
        ng = i;
        precnt = 0;
        Z.update(i, -1);
      };
      // 生成可能な数値かどうかテスト
      bool ok = true;
      ll b = 0;
      while (1) {
        if (B[a - 1].empty()) { // グループの末端値が(a-1)であるグループの存在確認
          ok = false;
          break;
        }
        b = B[a - 1].back(); // グルーピングを試行するindex
        if (b < ng) { // 生成可能でない数値をまたいでいるなら、生成不可
          ok = false;
          break;
        }
        B[a - 1].pop_back(); // 試行した値はもう使わないので除外
        ll pid = Z.query(pos0[b], i); // 範囲内に、より手前とペアリングしているグループがあってはいけない
        if (pid != pos0[b]) {  // pid == pos0[b]のはず
          continue; // 失敗なので、次のB[a-1]の値で再試行。
        }
        else break; // 成功
      }
      if (!ok){
        failure();
        continue;
      }

      Z.update(i, pos0[b]);  // id, val

      pos0[i] = pos0[b];
      precnt = cnt0[pos0[b]];
      ans += precnt;
    }
    add[i] = precnt;
    B[a].push_back(i);
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/agc063/submissions/44119608