matistjati

Untitled

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