【AtCoder】F - Common Prefixes / AtCoder Beginner Contest 213 - あめんばーどのバーチャル日記

500点にするにはむちゃくちゃ難しいけど600点かというと最近のインフレ的には少し簡単目。でも典型と言えば典型だからARCに持ってくと瞬殺されるのでABCにしか持ってけないねって感じ。
LCP気づいてからの解き方がいろいろありそうだったので自分の解き方書き溜め。

調べておくといいもの

接尾辞配列（Suffix Array：蟻本335p）
高さ配列（LCP Array : 蟻本339p）
スタックの応用（蟻本p298）

蟻本の方法をそれなりに把握していれば解けなくはない。

SuffixとLCP

Suffix ArrayとLCP Arrayを求める方法については蟻本はじめいろいろな所で書かれているので省略します。この問題はこちら知らないとまず解けません。最大S文字のN個の文字列のソートってO(SNlogN)だから普通にやると死んじゃう。私は理論だけ理解してライブラリ組んでませんでしたのでACL様様。
接尾辞の名の如く、尾から数えたものを見ていくと辞書順に並べやすくなるという事態が発生する。問題もi文字目以降からなる文字列とっているので、この瞬間に接尾と気づくとつよい。

スタックの応用

ではLCPを求めたがそこからどうやって類似度合計を求めるか。である。
ここでは自分自身による類似度は含めない。（f(Ai,Ai)で必ず自分の長さになる物）
ここで試しにサンプル2のSuffixとLCPの配列を見る。（便宜上最後に0を入れている）

1-i
1-ippi
4-issippi
0-ississippi
0-mississippi
1-pi
0-ppi
2-sippi
1-sissippi
3-ssippi
0-ssissippi

ここで最初の4行だけに注目してみる。

1-i
1-ippi
4-issippi
0-ississippi

この区間は全て一文字目がiで共通している区間であり、3と4はissiで共通している。
よくよく見ると最初のn文字が共通する区間というのは「LCPがn未満からn以上になった瞬間から、その後始めてn文字未満になるまでの末尾を含んだ区間」になる。
そして最初のn文字が共通している区間の長さがmだった場合、自分自身は含めていないのでm-1がこの長さmの区間全員分に含まれていくことになる。

3-1-i
3-1-ippi
3-4-issippi
3-0-ississippi

なので1文字目に関してこの区間は全員+3ができる。

3-1-i
3-1-ippi
6-4-issippi
6-0-ississippi

さらに、2～4文字目に関して共通してる区間に関しても+3×1でさらに+3されて6になる
これを愚直にやると往復分の計算量でO(N^2)になる。
でもこれは区間合計なのでいもす法で合計の増減を保存しておけばO(N)になる。

このプラスしている量って図解するとこうなるのである。

f:id:amentorimaru:20210809033630p:plain

要はできるだけ長い長方形を作れるようにした場合の長方形の面積が長方形の区間＋１この区間でプラスされる。
これは蟻本298pに紹介されているできるだけ大きい長方形を作る方法の応用で行ける。
ただしこの問題とは違い「スタックより1低いものが来たら、その左端はそこで打ち切り」ではなく「その低い場所まで削り取る」ことに注意。
図で言うなら右側の3本の場合、高さ2が来た後に高さ1が来ているが、まだ下半分は細長い長方形になれる可能性があるので、左の一本目が「高さ2から高さ1に削られた」と見ておいて保存しておく必要がある。

具体的には

整数ペアのスタックを用意し、(0,-1)とでも入れておく。前者が高さで、後者がインデックス
LCPをインデックス順に見ていき、スタック最後尾の高さよりも高いものが来た場合、その高さとインデックスをスタックに入れる
スタック最後尾の高さより低いものが来た場合、長方形を生成する。
1. スタックの最後尾が同じ高さになるまでスタックの最後尾を削り、左端までの距離×削った高さが面積になる
2. スタックの高さが狭義単調増加でなくなる場合は、その限界まで削って起き、スタックをポップする。
  1. ポップした後は次の最後尾でさらに削る
長方形を生成したインデックスの先端と末尾に、長方形の面積に応じたimosを記録しておく。

あとはimos法に従って合計を出しておく。
Suffix Arrayで順番が入れ替わっているのと、自分自身による類似度を入れておくことを忘れずに。

  ll n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> sfx = suffix_array(s);
  vector<int> lcp = lcp_array(s, sfx);
  lcp.push_back(0);

  vector<pair<ll,ll>> stack;  // ind, min
  stack.emplace_back(0, 0);
  VL imos(n + 1);

  REP(i, n) {
    if (lcp[i] > stack.back().second) {
      stack.emplace_back(i, lcp[i]);      
      continue;
    }
    while (1) {
      auto [bi, bm] = stack.back();
      if (lcp[i] >= bm)
        break;

      auto [bbi, bbm] = stack[stack.size() - 2];
      if (lcp[i] <= bbm) {
        ll len = bm - bbm;
        imos[bi] += (i - bi) * len;
        imos[i + 1] -= (i - bi) * len;
        stack.pop_back();
      }
      else {
        ll len = bm - lcp[i];
        imos[bi] += (i - bi) * len;
        imos[i + 1] -= (i - bi) * len;
        stack.back().second -= len;
      }
    }
  }

  vector<ll> sum(n);
  vector<ll> ans(n);

  sum[0] = imos[0];
  REP(i, n-1) 
    sum[i + 1] = sum[i] + imos[i + 1];
  
  REP(i, n) 
    ans[sfx[i]] = sum[i] + n - sfx[i];

  REP(i, n) 
    cout << ans[i] << endl;