結果
問題 | No.2361 Many String Compare Queries |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-23 23:04:03 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,020 ms / 2,500 ms |
コード長 | 15,849 bytes |
コンパイル時間 | 4,305 ms |
コンパイル使用メモリ | 285,732 KB |
実行使用メモリ | 43,700 KB |
最終ジャッジ日時 | 2024-07-01 02:51:14 |
合計ジャッジ時間 | 11,961 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 998244353;// constexpr int MOD = 1000000007;constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U>inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U>inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;template <typename Band>struct SparseTable {using BinOp = std::function<Band(Band, Band)>;SparseTable() = default;explicit SparseTable(const std::vector<Band>& a, const BinOp bin_op) {init(a, bin_op);}void init(const std::vector<Band>& a, const BinOp bin_op_) {bin_op = bin_op_;const int n = a.size();assert(n > 0);lg.assign(n + 1, 0);for (int i = 2; i <= n; ++i) {lg[i] = lg[i >> 1] + 1;}const int table_h = std::countr_zero(std::bit_floor(a.size())) + 1;data.assign(table_h, std::vector<Band>(n));std::copy(a.begin(), a.end(), data.front().begin());for (int i = 1; i < table_h; ++i) {for (int j = 0; j + (1 << i) <= n; ++j) {data[i][j] = bin_op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);}}}Band query(const int left, const int right) const {assert(left < right);const int h = lg[right - left];return bin_op(data[h][left], data[h][right - (1 << h)]);}private:BinOp bin_op;std::vector<int> lg;std::vector<std::vector<Band>> data;};template <typename T = std::string>struct SuffixArray {std::vector<int> sa, rank;template <typename U = char>explicit SuffixArray(const T& s_, const U sentinel = 0) : s(s_) {const int n = s.size();s.push_back(sentinel);sa.resize(n + 1);std::iota(sa.rbegin(), sa.rend(), 0);std::ranges::stable_sort(sa, {}, [this](const int index) -> int { return s[index]; });rank.resize(n + 1);for (int i = 0; i <= n; ++i) {rank[i] = s[i];}std::vector<int> tmp(n + 1), prev_sa(n + 1);for (int len = 1; len <= n; len <<= 1) {tmp[sa[0]] = 0;for (int i = 1; i <= n; ++i) {if (rank[sa[i - 1]] == rank[sa[i]] && sa[i - 1] + len <= n &&rank[sa[i - 1] + (len >> 1)] == rank[sa[i] + (len >> 1)]) {tmp[sa[i]] = tmp[sa[i - 1]];} else {tmp[sa[i]] = i;}}rank.swap(tmp);std::iota(tmp.begin(), tmp.end(), 0);std::copy(sa.begin(), sa.end(), prev_sa.begin());for (int i = 0; i <= n; ++i) {const int idx = prev_sa[i] - len;if (idx >= 0) sa[tmp[rank[idx]]++] = idx;}}for (int i = 0; i <= n; ++i) {rank[sa[i]] = i;}}std::vector<int> match(T* t) const {const int lb = lower_bound(t);++t->back();const int ub = lower_bound(t);--t->back();std::vector<int> res(ub - lb);std::copy(sa.begin() + lb, sa.begin() + ub, res.begin());std::sort(res.begin(), res.end());return res;}private:T s;int lower_bound(const T* t) const {const int s_size = s.size(), t_size = t->size();int lb = 0, ub = s_size;while (ub - lb > 1) {const int mid = std::midpoint(lb, ub);int s_idx = sa[mid], t_idx = 0;bool finished = false;for (; s_idx < s_size && t_idx < t_size; ++s_idx, ++t_idx) {if (s[s_idx] != (*t)[t_idx]) {(s[s_idx] < (*t)[t_idx] ? lb : ub) = mid;finished = true;break;}}if (!finished) (s_idx == s_size && t_idx < t_size ? lb : ub) = mid;}return ub;}};template <typename T = std::string>struct LongestCommonPrefix : SuffixArray<T> {std::vector<int> lcp_array;explicit LongestCommonPrefix(const T& s) : SuffixArray<T>(s) {const int n = s.size();lcp_array.resize(n);for (int i = 0, common = 0; i < n; ++i) {const int j = this->sa[this->rank[i] - 1];if (common > 0) --common;while (i + common < n && j + common < n &&s[i + common] == s[j + common]) {++common;}lcp_array[this->rank[i] - 1] = common;}st.init(lcp_array, [](const int a, const int b) -> int {return std::min(a, b);});}int query(int i, int j) const {assert(i != j);i = this->rank[i];j = this->rank[j];if (i > j) std::swap(i, j);return st.query(i, j);}private:SparseTable<int> st;};template <typename T>requires requires {typename T::Monoid;typename T::OperatorMonoid;{T::m_id()} -> std::same_as<typename T::Monoid>;{T::o_id()} -> std::same_as<typename T::OperatorMonoid>;{T::m_merge(std::declval<typename T::Monoid>(),std::declval<typename T::Monoid>())}-> std::same_as<typename T::Monoid>;{T::o_merge(std::declval<typename T::OperatorMonoid>(),std::declval<typename T::OperatorMonoid>())}-> std::same_as<typename T::OperatorMonoid>;{T::apply(std::declval<typename T::Monoid>(),std::declval<typename T::OperatorMonoid>())}-> std::same_as<typename T::Monoid>;}struct LazySegmentTree {using Monoid = typename T::Monoid;using OperatorMonoid = typename T::OperatorMonoid;explicit LazySegmentTree(const int n): LazySegmentTree(std::vector<Monoid>(n, T::m_id())) {}explicit LazySegmentTree(const std::vector<Monoid>& a): n(a.size()), height(std::countr_zero(std::bit_ceil(a.size()))),p2(1 << height) {lazy.assign(p2, T::o_id());data.assign(p2 << 1, T::m_id());std::copy(a.begin(), a.end(), data.begin() + p2);for (int i = p2 - 1; i > 0; --i) {data[i] = T::m_merge(data[i << 1], data[(i << 1) + 1]);}}void set(int idx, const Monoid val) {idx += p2;for (int i = height; i > 0; --i) {propagate(idx >> i);}data[idx] = val;for (int i = 1; i <= height; ++i) {const int current_idx = idx >> i;data[current_idx] =T::m_merge(data[current_idx << 1], data[(current_idx << 1) + 1]);}}void apply(int idx, const OperatorMonoid val) {idx += p2;for (int i = height; i > 0; --i) {propagate(idx >> i);}data[idx] = T::apply(data[idx], val);for (int i = 1; i <= height; ++i) {const int current_idx = idx >> i;data[current_idx] =T::m_merge(data[current_idx << 1], data[(current_idx << 1) + 1]);}}void apply(int left, int right, const OperatorMonoid val) {if (right <= left) [[unlikely]] return;left += p2;right += p2;const int ctz_left = std::countr_zero(static_cast<unsigned int>(left));for (int i = height; i > ctz_left; --i) {propagate(left >> i);}const int ctz_right = std::countr_zero(static_cast<unsigned int>(right));for (int i = height; i > ctz_right; --i) {propagate(right >> i);}for (int l = left, r = right; l < r; l >>= 1, r >>= 1) {if (l & 1) apply_sub(l++, val);if (r & 1) apply_sub(--r, val);}for (int i = left >> (ctz_left + 1); i > 0; i >>= 1) {data[i] = T::m_merge(data[i << 1], data[(i << 1) + 1]);}for (int i = right >> (ctz_right + 1); i > 0; i >>= 1) {data[i] = T::m_merge(data[i << 1], data[(i << 1) + 1]);}}Monoid get(int left, int right) {if (right <= left) [[unlikely]] return T::m_id();left += p2;right += p2;const int ctz_left = std::countr_zero(static_cast<unsigned int>(left));for (int i = height; i > ctz_left; --i) {propagate(left >> i);}const int ctz_right = std::countr_zero(static_cast<unsigned int>(right));for (int i = height; i > ctz_right; --i) {propagate(right >> i);}Monoid res_l = T::m_id(), res_r = T::m_id();for (; left < right; left >>= 1, right >>= 1) {if (left & 1) res_l = T::m_merge(res_l, data[left++]);if (right & 1) res_r = T::m_merge(data[--right], res_r);}return T::m_merge(res_l, res_r);}Monoid operator[](const int idx) {const int node = idx + p2;for (int i = height; i > 0; --i) {propagate(node >> i);}return data[node];}template <typename G>int find_right(int left, const G g) {if (left >= n) [[unlikely]] return n;left += p2;for (int i = height; i > 0; --i) {propagate(left >> i);}Monoid val = T::m_id();do {while (!(left & 1)) left >>= 1;Monoid nxt = T::m_merge(val, data[left]);if (!g(nxt)) {while (left < p2) {propagate(left);left <<= 1;nxt = T::m_merge(val, data[left]);if (g(nxt)) {val = nxt;++left;}}return left - p2;}val = nxt;++left;} while (!std::has_single_bit(static_cast<unsigned int>(left)));return n;}template <typename G>int find_left(int right, const G g) {if (right <= 0) [[unlikely]] return -1;right += p2;for (int i = height; i > 0; --i) {propagate((right - 1) >> i);}Monoid val = T::m_id();do {--right;while (right > 1 && (right & 1)) right >>= 1;Monoid nxt = T::m_merge(data[right], val);if (!g(nxt)) {while (right < p2) {propagate(right);right = (right << 1) + 1;nxt = T::m_merge(data[right], val);if (g(nxt)) {val = nxt;--right;}}return right - p2;}val = nxt;} while (!std::has_single_bit(static_cast<unsigned int>(right)));return -1;}private:const int n, height, p2;std::vector<Monoid> data;std::vector<OperatorMonoid> lazy;void apply_sub(const int idx, const OperatorMonoid& val) {data[idx] = T::apply(data[idx], val);if (idx < p2) lazy[idx] = T::o_merge(lazy[idx], val);}void propagate(const int idx) {// assert(1 <= idx && idx < p2);apply_sub(idx << 1, lazy[idx]);apply_sub((idx << 1) + 1, lazy[idx]);lazy[idx] = T::o_id();}};namespace monoid {template <typename T>struct RangeMinimumAndUpdateQuery {using Monoid = T;using OperatorMonoid = T;static constexpr Monoid m_id() { return std::numeric_limits<Monoid>::max(); }static constexpr OperatorMonoid o_id() {return std::numeric_limits<OperatorMonoid>::max();}static Monoid m_merge(const Monoid& a, const Monoid& b) {return std::min(a, b);}static OperatorMonoid o_merge(const OperatorMonoid& a,const OperatorMonoid& b) {return b == o_id() ? a : b;}static Monoid apply(const Monoid& a, const OperatorMonoid& b) {return b == o_id() ? a : b;}};template <typename T>struct RangeMaximumAndUpdateQuery {using Monoid = T;using OperatorMonoid = T;static constexpr Monoid m_id() {return std::numeric_limits<Monoid>::lowest();}static constexpr OperatorMonoid o_id() {return std::numeric_limits<OperatorMonoid>::lowest();}static Monoid m_merge(const Monoid& a, const Monoid& b) {return std::max(a, b);}static OperatorMonoid o_merge(const OperatorMonoid& a,const OperatorMonoid& b) {return b == o_id() ? a : b;}static Monoid apply(const Monoid& a, const OperatorMonoid& b) {return b == o_id()? a : b;}};template <typename T, T Inf>struct RangeMinimumAndAddQuery {using Monoid = T;using OperatorMonoid = T;static constexpr Monoid m_id() { return Inf; }static constexpr OperatorMonoid o_id() { return 0; }static Monoid m_merge(const Monoid& a, const Monoid& b) {return std::min(a, b);}static OperatorMonoid o_merge(const OperatorMonoid& a,const OperatorMonoid& b) {return a + b;}static Monoid apply(const Monoid& a, const OperatorMonoid& b) {return a + b;}};template <typename T, T Inf>struct RangeMaximumAndAddQuery {using Monoid = T;using OperatorMonoid = T;static constexpr Monoid m_id() { return -Inf; }static constexpr OperatorMonoid o_id() { return 0; }static Monoid m_merge(const Monoid& a, const Monoid& b) {return std::max(a, b);}static OperatorMonoid o_merge(const OperatorMonoid& a,const OperatorMonoid& b) {return a + b;}static Monoid apply(const Monoid& a, const OperatorMonoid& b) {return a + b;}};template <typename T>struct RangeSumAndUpdateQuery {using Monoid = struct { T sum; int len; };using OperatorMonoid = T;static std::vector<Monoid> init(const int n) {return std::vector<Monoid>(n, Monoid{0, 1});}static constexpr Monoid m_id() { return {0, 0}; }static constexpr OperatorMonoid o_id() {return std::numeric_limits<OperatorMonoid>::max();}static Monoid m_merge(const Monoid& a, const Monoid& b) {return Monoid{a.sum + b.sum, a.len + b.len};}static OperatorMonoid o_merge(const OperatorMonoid& a,const OperatorMonoid& b) {return b == o_id() ? a : b;}static Monoid apply(const Monoid& a, const OperatorMonoid& b) {return Monoid{b == o_id() ? a.sum : b * a.len, a.len};}};template <typename T>struct RangeSumAndAddQuery {using Monoid = struct { T sum; int len; };using OperatorMonoid = T;static std::vector<Monoid> init(const int n) {return std::vector<Monoid>(n, Monoid{0, 1});}static constexpr Monoid m_id() { return {0, 0}; }static constexpr OperatorMonoid o_id() { return 0; }static Monoid m_merge(const Monoid& a, const Monoid& b) {return Monoid{a.sum + b.sum, a.len + b.len};}static OperatorMonoid o_merge(const OperatorMonoid& a,const OperatorMonoid& b) {return a + b;}static Monoid apply(const Monoid& a, const OperatorMonoid& b) {return Monoid{a.sum + b * a.len, a.len};}};} // namespace monoidint main() {int n, q; string s; cin >> n >> q >> s;LongestCommonPrefix lcp(s);vector<ll> sum(n + 1, 0);REP(i, n + 1) sum[i] = n - lcp.sa[i];REP(i, n) sum[i + 1] += sum[i];vector<vector<pair<int, int>>> queries(n + 1);vector<ll> ans(q, 0);REP(i, q) {int l, r; cin >> l >> r; --l; --r;int lb = 0, ub = lcp.rank[l];while (ub - lb > 1) {const int mid = midpoint(lb, ub);(lcp.query(lcp.sa[mid], l) >= r - l + 1 ? ub : lb) = mid;}ans[i] = ll{lcp.rank[l] - lb} * (r - l);if (lb > 0) ans[i] += sum[lb];queries[lcp.rank[l]].emplace_back(i, r - l);}LazySegmentTree<monoid::RangeSumAndUpdateQuery<ll>> seg(monoid::RangeSumAndUpdateQuery<ll>::init(n + 1));// REP(i, n) cout << lcp.lcp_array[i] << " \n"[i + 1 == n];for (int i = n - 1; i >= 0; --i) {int lb = i, ub = n;while (ub - lb > 1) {const int mid = midpoint(lb, ub);(seg[mid].sum > lcp.lcp_array[i] ? lb : ub) = mid;}seg.apply(i, lb + 1, lcp.lcp_array[i]);// REP(i, n) cout << seg[i].sum << " \n"[i + 1 == n];for (const auto& [id, mn] : queries[i]) {int lb = i - 1, ub = n;while (ub - lb > 1) {const int mid = midpoint(lb, ub);(seg[mid].sum > mn ? lb : ub) = mid;}ans[id] += (lb - i + 1LL) * mn;ans[id] += seg.get(lb + 1, n).sum;}}REP(i, q) cout << ans[i] << '\n';return 0;}