matistjati

Untitled

Jun 23rd, 2026
13
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.73 KB | None | 0 0
  1. using namespace std;
  2. #include <bits/stdc++.h>
  3.  
  4. using ll = long long;
  5.  
  6. #define rep(i,a,b) for (int i = a; i < b; i++)
  7.  
  8. const ll mod = 1e9 + 7;
  9.  
  10. ll euclid(ll a, ll b, ll &x, ll &y) {
  11. if (!b) return x = 1, y = 0, a;
  12. ll d = euclid(b, a % b, y, x);
  13. return y -= a/b * x, d;
  14. }
  15.  
  16. struct Mod {
  17. ll x;
  18. Mod(ll xx) : x(xx) {}
  19. Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
  20. Mod operator-(Mod b) { return Mod((x - b.x + mod) % mod); }
  21. Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
  22. Mod operator/(Mod b) { return *this * invert(b); }
  23. Mod invert(Mod a) {
  24. ll x, y, g = euclid(a.x, mod, x, y);
  25. assert(g == 1); return Mod((x + mod) % mod);
  26. }
  27. Mod operator^(ll e) {
  28. if (!e) return Mod(1);
  29. Mod r = *this ^ (e / 2); r = r * r;
  30. return e&1 ? *this * r : r;
  31. }
  32. };
  33.  
  34. vector<Mod> qpow;
  35.  
  36. struct Node {
  37. Node *left, *right;
  38.  
  39. ll l, r;
  40. ll width;
  41. Mod brightness = Mod(0);
  42.  
  43. Node(ll l, ll r) :l(l), r(r) {
  44. width = (r - l + 1);
  45. brightness = Mod(0);
  46. if (l == r) return;
  47. ll mid = (l + r) / 2;
  48. left = new Node(l, mid);
  49. right = new Node(mid + 1, r);
  50. }
  51.  
  52. void update(ll pos, ll val) {
  53. if (pos < l || pos > r) return;
  54.  
  55. if (l == r) {
  56. brightness = brightness + Mod(val);
  57. return;
  58. }
  59.  
  60. left->update(pos, val);
  61. right->update(pos, val);
  62.  
  63. brightness = right->brightness + qpow[right->width] * left->brightness;
  64.  
  65. }
  66.  
  67. Mod query(ll pos) {
  68. // query [l, pos]
  69.  
  70. if (pos < l) return Mod(0);
  71. else if (pos >= r) return brightness * qpow[pos - r];
  72. else return left->query(pos) + right->query(pos);
  73. }
  74. };
  75.  
  76. int main() {
  77. ll n, q;
  78.  
  79. string p_string;
  80.  
  81. cin >> n >> q >> p_string;
  82.  
  83. Mod p(0);
  84. Mod div(1);
  85. for (int i = 2; i < p_string.size(); i++) {
  86. p = Mod(10) * p + Mod(p_string[i] - '0');
  87. div = div * Mod(10);
  88. }
  89. p = p / div;
  90. qpow.assign(n+2, Mod(0));
  91. qpow[0] = Mod(1);
  92. qpow[1] = Mod(1) - p;
  93. for (int i = 2; i < n+2; i++) qpow[i] = qpow[i-1] * qpow[1];
  94.  
  95. Node left_tree(0ll, n-1), right_tree(0ll, n-1);
  96.  
  97. vector<Mod> b_at(n, Mod(0));
  98.  
  99. for (int Q = 0; Q < q; Q++) {
  100. char tp; cin >> tp;
  101.  
  102. if (tp == '?') {
  103. ll x; cin >> x; x--;
  104. Mod ans = left_tree.query(x) + right_tree.query(n - x - 1) - b_at[x]; //>
  105. cout << (ans.x%mod+mod)%mod << endl;
  106. }
  107. else {
  108. ll x, val;
  109. cin >> val >> x; x--;
  110. if (tp == '-') val *= -1;
  111.  
  112. b_at[x] = b_at[x] + val;
  113.  
  114. left_tree.update(x, val);
  115. right_tree.update(n-x-1, val);
  116. }
  117. }
  118. }
  119.  
Add Comment
Please, Sign In to add comment