結果
問題 | No.2361 Many String Compare Queries |
ユーザー |
![]() |
提出日時 | 2023-06-23 23:38:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 470 ms / 2,500 ms |
コード長 | 11,671 bytes |
コンパイル時間 | 3,116 ms |
コンパイル使用メモリ | 230,812 KB |
最終ジャッジ日時 | 2025-02-15 01:40:48 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
#line 1 "main.cpp"//#pragma GCC target("avx")//#pragma GCC optimize("O3")//#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>#ifdef LOCAL#include <debug.hpp>#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else#define debug(...) (static_cast<void>(0))#endifusing namespace std;using ll = long long;using ld = long double;using pll = pair<ll, ll>;using pii = pair<int, int>;using vi = vector<int>;using vvi = vector<vi>;using vvvi = vector<vvi>;using vl = vector<ll>;using vvl = vector<vl>;using vvvl = vector<vvl>;using vpii = vector<pii>;using vpll = vector<pll>;using vs = vector<string>;template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;#define overload4(_1, _2, _3, _4, name, ...) name#define overload3(a,b,c,name,...) name#define rep1(n) for (ll UNUSED_NUMBER = 0; UNUSED_NUMBER < (n); ++UNUSED_NUMBER)#define rep2(i, n) for (ll i = 0; i < (n); ++i)#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)#define rrep1(n) for(ll i = (n) - 1;i >= 0;i--)#define rrep2(i,n) for(ll i = (n) - 1;i >= 0;i--)#define rrep3(i,a,b) for(ll i = (b) - 1;i >= (a);i--)#define rrep4(i,a,b,c) for(ll i = (a) + ((b)-(a)-1) / (c) * (c);i >= (a);i -= c)#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)#define all1(i) begin(i) , end(i)#define all2(i,a) begin(i) , begin(i) + a#define all3(i,a,b) begin(i) + a , begin(i) + b#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)#define sum(...) accumulate(all(__VA_ARGS__),0LL)template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }template<class T> auto min(const T& a){return *min_element(all(a));}template<class T> auto max(const T& a){return *max_element(all(a));}template<class... Ts> void in(Ts&... t);#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)#define VEC(type, name, size) vector<type> name(size); in(name)#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)ll intpow(ll a, ll b){ ll ans = 1; while(b){if(b & 1) ans *= a; a *= a; b /= 2;} return ans;}ll modpow(ll a, ll b, ll p){ ll ans = 1; a %= p;if(a < 0) a += p;while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }ll GCD(ll a,ll b) { if(a == 0 || b == 0) return 0; if(a % b == 0) return b; else return GCD(b,a%b);}ll LCM(ll a,ll b) { if(a == 0) return b; if(b == 0) return a;return a / GCD(a,b) * b;}namespace IO{#define VOID(a) decltype(void(a))struct setting{ setting(){cin.tie(nullptr); ios::sync_with_stdio(false);fixed(cout); cout.precision(12);}} setting;template<int I> struct P : P<I-1>{};template<> struct P<0>{};template<class T> void i(T& t){ i(t, P<3>{}); }void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){in(get<idx>(t)...);}template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ituple(t, make_index_sequence<tuple_size<T>::value>{});}#undef VOID}#define unpack(a) (void)initializer_list<int>{(a, 0)...}template<class... Ts> void in(Ts&... t){ unpack(IO :: i(t)); }#undef unpackstatic const double PI = 3.1415926535897932;template <class F> struct REC {F f;REC(F &&f_) : f(forward<F>(f_)) {}template <class... Args> auto operator()(Args &&...args) const { return f(*this, forward<Args>(args)...); }};//constexpr int mod = 1000000007;constexpr int mod = 998244353;#include <atcoder/string>using namespace atcoder;template <typename T>struct SparseTable {inline static constexpr T INF = numeric_limits<T>::max() / 2;int N;vector<vector<T> > table;T f(T a, T b) { return min(a, b); }SparseTable() {}SparseTable(const vector<T> &v) : N(v.size()) {int b = 1;while ((1 << b) <= N) ++b;table.push_back(v);for (int i = 1; i < b; i++) {table.push_back(vector<T>(N, INF));for (int j = 0; j + (1 << i) <= N; j++) {table[i][j] = f(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);}}}// [l, r)T query(int l, int r) {assert(0 <= l and l <= r and r <= N);if (l == r) return INF;int b = 31 - __builtin_clz(r - l);return f(table[b][l], table[b][r - (1 << b)]);}};#line 2 "segment-tree/segment-tree-beats.hpp"struct AngelBeats {using i64 = long long;static constexpr i64 INF = numeric_limits<i64>::max() / 2.1;struct alignas(32) Node {i64 sum = 0, g1 = 0, l1 = 0;i64 g2 = -INF, gc = 1, l2 = INF, lc = 1, add = 0;};vector<Node> v;i64 n, log;AngelBeats() {}AngelBeats(int _n) : AngelBeats(vector<i64>(_n)) {}AngelBeats(const vector<i64>& vc) {n = 1, log = 0;while (n < (int)vc.size()) n <<= 1, log++;v.resize(2 * n);for (i64 i = 0; i < (int)vc.size(); ++i) {v[i + n].sum = v[i + n].g1 = v[i + n].l1 = vc[i];}for (i64 i = n - 1; i; --i) update(i);}void range_chmin(int l, int r, i64 x) { inner_apply<1>(l, r, x); }void range_chmax(int l, int r, i64 x) { inner_apply<2>(l, r, x); }void range_add(int l, int r, i64 x) { inner_apply<3>(l, r, x); }void range_update(int l, int r, i64 x) { inner_apply<4>(l, r, x); }i64 range_min(int l, int r) { return inner_fold<1>(l, r); }i64 range_max(int l, int r) { return inner_fold<2>(l, r); }i64 range_sum(int l, int r) { return inner_fold<3>(l, r); }private:void update(int k) {Node& p = v[k];Node& l = v[k * 2 + 0];Node& r = v[k * 2 + 1];p.sum = l.sum + r.sum;if (l.g1 == r.g1) {p.g1 = l.g1;p.g2 = max(l.g2, r.g2);p.gc = l.gc + r.gc;} else {bool f = l.g1 > r.g1;p.g1 = f ? l.g1 : r.g1;p.gc = f ? l.gc : r.gc;p.g2 = max(f ? r.g1 : l.g1, f ? l.g2 : r.g2);}if (l.l1 == r.l1) {p.l1 = l.l1;p.l2 = min(l.l2, r.l2);p.lc = l.lc + r.lc;} else {bool f = l.l1 < r.l1;p.l1 = f ? l.l1 : r.l1;p.lc = f ? l.lc : r.lc;p.l2 = min(f ? r.l1 : l.l1, f ? l.l2 : r.l2);}}void push_add(int k, i64 x) {Node& p = v[k];p.sum += x << (log + __builtin_clz(k) - 31);p.g1 += x;p.l1 += x;if (p.g2 != -INF) p.g2 += x;if (p.l2 != INF) p.l2 += x;p.add += x;}void push_min(int k, i64 x) {Node& p = v[k];p.sum += (x - p.g1) * p.gc;if (p.l1 == p.g1) p.l1 = x;if (p.l2 == p.g1) p.l2 = x;p.g1 = x;}void push_max(int k, i64 x) {Node& p = v[k];p.sum += (x - p.l1) * p.lc;if (p.g1 == p.l1) p.g1 = x;if (p.g2 == p.l1) p.g2 = x;p.l1 = x;}void push(int k) {Node& p = v[k];if (p.add != 0) {push_add(k * 2 + 0, p.add);push_add(k * 2 + 1, p.add);p.add = 0;}if (p.g1 < v[k * 2 + 0].g1) push_min(k * 2 + 0, p.g1);if (p.l1 > v[k * 2 + 0].l1) push_max(k * 2 + 0, p.l1);if (p.g1 < v[k * 2 + 1].g1) push_min(k * 2 + 1, p.g1);if (p.l1 > v[k * 2 + 1].l1) push_max(k * 2 + 1, p.l1);}void subtree_chmin(int k, i64 x) {if (v[k].g1 <= x) return;if (v[k].g2 < x) {push_min(k, x);return;}push(k);subtree_chmin(k * 2 + 0, x);subtree_chmin(k * 2 + 1, x);update(k);}void subtree_chmax(int k, i64 x) {if (x <= v[k].l1) return;if (x < v[k].l2) {push_max(k, x);return;}push(k);subtree_chmax(k * 2 + 0, x);subtree_chmax(k * 2 + 1, x);update(k);}template <int cmd>inline void _apply(int k, i64 x) {if constexpr (cmd == 1) subtree_chmin(k, x);if constexpr (cmd == 2) subtree_chmax(k, x);if constexpr (cmd == 3) push_add(k, x);if constexpr (cmd == 4) subtree_chmin(k, x), subtree_chmax(k, x);}template <int cmd>void inner_apply(int l, int r, i64 x) {if (l == r) return;l += n, r += n;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}{int l2 = l, r2 = r;while (l < r) {if (l & 1) _apply<cmd>(l++, x);if (r & 1) _apply<cmd>(--r, x);l >>= 1;r >>= 1;}l = l2;r = r2;}for (int i = 1; i <= log; i++) {if (((l >> i) << i) != l) update(l >> i);if (((r >> i) << i) != r) update((r - 1) >> i);}}template <int cmd>inline i64 e() {if constexpr (cmd == 1) return INF;if constexpr (cmd == 2) return -INF;return 0;}template <int cmd>inline void op(i64& a, const Node& b) {if constexpr (cmd == 1) a = min(a, b.l1);if constexpr (cmd == 2) a = max(a, b.g1);if constexpr (cmd == 3) a += b.sum;}template <int cmd>i64 inner_fold(int l, int r) {if (l == r) return e<cmd>();l += n, r += n;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}i64 lx = e<cmd>(), rx = e<cmd>();while (l < r) {if (l & 1) op<cmd>(lx, v[l++]);if (r & 1) op<cmd>(rx, v[--r]);l >>= 1;r >>= 1;}if constexpr (cmd == 1) lx = min(lx, rx);if constexpr (cmd == 2) lx = max(lx, rx);if constexpr (cmd == 3) lx += rx;return lx;}};/*** @brief Range Chmin Chmax Add Update Range Min Max Sum Segment Tree Beats!* @docs docs/segment-tree/segment-tree-beats.md*/int main() {INT(n,q);STR(s);vi L(q),R(q);rep(i,q) {cin >> L[i] >> R[i];L[i]--;}auto sa = suffix_array(s);auto lcp = lcp_array(s,sa);auto spt = SparseTable<int>(lcp);vl ans(q);debug(ord);int cur = 0;vl init(n,1e9);AngelBeats abseg(init);debug(ans);vector<vpii> evt(n);rep(i,q) evt[L[i]].emplace_back(i,R[i]);rrep(i,n) {if(i < n - 1) abseg.range_chmin(i+1,n,lcp[i]);int l = sa[i];for(auto &[id,r]:evt[l]) {int len = r - l;int ng = n;int ok = i;while(ng - ok > 1) {int mid = (ng + ok) / 2;debug(mid);int lc = spt.query(i,mid);if(lc >= len) ok = mid;else ng = mid;}//debug(i,l,r,ok,ng);ans[id] += 1LL * (ok - i) * (r - l - 1);ans[id] += abseg.range_sum(ok+1,n);}}vl cs(n+1);rep(i,n) cs[i+1] = cs[i] + (n - sa[i]);AngelBeats abseg2(init);rep(i,n) {if(i > 0) abseg2.range_chmin(0,i,lcp[i-1]);int l = sa[i];for(auto &[id,r]:evt[l]) {int len = r - l;int ng = -1;int ok = i;while(ok - ng > 1) {int mid = (ng + ok) / 2;debug(mid);int lc = spt.query(mid,i);if(lc >= len) ok = mid;else ng = mid;}ans[id] += 1LL * (i + 1 - ok) * (r - l - 1);ans[id] += cs[ok];}}rep(i,q) cout << ans[i] << '\n';}