結果
| 問題 | No.2361 Many String Compare Queries |
| ユーザー |
 hashiryo
|
| 提出日時 | 2023-11-24 00:20:16 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 154 ms / 2,500 ms |
| コード長 | 18,665 bytes |
| コンパイル時間 | 3,578 ms |
| コンパイル使用メモリ | 249,964 KB |
| 実行使用メモリ | 80,464 KB |
| 最終ジャッジ日時 | 2024-09-26 08:25:59 |
| 合計ジャッジ時間 | 6,136 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 2 ms
5,376 KB |
| testcase_08 | AC | 116 ms
43,572 KB |
| testcase_09 | AC | 154 ms
56,680 KB |
| testcase_10 | AC | 139 ms
48,852 KB |
| testcase_11 | AC | 142 ms
80,332 KB |
| testcase_12 | AC | 144 ms
80,328 KB |
| testcase_13 | AC | 142 ms
80,464 KB |
| testcase_14 | AC | 126 ms
77,124 KB |
| testcase_15 | AC | 137 ms
77,124 KB |
ソースコード
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T>std::ostream &operator<<(std::ostream&,const std::vector<T>&);
template<class T>std::ostream &operator<<(std::ostream&,const std::set<T>&);
template<class T,class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<class T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
template<class T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<class T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
template <class T, class... Args> void debug__(const std::string &s, const T &a, const Args &...x) {std::cerr << BRIGHT_CYAN << s << COLOR_RESET << " = ";std::cerr << a;(std::cerr << ... << (std::cerr << ", ", x));std::cerr << func_LINE_FILE << '\n';}
#define debug(...) debug__(#__VA_ARGS__,__VA_ARGS__)
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?" [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on
template <class T, class F> class SparseTable {
std::vector<std::vector<T>> dat;
F f;
public:
SparseTable() {}
SparseTable(const std::vector<T> &v, const F &f): f(f) {
int n= v.size(), log= n > 1 ? 31 - __builtin_clz(n - 1) : 0;
dat.resize(log + 1), dat[0].assign(v.begin(), v.end());
for (int i= 0, I= 1, j; i < log; ++i, I<<= 1)
for (dat[i + 1].resize(j= dat[i].size() - I); j--;) dat[i + 1][j]= f(dat[i][j], dat[i][j + I]);
}
// [l, r)
T fold(int l, int r) const {
if (r == l + 1) return dat[0][l];
int k= 31 - __builtin_clz(r - l - 1);
return f(dat[k][l], dat[k][r - (1 << k)]);
}
};
template <class T> struct ListRange {
using Iterator= typename std::vector<T>::const_iterator;
Iterator bg, ed;
Iterator begin() const { return bg; }
Iterator end() const { return ed; }
size_t size() const { return std::distance(bg, ed); }
const T &operator[](int i) const { return bg[i]; }
};
template <class T> class CsrArray {
std::vector<T> csr;
std::vector<int> pos;
public:
CsrArray()= default;
CsrArray(const std::vector<T> &c, const std::vector<int> &p): csr(c), pos(p) {}
size_t size() const { return pos.size() - 1; }
const ListRange<T> operator[](int i) const { return {csr.cbegin() + pos[i], csr.cbegin() + pos[i + 1]}; }
};
class CartesianTree {
std::vector<std::array<int, 2>> rg, ch;
std::vector<int> par;
int rt;
public:
template <class Vec> CartesianTree(const Vec &a, bool is_min= 1): rg(a.size()), ch(a.size(), std::array{-1, -1}), par(a.size(), -1) {
const int n= a.size();
auto comp= [&](int l, int r) { return (is_min ? a[l] < a[r] : a[l] > a[r]) || (a[l] == a[r] && l < r); };
int st[n], t= 0;
for (int i= n; i--; rg[i][1]= (t ? st[t - 1] : n), st[t++]= i)
while (t && comp(i, st[t - 1])) ch[i][1]= st[--t];
for (int i= t= 0; i < n; rg[i][0]= (t ? st[t - 1] + 1 : 0), st[t++]= i++)
while (t && comp(i, st[t - 1])) ch[i][0]= st[--t];
for (int i= 0; i < n; ++i)
for (int b= 2; b--;)
if (ch[i][b] != -1) par[ch[i][b]]= i;
for (int i= 0; i < n; ++i)
if (par[i] == -1) rt= i;
}
std::array<int, 2> children(int i) const { return ch[i]; }
int parent(int i) const { return par[i]; }
int root() const { return rt; }
// [l,r)
std::array<int, 2> range(int i) const { return rg[i]; }
};
template <class Cost= void, bool weight= false> class Tree {
template <class D, class T> struct Edge_B {
int to;
T cost;
operator int() const { return to; }
};
template <class D> struct Edge_B<D, void> {
int to;
operator int() const { return to; }
};
using Edge= Edge_B<void, Cost>;
using C= std::conditional_t<std::is_void_v<Cost>, std::nullptr_t, Cost>;
std::vector<std::conditional_t<std::is_void_v<Cost>, std::pair<int, int>, std::tuple<int, int, Cost>>> es;
std::vector<Edge> g;
std::vector<int> P, PP, D, I, L, R, pos;
std::vector<C> DW, W;
public:
Tree(int n): P(n, -2) {}
template <class T= Cost> std::enable_if_t<std::is_void_v<T>, void> add_edge(int u, int v) { es.emplace_back(u, v), es.emplace_back(v, u); }
template <class T> std::enable_if_t<std::is_convertible_v<T, Cost>, void> add_edge(int u, int v, T c) { es.emplace_back(u, v, c), es.emplace_back(v, u, c); }
template <class T, class U, std::enable_if_t<std::conjunction_v<std::is_convertible<T, Cost>, std::is_convertible<U, Cost>>, std::nullptr_t> = nullptr> void add_edge(int u, int v, T c, U d) /* c:u->v, d:v->u */ { es.emplace_back(u, v, c), es.emplace_back(v, u, d); }
void build(int root= 0) {
size_t n= P.size();
I.resize(n), PP.resize(n), std::iota(PP.begin(), PP.end(), 0), D.assign(n, 0), L.assign(n, 0), R.assign(n, 0), pos.resize(n + 1), g.resize(es.size());
for (const auto &e: es) ++pos[std::get<0>(e)];
std::partial_sum(pos.begin(), pos.end(), pos.begin());
if constexpr (std::is_void_v<Cost>)
for (const auto &[f, t]: es) g[--pos[f]]= {t};
else
for (const auto &[f, t, c]: es) g[--pos[f]]= {t, c};
auto f= [&, i= 0, v= 0, t= 0](int r) mutable {
for (P[r]= -1, I[t++]= r; i < t; ++i)
for (int u: operator[](v= I[i]))
if (P[v] != u) P[I[t++]= u]= v;
};
f(root);
for (size_t r= 0; r < n; ++r)
if (P[r] == -2) f(r);
std::vector<int> Z(n, 1), nx(n, -1);
for (int i= n, v; i--;) {
if (P[v= I[i]] == -1) continue;
if (Z[P[v]]+= Z[v]; nx[P[v]] == -1) nx[P[v]]= v;
if (Z[nx[P[v]]] < Z[v]) nx[P[v]]= v;
}
for (int v: I)
if (nx[v] != -1) PP[nx[v]]= v;
for (int v: I)
if (P[v] != -1) PP[v]= PP[PP[v]], D[v]= D[P[v]] + 1;
for (int i= n; i--;) L[I[i]]= i;
for (int v: I) {
int ir= R[v]= L[v] + Z[v];
for (int u: operator[](v))
if (u != P[v] && u != nx[v]) L[u]= ir-= Z[u];
if (nx[v] != -1) L[nx[v]]= L[v] + 1;
}
if constexpr (weight) {
DW.resize(n), W.resize(n);
for (int v: I)
for (auto &[u, c]: operator[](v)) {
if (u != P[v]) DW[u]= DW[v] + c;
else W[v]= c;
}
}
for (int i= n; i--;) I[L[i]]= i;
}
size_t size() const { return P.size(); }
const ListRange<Edge> operator[](int v) const { return {g.cbegin() + pos[v], g.cbegin() + pos[v + 1]}; }
int depth(int v) const { return D[v]; }
C depth_w(int v) const {
static_assert(weight, "\'depth_w\' is not available");
return DW[v];
}
int to_seq(int v) const { return L[v]; }
int to_node(int i) const { return I[i]; }
int parent(int v) const { return P[v]; }
int head(int v) const { return PP[v]; }
int root(int v) const {
for (v= PP[v];; v= PP[P[v]])
if (P[v] == -1) return v;
}
bool connected(int u, int v) const { return root(u) == root(v); }
int lca(int u, int v) const {
for (;; v= P[PP[v]]) {
if (L[u] > L[v]) std::swap(u, v);
if (PP[u] == PP[v]) return u;
}
}
int la(int v, int k) const {
assert(k <= D[v]);
for (int u;; k-= L[v] - L[u] + 1, v= P[u])
if (L[v] - k >= L[u= PP[v]]) return I[L[v] - k];
}
int la_w(int v, C w) const {
static_assert(weight, "\'la_w\' is not available");
for (C c;; w-= c) {
int u= PP[v];
if (c= DW[v] - DW[u] + W[u]; w < c) {
int ok= L[v], ng= L[u] - 1;
for (int m; ok - ng > 1;) m= (ok + ng) / 2, (DW[v] - DW[I[m]] <= w ? ok : ng)= m;
return I[ok];
}
if (v= P[u]; v == -1) return u;
}
}
int jump(int u, int v, int k) const {
if (!k) return u;
if (u == v) return -1;
if (k == 1) return in_subtree(v, u) ? la(v, D[v] - D[u] - 1) : P[u];
int w= lca(u, v), d_uw= D[u] - D[w], d_vw= D[v] - D[w];
return k > d_uw + d_vw ? -1 : k <= d_uw ? la(u, k) : la(v, d_uw + d_vw - k);
}
int jump_w(int u, int v, C w) const {
static_assert(weight, "\'jump_w\' is not available");
if (u == v) return u;
int z= lca(u, v);
C d_uz= DW[u] - DW[z], d_vz= DW[v] - DW[z];
return w >= d_uz + d_vz ? v : w <= d_uz ? la_w(u, w) : la_w(v, d_uz + d_vz - w);
}
int dist(int u, int v) const { return D[u] + D[v] - D[lca(u, v)] * 2; }
C dist_w(int u, int v) const {
static_assert(weight, "\'dist_w\' is not available");
return DW[u] + DW[v] - DW[lca(u, v)] * 2;
}
// u is in v
bool in_subtree(int u, int v) const { return L[v] <= L[u] && L[u] < R[v]; }
int subtree_size(int v) const { return R[v] - L[v]; }
// half-open interval
std::array<int, 2> subtree(int v) const { return std::array{L[v], R[v]}; }
// sequence of closed intervals
template <bool edge= 0> std::vector<std::array<int, 2>> path(int u, int v) const {
std::vector<std::array<int, 2>> up, down;
while (PP[u] != PP[v]) {
if (L[u] < L[v]) down.emplace_back(std::array{L[PP[v]], L[v]}), v= P[PP[v]];
else up.emplace_back(std::array{L[u], L[PP[u]]}), u= P[PP[u]];
}
if (L[u] < L[v]) down.emplace_back(std::array{L[u] + edge, L[v]});
else if (L[v] + edge <= L[u]) up.emplace_back(std::array{L[u], L[v] + edge});
return up.insert(up.end(), down.rbegin(), down.rend()), up;
}
};
template <class String> struct SuffixArray {
String s;
std::vector<int> sa;
static inline std::vector<int> sa_is(const std::vector<int> &s, int K) {
const int n= s.size();
std::vector<char> t(n);
std::vector<int> bkt(K, 0), bkt_l(K), bkt_r(K), sa(n), p1;
t.back()= true;
for (int i= n; --i;)
if (t[i - 1]= (s[i - 1] < s[i] || (t[i] && s[i - 1] == s[i])); t[i] && !t[i - 1]) p1.push_back(i);
std::reverse(p1.begin(), p1.end());
const int n1= p1.size();
for (int i= n; i--;) ++bkt[s[i]];
for (int i= 0, sum= 0; i < K; ++i) sum+= bkt[i], bkt_r[i]= sum, bkt_l[i]= sum - bkt[i];
std::vector<int> s1(n1), sa1(n1);
std::fill_n(sa.begin(), n, -1), std::copy_n(bkt_r.begin(), K, bkt.begin());
for (int i= n1; i--;) sa[--bkt[s[p1[i]]]]= p1[i];
std::copy_n(bkt_l.begin(), K, bkt.begin());
for (int i= 0, j; i < n; ++i)
if ((j= sa[i] - 1) >= 0 && !t[j]) sa[bkt[s[j]]++]= j;
std::copy_n(bkt_r.begin(), K, bkt.begin());
for (int i= n, j; i--;)
if ((j= sa[i] - 1) >= 0 && t[j]) sa[--bkt[s[j]]]= j;
for (int i= 0, j= 0; i < n; ++i)
if (t[sa[i]] && sa[i] > 0 && !t[sa[i] - 1]) sa1[j++]= sa[i];
int name= 0;
for (int i= 0, prev= -1, j, pos; i < n1; ++i, sa[pos]= name - 1)
for (j= 0, pos= sa1[i];; ++j)
if (prev == -1 || s[pos + j] != s[prev + j] || t[pos + j] != t[prev + j]) {
prev= pos, ++name;
break;
} else if (j && ((t[pos + j] && !t[pos + j - 1]) || (t[prev + j] && !t[prev + j - 1]))) break;
for (int i= n1; i--;) s1[i]= sa[p1[i]];
if (name != n1) sa1= sa_is(s1, name);
else
for (int i= n1; i--;) sa1[s1[i]]= i;
std::copy_n(bkt_r.begin(), K, bkt.begin()), std::fill_n(sa.begin(), n, -1);
for (int i= n1; i--;) sa[--bkt[s[p1[sa1[i]]]]]= p1[sa1[i]];
for (int i= 0, j; i < n; ++i)
if ((j= sa[i] - 1) >= 0 && !t[j]) sa[bkt_l[s[j]]++]= j;
for (int i= n, j; i--;)
if ((j= sa[i] - 1) >= 0 && t[j]) sa[--bkt_r[s[j]]]= j;
return sa;
}
public:
SuffixArray(const String &S): s(S) {
std::vector<int> s_cpy(s.size() + 1);
if constexpr (std::is_convertible_v<String, std::string>) std::copy(s.begin(), s.end(), s_cpy.begin()), sa= sa_is(s_cpy, 128), sa.erase(sa.begin());
else {
auto v= s;
sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
for (int i= s.size(); i--;) s_cpy[i]= std::lower_bound(v.begin(), v.end(), s[i]) - v.begin() + 1;
sa= sa_is(s_cpy, v.size() + 1), sa.erase(sa.begin());
}
}
int operator[](int i) const { return sa[i]; }
size_t size() const { return sa.size(); }
auto begin() const { return sa.begin(); }
auto end() const { return sa.end(); }
// return {l,r} s.t. P is a prefix of S[sa[i]:] ( i in [l,r) )
// l == r if P is not a substr of S
// O(|P|log|S|)
std::pair<int, int> pattern_matching(const String &P) const {
const int n= s.size(), m= P.size();
if (n < m) return {0, 0};
auto f1= [&](int h) {
auto t= s.begin() + h;
for (int j= 0, e= std::min(n - h, m); j < e; ++j) {
if (t[j] < P[j]) return true;
if (t[j] > P[j]) return false;
}
return n - h < m;
};
auto f2= [&](int h) {
auto t= s.begin() + h;
for (int j= 0, e= std::min(n - h, m); j < e; ++j)
if (t[j] > P[j]) return false;
return true;
};
auto L= std::partition_point(sa.begin(), sa.end(), f1), R= std::partition_point(L, sa.end(), f2);
return {L - sa.begin(), R - sa.begin()};
}
};
struct LCPArray {
std::vector<int> rnk;
template <class String> LCPArray(const SuffixArray<String> &sa): rnk(sa.size()) {
const int n= sa.size(), log= n > 2 ? 31 - __builtin_clz(n - 2) : 0;
dat.resize(log + 1), dat[0].resize(n - 1);
auto &lcp= dat[0];
for (int i= n; i--;) rnk[sa[i]]= i;
for (int i= 0, h= 0; i < n; ++i) {
if (rnk[i] == n - 1) {
h= 0;
continue;
}
for (int j= sa[rnk[i] + 1]; i + h < n && j + h < n && sa.s[i + h] == sa.s[j + h];) ++h;
if ((lcp[rnk[i]]= h)) --h;
}
for (int i= 0, I= 1, j; i < log; ++i, I<<= 1)
for (dat[i + 1].resize(j= dat[i].size() - I); j--;) dat[i + 1][j]= std::min(dat[i][j], dat[i][j + I]);
}
int operator[](int i) const { return dat[0][i]; }
size_t size() const { return dat[0].size(); }
auto begin() const { return dat[0].begin(); }
auto end() const { return dat[0].end(); }
int operator()(int i, int j) const {
if (i == j) return rnk.size() - i;
auto [l, r]= std::minmax(rnk[i], rnk[j]);
if (r == l + 1) return dat[0][l];
int k= 31 - __builtin_clz(r - l - 1);
return std::min(dat[k][l], dat[k][r - (1 << k)]);
}
private:
std::vector<std::vector<int>> dat;
};
struct SuffixTree {
Tree<void> tree;
std::vector<std::tuple<int, int, int, int>> node;
std::vector<int> suf;
template <class String> SuffixTree(const SuffixArray<String> &sa, const LCPArray &lcp): tree(1), suf(sa.size()) {
const int n= sa.size();
node.emplace_back(0, n, 0, 0);
if (n == 1) {
tree= Tree<void>(2), tree.add_edge(0, 1), tree.build(), node.emplace_back(0, 1, 0, 1), suf[0]= 1;
return;
}
std::vector<std::tuple<int, int>> es;
CartesianTree ct(lcp);
auto dfs= [&](auto dfs, int p, int idx, int h) -> void {
auto [l, r]= ct.range(idx);
++r;
int hh= lcp[idx];
if (h < hh) es.emplace_back(p, node.size()), p= node.size(), node.emplace_back(l, r, h, hh);
auto [lch, rch]= ct.children(idx);
if (lch == -1) {
if (hh < n - sa[idx]) es.emplace_back(p, node.size()), suf[sa[idx]]= node.size(), node.emplace_back(idx, idx + 1, hh, n - sa[idx]);
else suf[sa[idx]]= p;
} else dfs(dfs, p, lch, hh);
if (rch == -1) {
if (hh < n - sa[idx + 1]) es.emplace_back(p, node.size()), suf[sa[idx + 1]]= node.size(), node.emplace_back(idx + 1, idx + 2, hh, n - sa[idx + 1]);
else suf[sa[idx + 1]]= p;
} else dfs(dfs, p, rch, hh);
};
if (int r= ct.root(); lcp[r] > 0) es.emplace_back(0, 1), node.emplace_back(0, n, 0, lcp[r]), dfs(dfs, 1, r, lcp[r]);
else dfs(dfs, 0, r, 0);
tree= Tree<void>(node.size());
for (auto [u, v]: es) tree.add_edge(u, v);
tree.build();
}
int size() const { return node.size(); }
auto &operator[](int i) const { return node[i]; }
auto begin() const { return node.begin(); }
auto end() const { return node.end(); }
int substr(int l) const { return suf[l]; }
int substr(int l, int n) const {
for (int v= suf[l], u, w;; v= w)
if (u= tree.head(v), w= tree.parent(u); w == -1 || std::get<3>(node[w]) < n) {
int ok= tree.to_seq(v), ng= tree.to_seq(u) - 1;
for (int m; ok - ng > 1;) m= (ok + ng) / 2, (n <= std::get<3>(node[tree.to_node(m)]) ? ok : ng)= m;
return tree.to_node(ok);
}
}
template <class String> std::string debug_output(const SuffixArray<String> &sa) const {
std::string res= "\n";
for (int i= 0; i < node.size(); ++i) {
auto [l, r, h, hh]= node[i];
res+= std::to_string(i) + ": (" + std::to_string(l) + "," + std::to_string(r) + "," + std::to_string(h) + "," + std::to_string(hh) + ") ";
res+= sa.s.substr(sa[l] + h, hh - h);
res+= "\n";
}
for (int i= 0; i < sa.size(); ++i) {
res+= " " + sa.s.substr(sa[i]) + "\n";
}
return res;
}
};
using namespace std;
namespace yukicoder2361 {
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N, Q;
cin >> N >> Q;
string S;
cin >> S;
SuffixArray sa(S);
LCPArray lcp(sa);
SuffixTree st(sa, lcp);
// debug(st.debug_output(sa));
int n= st.size();
vector<long long> sum(n);
for (int i= 0; i + 1 < n; ++i) {
auto [l, r, h, hh]= st[i];
sum[i + 1]= sum[i] + (long long)(r - l) * (hh - h);
}
while (Q--) {
int L, R;
cin >> L >> R, --L;
int len= R - L;
int v= st.substr(L, len);
auto [l, r, h, hh]= st[v];
cout << sum[v] + (long long)(r - l) * (len - h - 1) << '\n';
}
return 0;
}
}
signed main() {
yukicoder2361::main();
return 0;
}