結果

問題 No.2361 Many String Compare Queries
ユーザー SSRSSSRS
提出日時 2023-06-24 12:49:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 396 ms / 2,500 ms
コード長 6,688 bytes
コンパイル時間 2,525 ms
コンパイル使用メモリ 192,800 KB
実行使用メモリ 68,372 KB
最終ジャッジ日時 2024-07-01 15:47:57
合計ジャッジ時間 6,999 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 396 ms
51,252 KB
testcase_09 AC 390 ms
51,580 KB
testcase_10 AC 391 ms
51,060 KB
testcase_11 AC 321 ms
68,372 KB
testcase_12 AC 340 ms
68,332 KB
testcase_13 AC 336 ms
68,336 KB
testcase_14 AC 283 ms
56,252 KB
testcase_15 AC 290 ms
56,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
vector<int> suffix_array(const vector<int> &A, int mx){
  int N = A.size();
  vector<int> sum(mx + 1, 0);
  for (int i = 0; i < N; i++){
    sum[A[i] + 1]++;
  }
  for (int i = 0; i < mx; i++){
    sum[i + 1] += sum[i];
  }
  vector<bool> is_s(N);
  is_s[N - 1] = false;
  for (int i = N - 2; i >= 0; i--){
    is_s[i] = A[i] < A[i + 1] || A[i] == A[i + 1] && is_s[i + 1];
  }
  vector<int> id(N, -1);
  vector<int> pos;
  int M = 0;
  for (int i = 1; i < N; i++){
    if (is_s[i] && !is_s[i - 1]){
      id[i] = M;
      pos.push_back(i);
      M++;
    }
  }
  vector<int> sa(N);
  auto induce = [&](vector<int>& lms){
    sa = vector<int>(N, -1);
    vector<bool> used(N, false);
    vector<int> p(mx);
    vector<int> p2(mx);
    for (int i = 0; i < mx; i++){
      p[i] = sum[i + 1] - 1;
      p2[i] = sum[i];
    }
    for (int i = M - 1; i >= 0; i--){
      sa[p[A[lms[i]]]] = lms[i];
      p[A[lms[i]]]--;
      used[lms[i]] = true;
    }
    sa[p2[A[N - 1]]] = N - 1;
    p2[A[N - 1]]++;
    used[N - 1] = true;
    for (int i = 0; i < N; i++){
      if (sa[i] > 0){
        if (!is_s[sa[i] - 1] && !used[sa[i] - 1]){
          sa[p2[A[sa[i] - 1]]] = sa[i] - 1;
          p2[A[sa[i] - 1]]++;
          used[sa[i] - 1] = true;
        }
      }
    }
    for (int i = 0; i < N; i++){
      if (sa[i] != -1){
        if (id[sa[i]] != -1){
          used[sa[i]] = false;
          sa[i] = -1;
        }
      }
    }
    for (int i = 0; i < mx; i++){
      p[i] = sum[i + 1] - 1;
    }
    for (int i = N - 1; i >= 0; i--){
      if (sa[i] > 0){
        if (is_s[sa[i] - 1] && !used[sa[i] - 1]){
          sa[p[A[sa[i] - 1]]] = sa[i] - 1;
          p[A[sa[i] - 1]]--;
          used[sa[i] - 1] = true;
        }
      }
    }
  };
  induce(pos);
  if (M == 0){
    return sa;
  }
  vector<int> lms;
  for (int i = 0; i < N; i++){
    if (id[sa[i]] != -1){
      lms.push_back(sa[i]);
    }
  }
  vector<int> c(M);
  c[0] = 0;
  for (int i = 0; i < M - 1; i++){
    c[i + 1] = c[i];
    int x = lms[i];
    int y = lms[i + 1];
    bool ok = true;
    while (x < N && y < N){
      if (A[x] != A[y]){
        ok = false;
        break;
      }
      x++;
      y++;
      if (x == N || y == N){
        break;
      }
      if (id[x] != -1){
        if (id[y] == -1){
          ok = false;
        }
        break;
      }
    }
    if (x == N || y == N){
      ok = false;
    }
    if (!ok){
      c[i + 1]++;
    }
  }
  vector<int> rec(M);
  for (int i = 0; i < M; i++){
    rec[id[lms[i]]] = c[i];
  }
  vector<int> sa2 = suffix_array(rec, c[M - 1] + 1);
  vector<int> pos2(M);
  for (int i = 0; i < M; i++){
    pos2[i] = pos[sa2[i]];
  }
  induce(pos2);
  return sa;
}
vector<int> suffix_array(const string &S){
  int N = S.size();
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    A[i] = S[i];
  }
  return suffix_array(A, 256);
}
template <typename T>
vector<int> lcp_array(const T &A, vector<int> &SA){
  int N = A.size();
  vector<int> rank(N);
  for (int i = 0; i < N; i++){
    rank[SA[i]] = i;
  }
  vector<int> lcp(N - 1, 0);
  int h = 0;
  for (int i = 0; i < N; i++){
    if (rank[i] > 0){
      int prev = SA[rank[i] - 1];
      if (h > 0){
        h--;
      }
      while (i + h < N && prev + h < N){
        if (A[i + h] != A[prev + h]){
          break;
        }
        h++;
      }
      lcp[rank[i] - 1] = h;
    }
  }
  return lcp;
}
vector<int> cartesian_tree_min(vector<int> &A){
  int N = A.size();
  vector<int> pr(N, -1);
  stack<int> st;
  st.push(0);
  for (int i = 1; i < N; i++){
    int prev = -1;
    while (!st.empty()){
      int j = st.top();
      if (A[i] < A[j]){
        st.pop();
        if (prev != -1){
          pr[prev] = j;
        }
        prev = j;
      } else {
        break;
      }
    }
    if (prev != -1){
      pr[prev] = i;
    }
    st.push(i);
  }
  while (st.size() >= 2){
    int x = st.top();
    st.pop();
    pr[x] = st.top();
  }
  return pr;
}
struct suffix_array_tree{
  int root;
  vector<int> p, L, R, l, r;
  suffix_array_tree(string S){
    int N = S.size();
    vector<int> SA = suffix_array(S);
    vector<int> LCP = lcp_array(S, SA);
    p = cartesian_tree_min(LCP);
    p.resize(N * 2 - 1);
    L.resize(N * 2 - 1, -1);
    R.resize(N * 2 - 1, -1);
    for (int i = 0; i < N - 1; i++){
      if (p[i] == -1){
        root = i;
      } else {
        if (i < p[i]){
          L[p[i]] = i;
        }
        if (p[i] < i){
          R[p[i]] = i;
        }
      }
    }
    int cnt = 0;
    auto dfs = [&](auto dfs, int v) -> void {
      if (L[v] == -1){
        L[v] = N - 1 + SA[cnt];
        p[N - 1 + SA[cnt]] = v;
        cnt++;
      } else {
        dfs(dfs, L[v]);
      }
      if (R[v] == -1){
        R[v] = N - 1 + SA[cnt];
        p[N - 1 + SA[cnt]] = v;
        cnt++;
      } else {
        dfs(dfs, R[v]);
      }
    };
    dfs(dfs, root);
    l.resize(N * 2 - 1);
    r.resize(N * 2 - 1);
    for (int i = 0; i < N * 2 - 1; i++){
      if (i == root){
        l[i] = 1;
      } else {
        l[i] = LCP[p[i]] + 1;
      }
      if (i < N - 1){
        r[i] = LCP[i] + 1;
      } else {
        r[i] = N * 2 - i;
      }
    }
  }
};
int main(){
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  if (N == 1){
    for (int i = 0; i < Q; i++){
      cout << 0 << endl;
    }
  } else {
    suffix_array_tree T(S);
    vector<int> dp1(N * 2 - 1, 0);
    auto dfs1 = [&](auto dfs1, int v) -> void {
      if (v >= N - 1){
        dp1[v] = 1;
      }
      if (T.L[v] != -1){
        dfs1(dfs1, T.L[v]);
        dp1[v] += dp1[T.L[v]];
      }
      if (T.R[v] != -1){
        dfs1(dfs1, T.R[v]);
        dp1[v] += dp1[T.R[v]];
      }
    };
    dfs1(dfs1, T.root);
    long long curr = 0;
    vector<long long> dp2(N * 2 - 1, 0);
    auto dfs2 = [&](auto dfs2, int v) -> void {
      dp2[v] = curr;
      curr += (long long) dp1[v] * (T.r[v] - T.l[v]);
      if (T.L[v] != -1){
        dfs2(dfs2, T.L[v]);
      }
      if (T.R[v] != -1){
        dfs2(dfs2, T.R[v]);
      }
    };
    dfs2(dfs2, T.root);
    vector<vector<int>> pp(LOG, vector<int>(N * 2 - 1, -1));
    pp[0] = T.p;
    for (int i = 0; i < LOG - 1; i++){
      for (int j = 0; j < N * 2 - 1; j++){
        if (pp[i][j] != -1){
          pp[i + 1][j] = pp[i][pp[i][j]];
        }
      }
    }
    for (int i = 0; i < Q; i++){
      int l, r;
      cin >> l >> r;
      l--;
      int v = N - 1 + l;
      for (int j = LOG - 1; j >= 0; j--){
        if (pp[j][v] != -1){
          if (T.r[pp[j][v]] > r - l){
            v = pp[j][v];
          }
        }
      }
      cout << dp2[v] + (long long) dp1[v] * (r - l - T.l[v]) << endl;
    }
  }
}
0