This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#include <string> #include <vector> #include <algorithm> #include <iostream> #include <cstdio> using namespace std; #include "../str_009_manacher.cpp" #include "../../structure/strc_008_abst_segtree.cpp" void tiny_test_str() { string s; cin >> s; char dummy = '$'; Manacher<string, char> man(s, dummy); man.dump(); } void tiny_test_int() { int N; cin >> N; vector<int> v(N); for(int i=0; i<N; i++) cin >> v[i]; int dummy = 0; Manacher< vector<int>, int > man(v, dummy); man.dump(false); } void yuki_464() { string s; cin >> s; int N = s.size(); Manacher<string, char> man(s, '$'); long long int dp[5010][5] = {}; dp[0][0] = 1; for(int i=0; i<N; i++) { for(int j=i+1; j<=N; j++) { for(int k=0; k<4; k++) { if(k != 2) { if(!man.is_palindrome(i, j)) continue; dp[j][k+1] += dp[i][k]; } else { dp[j][k+1] += dp[i][k]; } } } } cout << dp[N][4] << endl; } void WUPC2019_E() { int N, M; cin >> N >> M; vector<int> row(N), col(M); for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { char c; cin >> c; if(c == '1') row[i]++, col[j]++; } } int dummy = -1, ans = 0; Manacher< vector<int>, int > mr(row, dummy), mc(col, dummy); for(int i=0; i<N-1; i++) { for(int j=0; j<M-1; j++) { bool ok = true; ok &= mr.is_palindrome(0, i+1); ok &= mr.is_palindrome(i+1, N); ok &= mc.is_palindrome(0, j+1); ok &= mc.is_palindrome(j+1, M); if(ok) ans++; } } cout << ans << endl; } void ukuku09_D() { struct SegFunc { static int update(int a, int b) { return max(a, b); } static int combine(int a, int b) { return max(a, b); } }; int N, Q; cin >> N >> Q; string s; cin >> s; Manacher< string, char > man(s, '$'); SegmentTree< int, SegFunc > seg(N, -1); for(int i=0; i<N; i++) { int rad = man.get_rad(i); seg.update(i, rad); } while(Q--) { int ql, qr; cin >> ql >> qr; ql--; int ub = (N + 1) / 2 + 1, lb = -1; while(ub - lb > 1) { int mid = (ub + lb) / 2; int l = ql + mid - 1; int r = qr - mid + 1; bool ok = true; if(l >= r) ok = false; else { int val = seg.query(l, r); ok = (val >= mid); } if(ok) lb = mid; else ub = mid; } int ans = lb * 2 - 1; cout << ans << endl; } } int main() { // tiny_test_str(); // tiny_test_int(); // yuki_464(); // WUPC2019_E(); ukuku09_D(); return 0; }
#line 1 "string/verify/verify_str_009_manacher.cpp" #include <string> #include <vector> #include <algorithm> #include <iostream> #include <cstdio> using namespace std; #line 1 "string/str_009_manacher.cpp" // Manacher のアルゴリズム // 各インデックスについて回文半径を線形時間で求める // ダミー文字を挟むことにより偶数長回文にも対応 template <typename ArrayType, typename ElemType> struct Manacher { ArrayType v; ElemType dummy; vector<int> rad; ArrayType insert_dummy_elem(ArrayType vec, ElemType dummy) { int N = vec.size(); ArrayType res(2*N - 1, dummy); for(int i=0; i<N; i++) res[2*i] = vec[i]; return res; } void build() { int N = v.size(), i, j; rad = vector<int>(N); for(i=j=0; i<N; ) { while(i-j >= 0 and i+j < N and v[i-j] == v[i+j]) j++; rad[i] = j; int k; for(k=1; i-k >= 0 and rad[i]-k > rad[i-k]; k++) rad[i+k] = rad[i-k]; i += k; j = max(0, j-k); } } Manacher(ArrayType v_, ElemType dummy_) : v(v_), dummy(dummy_) { v = insert_dummy_elem(v, dummy); build(); } // idx を中心とする回文半径 (0-indexed) int get_rad(int idx) { return (rad[2*idx] + 1) / 2; } // 部分文字列 [l, r) が回文かどうか (0-indexed) bool is_palindrome(int l, int r) { if(l == r) return true; int idx = l + r - 1, len = r - l; return rad[idx] >= len; } }; #line 1 "structure/strc_008_abst_segtree.cpp" // @category セグメント木 (Segment Tree) // @title セグメント木 (Segment Tree) // 抽象 SegmentTree (0-indexed・一点更新・区間取得) template <typename MonoidType> struct SegmentTree { using Function = function< MonoidType(MonoidType, MonoidType) >; // node, identity element int n; vector<MonoidType> node; MonoidType E0; // update / combine function Function upd_f, cmb_f; void build(int m, vector<MonoidType> v = vector<MonoidType>()) { if(v != vector<MonoidType>()) m = v.size(); n = 1; while(n < m) n *= 2; node = vector<MonoidType>(2*n-1, E0); if(v != vector<MonoidType>()) { for(int i=0; i<m; i++) { node[n-1+i] = v[i]; } for(int i=n-2; i>=0; i--) { node[i] = cmb_f(node[2*i+1], node[2*i+2]); } } } // initialize SegmentTree() {} SegmentTree(int n_, MonoidType E0_, Function upd_f_, Function cmb_f_, vector<MonoidType> v = vector<MonoidType>()) : E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) { build(n_, v); } // update k-th element (applied value: x) void update(int k, MonoidType x) { k += n - 1; node[k] = upd_f(node[k], x); while(k > 0) { k = (k - 1) / 2; node[k] = cmb_f(node[2*k+1], node[2*k+2]); } } // range query for [a, b) // 非再帰のアイデア: http://d.hatena.ne.jp/komiyam/20131202/1385992406 MonoidType query(int a, int b) { MonoidType vl = E0, vr = E0; for(int l=a+n, r=b+n; l<r; l>>=1, r>>=1) { if(l & 1) vl = cmb_f(vl, node[(l++)-1]); if(r & 1) vr = cmb_f(node[(--r)-1], vr); } return cmb_f(vl, vr); } }; #line 9 "string/verify/verify_str_009_manacher.cpp" void tiny_test_str() { string s; cin >> s; char dummy = '$'; Manacher<string, char> man(s, dummy); man.dump(); } void tiny_test_int() { int N; cin >> N; vector<int> v(N); for(int i=0; i<N; i++) cin >> v[i]; int dummy = 0; Manacher< vector<int>, int > man(v, dummy); man.dump(false); } void yuki_464() { string s; cin >> s; int N = s.size(); Manacher<string, char> man(s, '$'); long long int dp[5010][5] = {}; dp[0][0] = 1; for(int i=0; i<N; i++) { for(int j=i+1; j<=N; j++) { for(int k=0; k<4; k++) { if(k != 2) { if(!man.is_palindrome(i, j)) continue; dp[j][k+1] += dp[i][k]; } else { dp[j][k+1] += dp[i][k]; } } } } cout << dp[N][4] << endl; } void WUPC2019_E() { int N, M; cin >> N >> M; vector<int> row(N), col(M); for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { char c; cin >> c; if(c == '1') row[i]++, col[j]++; } } int dummy = -1, ans = 0; Manacher< vector<int>, int > mr(row, dummy), mc(col, dummy); for(int i=0; i<N-1; i++) { for(int j=0; j<M-1; j++) { bool ok = true; ok &= mr.is_palindrome(0, i+1); ok &= mr.is_palindrome(i+1, N); ok &= mc.is_palindrome(0, j+1); ok &= mc.is_palindrome(j+1, M); if(ok) ans++; } } cout << ans << endl; } void ukuku09_D() { struct SegFunc { static int update(int a, int b) { return max(a, b); } static int combine(int a, int b) { return max(a, b); } }; int N, Q; cin >> N >> Q; string s; cin >> s; Manacher< string, char > man(s, '$'); SegmentTree< int, SegFunc > seg(N, -1); for(int i=0; i<N; i++) { int rad = man.get_rad(i); seg.update(i, rad); } while(Q--) { int ql, qr; cin >> ql >> qr; ql--; int ub = (N + 1) / 2 + 1, lb = -1; while(ub - lb > 1) { int mid = (ub + lb) / 2; int l = ql + mid - 1; int r = qr - mid + 1; bool ok = true; if(l >= r) ok = false; else { int val = seg.query(l, r); ok = (val >= mid); } if(ok) lb = mid; else ub = mid; } int ans = lb * 2 - 1; cout << ans << endl; } } int main() { // tiny_test_str(); // tiny_test_int(); // yuki_464(); // WUPC2019_E(); ukuku09_D(); return 0; }