This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2444" // header file section #include <algorithm> #include <bitset> #include <cfloat> #include <cstdio> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <tuple> #include <utility> #include <vector> #include "../../segment_tree/segment_tree.hpp" using namespace std; using llong = long long; using ull = unsigned long long; llong n, m; string s; char com; string op; set<tuple<ull, ull, ull>> st; template <ull base> struct RollingHash { using value_type = pair<ull, ull>; using T = value_type; static std::vector<ull> pow_table; inline static T identity() { return {0ull, 0ull}; }; inline static T operation(const T a, const T b) { T ret; ret.first = a.first * power(b.second) + b.first; ret.second = a.second + b.second; return ret; }; inline static ull power(ull n) { while (pow_table.size() <= n) pow_table.push_back(pow_table.back() * base); return pow_table[n]; }; }; template <ull base> vector<ull> RollingHash<base>::pow_table(1, 1); int main() { cin >> n >> m; cin >> s; SegmentTree<RollingHash<1710>> seg1(n); SegmentTree<RollingHash<1000000007>> seg2(n); SegmentTree<RollingHash<10134>> seg3(n); for (int i = 0; i < n; i++) { seg1.update(i, {s[i], 1}); seg2.update(i, {s[i], 1}); seg3.update(i, {s[i], 1}); } llong l, r; l = r = 0; for (int i = 0; i < m; i++) { cin >> com >> op; if (com == 'L') { if (op == "++") l++; else l--; } else if (com == 'R') { if (op == "++") r++; else r--; } auto key = make_tuple(seg1.fold(l, r + 1).first, seg2.fold(l, r + 1).first, seg3.fold(l, r + 1).first); st.insert(key); } cout << st.size() << endl; };
#line 1 "test/aoj/2444_1.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2444" // header file section #include <algorithm> #include <bitset> #include <cfloat> #include <cstdio> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <tuple> #include <utility> #include <vector> #line 1 "segment_tree/segment_tree.hpp" #line 5 "segment_tree/segment_tree.hpp" #include <iterator> #line 7 "segment_tree/segment_tree.hpp" //=== template <class Monoid> struct SegmentTree { using T = typename Monoid::value_type; std::vector<T> tree; SegmentTree() = default; explicit SegmentTree(int n) : tree(n << 1, Monoid::identity()){}; template <class InputIterator> SegmentTree(InputIterator first, InputIterator last) { tree.assign(distance(first, last) << 1, Monoid::identity()); int i; i = size(); for (InputIterator itr = first; itr != last; itr++) { tree[i++] = *itr; } for (i = size() - 1; i > 0; i--) { tree[i] = Monoid::operation(tree[(i << 1)], tree[(i << 1) | 1]); } }; inline int size() { return tree.size() >> 1; }; inline T operator[](int k) { return tree[k + size()]; }; void set(int k, const T dat) { k += size(); tree[k] = dat; while (k > 1) { k >>= 1; tree[k] = Monoid::operation(tree[(k << 1)], tree[(k << 1) | 1]); } }; void update(int k, const T dat) { set(k, dat); }; // [l, r) T fold(int l, int r) { l += size(); // points leaf r += size(); T lv = Monoid::identity(); T rv = Monoid::identity(); while (l < r) { if (l & 1) lv = Monoid::operation(lv, tree[l++]); if (r & 1) rv = Monoid::operation(tree[--r], rv); l >>= 1; r >>= 1; } return Monoid::operation(lv, rv); }; template <class F> inline int sub_tree_search(int i, T sum, F f) { while (i < size()) { T x = Monoid::operation(sum, tree[i << 1]); if (f(x)) { i = i << 1; } else { sum = x; i = (i << 1) | 1; } } return i - size() + 1; } template <class F> int find_first(int l, F f) { l += size(); int r = size() * 2; // r = n; int tmpr = r; int shift = 0; T sum = Monoid::identity(); while (l < r) { if (l & 1) { if (f(Monoid::operation(sum, tree[l]))) { return sub_tree_search(l, sum, f); } sum = Monoid::operation(sum, tree[l]); l++; } l >>= 1; r >>= 1; shift++; } while (shift > 0) { shift--; r = tmpr >> shift; if (r & 1) { r--; if (f(Monoid::operation(sum, tree[r]))) { return sub_tree_search(r, sum, f); } sum = Monoid::operation(sum, tree[r]); } } return -1; }; }; //=== #line 20 "test/aoj/2444_1.test.cpp" using namespace std; using llong = long long; using ull = unsigned long long; llong n, m; string s; char com; string op; set<tuple<ull, ull, ull>> st; template <ull base> struct RollingHash { using value_type = pair<ull, ull>; using T = value_type; static std::vector<ull> pow_table; inline static T identity() { return {0ull, 0ull}; }; inline static T operation(const T a, const T b) { T ret; ret.first = a.first * power(b.second) + b.first; ret.second = a.second + b.second; return ret; }; inline static ull power(ull n) { while (pow_table.size() <= n) pow_table.push_back(pow_table.back() * base); return pow_table[n]; }; }; template <ull base> vector<ull> RollingHash<base>::pow_table(1, 1); int main() { cin >> n >> m; cin >> s; SegmentTree<RollingHash<1710>> seg1(n); SegmentTree<RollingHash<1000000007>> seg2(n); SegmentTree<RollingHash<10134>> seg3(n); for (int i = 0; i < n; i++) { seg1.update(i, {s[i], 1}); seg2.update(i, {s[i], 1}); seg3.update(i, {s[i], 1}); } llong l, r; l = r = 0; for (int i = 0; i < m; i++) { cin >> com >> op; if (com == 'L') { if (op == "++") l++; else l--; } else if (com == 'R') { if (op == "++") r++; else r--; } auto key = make_tuple(seg1.fold(l, r + 1).first, seg2.fold(l, r + 1).first, seg3.fold(l, r + 1).first); st.insert(key); } cout << st.size() << endl; };