結果
| 問題 | No.2361 Many String Compare Queries |
| ユーザー |
 SSRS
|
| 提出日時 | 2023-06-23 22:36:31 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,537 bytes |
| コンパイル時間 | 2,588 ms |
| コンパイル使用メモリ | 191,724 KB |
| 実行使用メモリ | 73,032 KB |
| 最終ジャッジ日時 | 2024-07-01 02:20:33 |
| 合計ジャッジ時間 | 6,720 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 2 WA * 12 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:245:7: warning: 'root' may be used uninitialized [-Wmaybe-uninitialized]
245 | if (i != root){
| ^~
main.cpp:208:9: note: 'root' was declared here
208 | int root;
| ^~~~
ソースコード
#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;}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 {vector<int> SA = suffix_array(S);vector<int> LCP = lcp_array(S, SA);vector<int> p = cartesian_tree_min(LCP);vector<int> L(N - 1, -1), R(N - 1, -1);int root;for (int i = 0; i < N - 1; i++){if (p[i] == -1){root = i;} else {if (i < p[i]){L[p[i]] = i;}if (i > p[i]){R[p[i]] = i;}}}int V = N * 2 - 1;p.resize(V);L.resize(V, -1);R.resize(V, -1);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);vector<int> mn(V), mx(V);for (int i = 0; i < N * 2 - 1; i++){if (i != root){mn[i] = 1;} else {mn[i] = LCP[p[i]] + 1;}if (i < N - 1){mx[i] = LCP[i] + 1;} else {mx[i] = N - (i - (N - 1)) + 1;}}vector<int> dp1(V, 0);auto dfs1 = [&](auto dfs1, int v) -> void {if (v >= N - 1){dp1[v] = 1;}if (L[v] != -1){dfs1(dfs1, L[v]);dp1[v] += dp1[L[v]];}if (R[v] != -1){dfs1(dfs1, R[v]);dp1[v] += dp1[R[v]];}};dfs1(dfs1, root);long long curr = 0;vector<long long> dp2(V, 0);auto dfs2 = [&](auto dfs2, int v) -> void {dp2[v] = curr;curr += (long long) dp1[v] * (mx[v] - mn[v]);if (L[v] != -1){dfs2(dfs2, L[v]);}if (R[v] != -1){dfs2(dfs2, R[v]);}};dfs2(dfs2, root);vector<vector<int>> pp(LOG, vector<int>(V, -1));pp[0] = p;for (int i = 0; i < LOG - 1; i++){for (int j = 0; j < V; 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 (mx[pp[j][v]] >= r - l){v = pp[j][v];}}}cout << dp2[v] + (long long) dp1[v] * (r - l - mn[v]) << endl;}}}