fork download
copy 
  1. /*
  2.     Author: Cadocx
  3.     Codeforces: https://c...content-available-to-author-only...s.com/profile/Kadoc
  4.     VNOJ: oj.vnoi.info/user/Cadoc
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. // input/output
  11. #define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  12. #define el cout << '\n'
  13. #define debug(x) cout << #x << " = " << x << '\n'
  14. #define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
  15. // #pragma GCC optimize("O2", "unroll-loops", "Ofast")
  16. // #pragma GCC target("avx,avx2,fma")
  17. //data type
  18. #define ll long long
  19. #define ull unsigned long long
  20. #define pii pair<int, int>
  21. #define pll pair<ll, ll>
  22. #define piv pair<int, vector<int>>
  23. #define vi vector<int>
  24. #define vl vector<ll>
  25. #define vc vector<char>
  26. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return 1; }; return 0; }
  27. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return 1; }; return 0; }
  28. //STL
  29. #define sz(x) (int)(x).size()
  30. #define FOR(i,l,r) for(auto i = l; i <= r; i++)
  31. #define FORD(i,r,l) for(auto i = r; i >= l; i--)
  32. #define forin(i,a) for(auto i : a)
  33. #define pb push_back
  34. #define eb emplace_back
  35. #define pf push_front
  36. #define all(x) (x).begin(), (x).end()
  37. #define fi first
  38. #define se second
  39. //bitmask
  40. #define bitcnt(n) __builtin_popcount(n)
  41. #define mask(i) (1 << (i))
  42. #define bit(n, i) (((n) >> (i)) & 1)
  43. #define set_on(n, i) ((n) | mask(i))
  44. #define set_off(n, i) ((n) & ~mask(i))
  45. //constant
  46. #define N 300005
  47. #define MOD 1000230007
  48. #define INF 0x3f3f3f3f
  49. #define LINF 0x3f3f3f3f3f3f3f3f
  50. #define base 31
  51. #define Kadoc 0
  52.  
  53. int n, q;
  54. ll a[N];
  55. ll st[N << 2], lz[N << 2], t[N];
  56.  
  57. void push(int id, int l, int r){
  58.     if(!lz[id]) return;
  59.     st[id] += lz[id];
  60.     if(l != r){
  61.         lz[id<<1] += lz[id];
  62.         lz[id<<1|1] += lz[id];
  63.     }
  64.     lz[id] = 0;
  65. }
  66.  
  67. void upd(int id, int l, int r, int u, int v, ll x){
  68.     push(id, l, r);
  69.     if(v < l || r < u) return;
  70.     if(u <= l && r <= v){
  71.         lz[id] += x;
  72.         push(id, l, r);
  73.         return;
  74.     }
  75.     int m = (l+r)>>1;
  76.     upd(id<<1, l, m, u, v, x);
  77.     upd(id<<1|1, m+1, r, u, v, x);
  78.     st[id] = max(st[id<<1], st[id<<1|1]);
  79. }
  80.  
  81. ll get(int id, int l, int r, int u, int v){
  82.     push(id, l, r);
  83.     if(v < l || r < u) return -LINF;
  84.     if(u <= l && r <= v) return st[id];
  85.     int m = (l+r)>>1;
  86.     return max(get(id<<1, l, m, u, v), get(id<<1|1, m+1, r, u, v));
  87. }
  88.  
  89. void updBIT(int x, ll v){
  90.     for(;x<=N; x+=x&-x) t[x] += v;
  91. }
  92.  
  93. ll getBIT(int x){
  94.     ll Ans = 0;
  95.     for(;x; x-=x&-x) Ans += t[x];
  96.     return Ans;
  97. }
  98.  
  99. void solve(){
  100.     cin >> n >> q;
  101.  
  102.     ll pre = 0;
  103.     FOR(i, 1, n){
  104.         cin >> a[i];
  105.         updBIT(i, a[i]);
  106.         upd(1, 1, n, i, i, a[i] - pre);
  107.         pre += a[i];
  108.     }
  109.  
  110.     while(q--){
  111.         int op; cin >> op;
  112.         if(op == 1){
  113.             int i, x; cin >> i >> x;
  114.             upd(1, 1, n, i+1, n, a[i] - x);
  115.             upd(1, 1, n, i, i, x - a[i]);
  116.             updBIT(i, x - a[i]);
  117.             a[i] = x;
  118.         }
  119.         else{
  120.             int l, r; cin >> l >> r;
  121.             cout << get(1, 1, n, l, r) + getBIT(l-1); el;
  122.         }
  123.     }
  124. }
  125.  
  126. int main(){
  127.     #define NAME "lol"
  128.     if(fopen(NAME".inp", "r")){
  129.         freopen(NAME".inp", "r", stdin);
  130.         freopen(NAME".out", "w", stdout);
  131.     }
  132.  
  133.     fastIO;
  134.  
  135.     if(Kadoc){
  136.         int tc; cin >> tc;
  137.         while(tc--){
  138.             solve();
  139.         }
  140.     } else solve();
  141. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8rFFX4
language:
C++14 (gcc 8.3)
created:
8 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!