#include #include #include #include #include using ll = long long; using namespace std; #define isLMS(i) (isL[(i)-1] && !isL[i]) #define LIMIT 200000 template class SuffixArray { vector s; const size_t len, limit; // lenは配列長 limitは配列に登場する文字/数字の種類数 vector bin, // 頭文字の各アルファベットの出現回数の累積和 cnt, // どのアルファベットから始まるものをいくつsaに割り当てたか lms, // LMSのインデックスを格納する配列 isL, // s[i]がL型なら1 S型なら0 sa; // sのsuffix arrayをインデックスで格納する配列 public: vector rank; // s[i:]が辞書順で何番目のsuffixか(saの逆写像)、番兵も // Tが整数の時よう SuffixArray(vector s, size_t limit=LIMIT) : s(s), len(s.size()), limit(limit), bin(limit+1, 0), cnt(limit+1, 0), isL(len+1), sa(len+1), rank(len+1) { (this->s).push_back(0); // 末尾に番兵の追加 lms.reserve(len/2); // lmsの領域の確保 sa_is(); // SAの構築 for (size_t i=0; i<=len; i++) rank[sa[i]] = i; // rankの計算 } // Tがcharの時用 SuffixArray(string s, size_t limit=256) : SuffixArray(vector(s.begin(), s.end()), limit) {} // LCP(高さ配列、蟻本p339)を計算する // lcp[i] = sa[i]とsa[i+1]の先頭何文字が一致しているか // このlcpをRange Minimum Queryに載せれば任意のi jに対してlcpが計算可能 vector lcp; void construct_lcp() { lcp.resize(len); size_t h = 0; for (size_t i=0; i 0) h--; for ( ; i+h int operator[](ID i) { return (int)sa[(size_t)i]; } private: //SA-IS法によりSuffixArrayを構築する void sa_is() { isL[len] = false; bin[1] = 1; for (size_t i=len; i>0; i--) { isL[i-1] = (s[i-1] == s[i]) ? isL[i] : (s[i-1] > s[i]); bin[(size_t)s[i-1]+1]++; if (isLMS(i)) lms.push_back(i); } vector aligned(lms); // あとでlmsは色々並べ替えるが、ここに今の整列した状態を保存しておく reverse(aligned.begin(), aligned.end()); // 降順になっているのをひっくり返して昇順にする for (size_t i=0; i 0 && (isLMS(i+d) || isLMS(j+d))) break; } sa[j] = n; } if (n < lmslen-1) { vector next_s(lmslen-1); for (size_t i=0; i next(next_s, n+1); for (size_t i=0; i #include #define ASSIGN_I [](T &ival, T x) { ival = x; } // i番目にxを代入(点更新のデフォルト) template class SegmentTree { int n; // 葉の数 T def; // 初期値 && 単位元 vector tree; // 本体 using op_func_t = function; using up_func_t = function; op_func_t op_func; // 区間クエリで使う処理 up_func_t up_func; // 点更新で使う処理 ただの変更の他、i番目にxをたすみたいなこともできる // 区間[a, b)の総和(と言うか総operation(は?)) // ノードk=[l, r)を見ている T _query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return def; // 全く交差しない場合 if (a <= l && r <= b) return tree[(size_t)k]; // 完全に包含される場合 T vl = _query(a, b, k * 2 + 1, l, (l + r) / 2), vr = _query(a, b, k * 2 + 2, (l + r) / 2, r); return op_func(vl, vr); } public: SegmentTree(int _n, T _def, op_func_t _op_func, up_func_t _up_func = ASSIGN_I) : def(_def), op_func(_op_func), up_func(_up_func) { n = 1; while (n < _n) n <<= 1; tree = vector((size_t)(2*n - 1), def); } //よく使うやつら min, max, sum SegmentTree(int _n, T _def, string mode, up_func_t _up_func = ASSIGN_I) : SegmentTree( _n, _def, mode == "max" ? [](T l, T r) { return max(l, r); } : (mode == "min" ? [](T l, T r) { return min(l, r); } : [](T l, T r) { return l + r; }), // sum _up_func ) {} SegmentTree(int _n, string mode, up_func_t _up_func = ASSIGN_I) : SegmentTree( _n, mode == "max" ? numeric_limits::lowest() : (mode == "min" ? numeric_limits::max() : 0), // sum mode, _up_func ) {} template void update(ID i, T x) { i += (ID)n - 1; up_func(tree[(size_t)i], x); while (i > 0) { i = (i - 1) / 2; tree[(size_t)i] = op_func(tree[(size_t)(i * 2 + 1)], tree[(size_t)(i * 2 + 2)]); } } template T query(ID1 a, ID2 b) { return _query((int)a, (int)b, 0, 0, n); } void print_tree() { size_t next = 0, size = (size_t)(2 * n - 1); for (size_t i=0; i> n; string s, si; int tops[n+1]; for (int i=0; i> si; tops[i] = s.size(); s += si; } tops[n] = s.size(); SuffixArray sa(s); sa.construct_lcp(); SegmentTree sgt(s.size(), "min"); int l=0; for (auto &lcpl:sa.lcp) sgt.update(l++, lcpl); int m; ll x, d, ans = 0; cin >> m >> x >> d; for (int k=0; k j) swap(i, j); else j++; x = (x + d) % (n * (n-1)); ans += min({sgt.query(sa.rank[tops[i]], sa.rank[tops[j]]), tops[i+1] - tops[i], tops[j+1] - tops[j]}); } cout << ans << '\n'; return 0; }