Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using namespace std;
- #include <bits/stdc++.h>
- using ll = long long;
- #define rep(i,a,b) for (int i = a; i < b; i++)
- const ll mod = 1e9 + 7;
- ll euclid(ll a, ll b, ll &x, ll &y) {
- if (!b) return x = 1, y = 0, a;
- ll d = euclid(b, a % b, y, x);
- return y -= a/b * x, d;
- }
- struct Mod {
- ll x;
- Mod(ll y) : Mod(y%mod+mod,0){}
- Mod(ll y,int) : x(y<mod?y:y-mod){}
- Mod operator+(Mod b) { return {x + b.x,0}; }
- Mod operator-(Mod b) { return {x - b.x + mod,0}; }
- Mod operator*(Mod b) { return {x * b.x % mod,0}; }
- Mod operator/(Mod b) { return *this * invert(b); }
- Mod invert(Mod a) {
- ll x,y;
- assert(euclid(a.x,mod,x,y)==1); return x;
- }
- Mod operator^(ll e) {
- if (!e) return Mod(1);
- Mod r = *this ^ (e / 2); r = r * r;
- return e&1 ? *this * r : r;
- }
- };
- vector<Mod> qpow;
- struct Node {
- Node *left, *right;
- ll l, r;
- ll width;
- Mod brightness = Mod(0);
- Node(ll l, ll r) :l(l), r(r) {
- width = (r - l + 1);
- brightness = Mod(0);
- if (l == r) return;
- ll mid = (l + r) / 2;
- left = new Node(l, mid);
- right = new Node(mid + 1, r);
- }
- void update(ll pos, ll val) {
- if (pos < l || pos > r) return;
- if (l == r) {
- brightness = brightness + Mod(val);
- return;
- }
- left->update(pos, val);
- right->update(pos, val);
- brightness = right->brightness + qpow[right->width] * left->brightness;
- }
- Mod query(ll pos) {
- // query [l, pos]
- if (pos < l) return Mod(0);
- else if (pos >= r) return brightness * qpow[pos - r];
- else return left->query(pos) + right->query(pos);
- }
- };
- int main() {
- ll n, q;
- string p_string;
- cin >> n >> q >> p_string;
- Mod p(0);
- Mod div(1);
- for (int i = 2; i < p_string.size(); i++) {
- p = Mod(10) * p + Mod(p_string[i] - '0');
- div = div * Mod(10);
- }
- p = p / div;
- qpow.assign(n+2, Mod(0));
- qpow[0] = Mod(1);
- qpow[1] = Mod(1) - p;
- for (int i = 2; i < n+2; i++) qpow[i] = qpow[i-1] * qpow[1];
- Node left_tree(0ll, n-1), right_tree(0ll, n-1);
- vector<Mod> b_at(n, Mod(0));
- for (int Q = 0; Q < q; Q++) {
- char tp; cin >> tp;
- if (tp == '?') {
- ll x; cin >> x; x--;
- Mod ans = left_tree.query(x) + right_tree.query(n - x - 1) - b_at[x]; //>
- cout << ans.x << endl;
- }
- else {
- ll x, val;
- cin >> val >> x; x--;
- if (tp == '-') val *= -1;
- b_at[x] = b_at[x] + val;
- left_tree.update(x, val);
- right_tree.update(n-x-1, val);
- }
- }
- }
Add Comment
Please, Sign In to add comment