結果

問題 No.2361 Many String Compare Queries
ユーザー hashiryo
提出日時 2023-11-24 00:20:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 171 ms / 2,500 ms
コード長 18,665 bytes
コンパイル時間 3,469 ms
コンパイル使用メモリ 240,132 KB
最終ジャッジ日時 2025-02-17 23:31:47
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0