結果
問題 | No.2361 Many String Compare Queries |
ユーザー |
![]() |
提出日時 | 2023-06-23 23:51:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,500 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 2,142 ms |
コンパイル使用メモリ | 144,032 KB |
実行使用メモリ | 12,628 KB |
最終ジャッジ日時 | 2024-07-01 03:38:59 |
合計ジャッジ時間 | 3,966 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
#include <algorithm> #include <iostream> #include <numeric> #include <string> #include <utility> #include <vector> using namespace std; using lint = long long; using pint = pair<int, int>; #define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++) #define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) #include <atcoder/string> #include <atcoder/segtree> int op1(int l, int r) { return min(l, r); } int e1() { return 1 << 30; } int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, Q; string S; cin >> N >> Q >> S; const auto sa = atcoder::suffix_array(S); auto lcp = atcoder::lcp_array(S, sa); lcp.push_back(0); vector<lint> rcs(N); vector<pint> st; st.emplace_back(N - 1, 0); IREP(i, N - 1) { while (st.back().second > lcp.at(i)) st.pop_back(); rcs.at(i) = rcs.at(st.back().first) + lint(st.back().first - i) * lcp.at(i); st.emplace_back(i, lcp.at(i)); } vector<int> sainv(N, -1); REP(i, N) sainv.at(sa.at(i)) = i; vector<lint> cs(N + 1); REP(i, N) cs.at(i + 1) = cs.at(i) + (N - sa.at(i)); atcoder::segtree<int, op1, e1> lcptree(lcp); while (Q--) { int l, r; cin >> l >> r; --l; const int len = r - l; int b = lcptree.min_left(sainv.at(l), [&](int v) { return v >= len; }); lint ret = cs.at(b) + (len - 1); if (b < N and len > 1) { int bnxt = lcptree.max_right(b, [&](int v) { return v >= len - 1; }); ret += lint(len - 1) * (bnxt - b); if (bnxt < N) ret += rcs.at(bnxt); } cout << ret << '\n'; } }