fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const ll MOD = 1e9 + 7;
  6. ll addd(ll a, ll b) { return ((a % MOD) + (b % MOD)) % MOD; }
  7. ll mul(ll a, ll b) { return ((a % MOD) * (b % MOD)) % MOD; }
  8. ll sub(ll a, ll b) { return (((a - b) % MOD) + MOD) % MOD; }
  9. ll modExp(ll a, ll b) {
  10.   if (b <= 0)
  11.     return 1;
  12.   ll ret = modExp(a * a % MOD, b / 2);
  13.   if (b % 2)
  14.     ret = ret * a % MOD;
  15.   return ret;
  16. }
  17. ll inverse(ll b) { return modExp(b, MOD - 2); }
  18. ll divv(ll a, ll b) { return ((a % MOD) * (inverse(b) % MOD)) % MOD; }
  19.  
  20.  
  21. //prod st
  22.  
  23.  
  24. #define int long long
  25. struct SegmentTreeP { // 0-Indexed
  26.     vector<int> tree;
  27.     int skip = 1; // depentent on merge (sum => 0, min => OO, max => -OO)
  28.     int sz;
  29.  
  30. #define mid ((r + l) >> 1)
  31. #define L node * 2 + 1
  32. #define R node * 2 + 2
  33.  
  34.     int merge(int a, int b){
  35.         return mul(a,b);
  36.     }
  37.  
  38.     int build(int l, int r, int node, vector<int> &a){
  39.         if(l == r){
  40.             if(l < (int)a.size()) return (tree[node] = a[l]);
  41.             return skip;
  42.         }
  43.         return tree[node] = merge(build(l, mid, L, a), build(mid + 1, r, R, a));
  44.     }
  45.  
  46.     int update(int l, int r, int node, int idx, int val){
  47.         if(l == r) return tree[node] = val;
  48.         if(idx <= mid) return tree[node] = merge(update(l, mid, L, idx, val), tree[R]);
  49.         else return tree[node] = merge(tree[L], update(mid + 1, r, R, idx, val));
  50.     }
  51.     int add(int l, int r, int node, int idx, int val){
  52.         if(l == r) return tree[node] += val;
  53.         if(idx <= mid) return tree[node] = merge(add(l, mid, L, idx, val), tree[R]);
  54.         else return tree[node] = merge(tree[L], add(mid + 1, r, R, idx, val));
  55.     }
  56.  
  57.     int query(int l, int r, int node, int tl, int tr){
  58.         if(tl > r || tr < l) return skip;
  59.         if(l >= tl && r <= tr) return tree[node];
  60.         return merge(query(l, mid, L, tl, tr), query(mid + 1, r, R, tl, tr));
  61.     }
  62.  
  63.     SegmentTreeP(vector <int> &a){
  64.         int n = (int)a.size(); sz = 1;
  65.         while(sz <= n) sz *= 2;
  66.         tree = vector <int> (2 * sz, skip);
  67.         build(0, sz - 1, 0, a);
  68.     }
  69.  
  70.     SegmentTreeP(int n){
  71.         sz = 1;
  72.         while(sz <= n) sz *= 2;
  73.         tree = vector <int> (2 * sz, skip);
  74.     }
  75.  
  76.     void update(int idx, int val){ update(0, sz - 1, 0, idx, val); }
  77.     void add(int idx, int val){ add(0, sz - 1, 0, idx, val); }
  78.     int query(int l, int r){  return query(0, sz - 1, 0, l, r); }
  79.  
  80. #undef R
  81. #undef L
  82. #undef mid
  83. };
  84. #undef int
  85.  
  86.  
  87. //sum st
  88.  
  89. #define int long long
  90. struct SegmentTreeS { // 0-Indexed
  91.     vector<int> tree;
  92.     int skip = 0; // depentent on merge (sum => 0, min => OO, max => -OO)
  93.     int sz;
  94.  
  95. #define mid ((r + l) >> 1)
  96. #define L node * 2 + 1
  97. #define R node * 2 + 2
  98.  
  99.     int merge(int a, int b){
  100.         return addd(a,b);
  101.     }
  102.  
  103.     int build(int l, int r, int node, vector<int> &a){
  104.         if(l == r){
  105.             if(l < (int)a.size()) return (tree[node] = a[l]);
  106.             return skip;
  107.         }
  108.         return tree[node] = merge(build(l, mid, L, a), build(mid + 1, r, R, a));
  109.     }
  110.  
  111.     int update(int l, int r, int node, int idx, int val){
  112.         if(l == r) return tree[node] = val;
  113.         if(idx <= mid) return tree[node] = merge(update(l, mid, L, idx, val), tree[R]);
  114.         else return tree[node] = merge(tree[L], update(mid + 1, r, R, idx, val));
  115.     }
  116.     int add(int l, int r, int node, int idx, int val){
  117.         if(l == r) return tree[node] += val;
  118.         if(idx <= mid) return tree[node] = merge(add(l, mid, L, idx, val), tree[R]);
  119.         else return tree[node] = merge(tree[L], add(mid + 1, r, R, idx, val));
  120.     }
  121.  
  122.     int query(int l, int r, int node, int tl, int tr){
  123.         if(tl > r || tr < l) return skip;
  124.         if(l >= tl && r <= tr) return tree[node];
  125.         return merge(query(l, mid, L, tl, tr), query(mid + 1, r, R, tl, tr));
  126.     }
  127.  
  128.     SegmentTreeS(vector <int> &a){
  129.         int n = (int)a.size(); sz = 1;
  130.         while(sz <= n) sz *= 2;
  131.         tree = vector <int> (2 * sz, skip);
  132.         build(0, sz - 1, 0, a);
  133.     }
  134.  
  135.     SegmentTreeS(int n){
  136.         sz = 1;
  137.         while(sz <= n) sz *= 2;
  138.         tree = vector <int> (2 * sz, skip);
  139.     }
  140.  
  141.     void update(int idx, int val){ update(0, sz - 1, 0, idx, val); }
  142.     void add(int idx, int val){ add(0, sz - 1, 0, idx, val); }
  143.     int query(int l, int r){  return query(0, sz - 1, 0, l, r); }
  144.  
  145. #undef R
  146. #undef L
  147. #undef mid
  148. };
  149. #undef int
  150.  
  151.  
  152.  
  153.  
  154. ll power(ll b,ll n)
  155.     {
  156.         b%=MOD;
  157.         ll s=1;
  158.         while(n)
  159.         {
  160.             if(n%2==1)s=s*b%MOD;
  161.             b=b*b%MOD;
  162.             n/=2;
  163.         }
  164.         return s;
  165.     }
  166. void solve() {
  167.   ll n;
  168.   cin >> n;
  169.   vector<ll> v(n);
  170.   ll q;
  171.   cin >> q;
  172.   vector<ll> summ(n);
  173.  
  174.   for (ll i = 0; i < n; i++){
  175.     cin >> v[i];
  176.     summ[i]=divv(divv(v[i],100),divv(100-v[i],100));
  177.     v[i]=divv(100-v[i],100);
  178.   }
  179.   SegmentTreeP sp(v);
  180.   SegmentTreeS ss(summ);
  181.   while (q--) {
  182.     ll t;
  183.     cin >> t;
  184.     if (t == 1) {
  185.       ll ind,val;
  186.       cin >> ind>>val;
  187.       sp.update(ind-1,divv(100-val,100));
  188.       ss.update(ind-1,divv(divv(val,100),divv(100-val,100)));
  189.     }
  190.     else{
  191.         ll ind;
  192.         cin >> ind;
  193.         //product + product*sum
  194.         ll f=sp.query(ind,n-1);
  195.         ll s=ss.query(ind,n-1);
  196.         cout << addd(f,(mul(f,s)))<<endl;
  197.     }
  198.   }
  199. }
  200.  
  201. int main() {
  202.   ios::sync_with_stdio(0);
  203.   cin.tie(0);
  204.   cout.tie(0);
  205.   ll t = 1;
  206.   // cin >> t;
  207.   while (t--) {
  208.     solve();
  209.   }
  210.   return 0;
  211. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1Bkop0
language:
C++14 (clang 8.0)
created:
3 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!