fork download
copy 
  1. // #pragma GCC optimize("O3", "unroll-loops")
  2. // #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. // #define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. // #define int ll
  16. #define pii pair<int, int>
  17. #define pll pair<ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned long long
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rall(s) s.rbegin(), s.rend()
  27. #define rev reverse
  28. #define gcd __gcd
  29. #define pushb push_back
  30. #define popb pop_back
  31. #define pushf push_front
  32. #define popf pop_front
  33. #define emp emplace
  34. #define empb emplace_back
  35. #define mul2x(a, x) a << x
  36. #define div2x(a, x) a >> x
  37. #define lcm(a, b) (a / __gcd(a, b) * b)
  38. #define log_base(x, base) log(x) / log(base)
  39. #define debug cerr << "No errors!", exit(0);
  40. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  41. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  42. #define fors(i, a, b) for (int i = a; i >= b; --i)
  43. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  44. #define pqueue priority_queue
  45. #define sqrt sqrtl
  46. #define i128 __int128
  47. #define popcount __builtin_popcountll
  48. #define BIT(x, i) (((x) >> (i)) & 1)
  49. #define MASK(x) ((1LL) << (x))
  50. #define want_digit(x) cout << fixed << setprecision(x);
  51. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  52. #define mapa make_pair
  53. using namespace std;
  54. const int MOD = 1e9 + 7; // 998244353;
  55. const int inf = 1e9;
  56. const ll INF = 1e18; // MASK(63) - 1
  57. const int limN = 5e4 + 5;
  58.  
  59. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  60. inline ll random(const ll &L, const ll &R) {
  61.   return uniform_int_distribution<ll>(L, R)(rng);
  62. }
  63.  
  64. /* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
  65.  
  66. int mul(const int &x, const int &y) {
  67.     return (1LL * x * y) % MOD;
  68. }
  69.  
  70. int add(const int &x, const int &y) {
  71.     return (x + y) % MOD;
  72. }
  73.  
  74. struct Node {
  75.     int v, o, i, _2, _6, vo, voi, voi2, voi26, oi, oi2, oi26, i2, i26, _26;
  76.     Node () {
  77.         v = o = i = _2 = _6 = vo = voi = voi2 = 
  78.         voi26 = oi = oi2 = oi26 = i2 = i26 = _26 = 0;
  79.     }
  80. };
  81.  
  82. Node operator + (const Node &a, const Node &b) {
  83.     Node r;
  84.     // 1 ký tự
  85.     r.v = add(a.v, b.v); r.o = add(a.o, b.o); r.i = add(a.i, b.i); 
  86.     r._2 = add(a._2, b._2); r._6 = add(a._6, b._6);
  87.  
  88.     // 2 ký tự
  89.     r.vo = add(add(a.vo, b.vo), mul(a.v, b.o));
  90.     r.oi = add(add(a.oi, b.oi), mul(a.o, b.i));
  91.     r.i2 = add(add(a.i2, b.i2), mul(a.i, b._2));
  92.     r._26 = add(add(a._26, b._26), mul(a._2, b._6));
  93.  
  94.     // 3 ký tự
  95.     r.voi = add(add(add(a.voi, b.voi), mul(a.v, b.oi)), mul(a.vo, b.i));
  96.     r.oi2 = add(add(add(a.oi2, b.oi2), mul(a.oi, b._2)), mul(a.o, b.i2));
  97.     r.i26 = add(add(add(a.i26, b.i26), mul(a.i, b._26)), mul(a.i2, b._6));
  98.  
  99.     // 4 ký tự 
  100.     r.voi2 = add(add(add(add(a.voi2, b.voi2), mul(a.v, b.oi2)), mul(a.vo, b.i2)), mul(a.voi, b._2));
  101.     r.oi26 = add(add(add(add(a.oi26, b.oi26), mul(a.oi2, b._6)), mul(a.o, b.i26)), mul(a.oi, b._26));
  102.  
  103.     // 5 ký tự (Bro dài điên T^T)
  104.     r.voi26 = add(add(add(add(add(a.voi26, b.voi26), mul(a.v, b.oi26)), mul(a.vo, b.i26)), mul(a.voi, b._26)), mul(a.voi2, b._6));
  105.     return r;
  106. }
  107.  
  108. struct SegmentTree {
  109.     int n;
  110.     vector <Node> seg;
  111.  
  112.     SegmentTree(int _n) {
  113.         n = _n;
  114.         seg.resize(n * 4 + 1, Node());
  115.     }
  116.  
  117.     void update(int id, int l, int r, int pos, char v) {
  118.         if (l > pos || pos > r) return;
  119.         if (l == r) {
  120.             if (v == 'V') ++seg[id].v;
  121.             else if (v == 'O') ++seg[id].o;
  122.             else if (v == 'I') ++seg[id].i;
  123.             else if (v == '2') ++seg[id]._2;
  124.             else if (v == '6') ++seg[id]._6;
  125.             return;
  126.         }
  127.  
  128.         int mid = (l + r) >> 1;
  129.         update(id << 1, l, mid, pos, v);
  130.         update(id << 1 | 1, mid + 1, r, pos, v);
  131.         seg[id] = seg[id << 1] + seg[id << 1 | 1];
  132.     }
  133.  
  134.     Node get(int id, int l, int r, int u, int v) {
  135.         if (l > v || u > r) return Node();
  136.         if (u <= l && r <= v) return seg[id];
  137.         int mid = (l + r) >> 1;
  138.         return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
  139.     }
  140.  
  141.     void update(int pos, char v) { update(1, 1, n, pos, v); }
  142.     Node get(int u, int v) {
  143.         return get(1, 1, n, u, v);
  144.     }
  145. };
  146.  
  147. int n, q;
  148. str s;
  149.  
  150. void solve() {
  151.     cin >> n >> q >> s;
  152.     s = " " + s;
  153.     SegmentTree IT(n);
  154.     forw (i, 1, n) IT.update(i, s[i]);
  155.  
  156.     while (q--) {
  157.         int l, r; cin >> l >> r;
  158.         Node ret = IT.get(l, r);
  159.         cout << ret.voi26 << endl;
  160.     }
  161. }
  162.  
  163. signed main() {
  164.     ios::sync_with_stdio(false), cin.tie(nullptr);
  165.     srand(time(NULL));
  166.     #define name "test"
  167.     if (fopen(name ".INP", "r")) {
  168.         freopen(name ".INP", "r", stdin);
  169.         freopen(name ".OUT", "w", stdout);
  170.     }
  171.     bool testCase = false;
  172.     int numTest = 1;
  173.     // cin >> numTest;
  174.     forw (i, 1, numTest) {
  175.         if (testCase) cout << "Case #" << i << ": ";
  176.         solve();
  177.     }
  178.     return 0;
  179. }
  180.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
8 4
VVOI2626
1 6
2 8
4 5
1 8
stdout
copy 
2
3
0
6
https://ideone.com/M8Mkdx
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!