fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iostream>
  5. #include <cmath>
  6. #include <map>
  7. #include <set>
  8. #include <cassert>
  9. #include <queue>
  10. using namespace std;
  11.  
  12. #define rank XBOCT4
  13. #define right solo322
  14. #define y1 dread1
  15. #define left hohohaha
  16.  
  17. const double PI = acos(-1.0);
  18. const int MD = 1000000000 + 7;
  19. const long long INF = 1e18;
  20. struct Node {
  21.     long long best;
  22.     long long sumStartPlus, sumStartMinus, sumEndPlus, sumEndMinus;
  23.     long long maxStartPlus, maxStartMinus, maxEndPlus, maxEndMinus;
  24.     int cnt;
  25.     bool flag;
  26.     Node(long long value) {
  27.         flag          =  true;
  28.         best          =  value;
  29.         maxStartPlus  =  value;
  30.         maxStartMinus = -value;
  31.         maxEndMinus   = -INF;
  32.         maxEndPlus    =  value;
  33.         sumStartPlus  =  value;
  34.         sumStartMinus = -value;
  35.         sumEndPlus    =  value;
  36.         sumEndMinus   = -INF;
  37.         cnt           =  1;
  38.     }
  39.  
  40.     Node() {}
  41.  
  42. };
  43.  
  44. inline Node combine(Node left, Node right) {
  45.     Node res;
  46.     if (!left.flag && !right.flag) {
  47.         res.flag = false;
  48.         return res;
  49.     }
  50.     if (!left.flag) {
  51.         return right;
  52.     }
  53.     if (!right.flag) {
  54.         return left;
  55.     }
  56.     res.flag = true;
  57.     res.cnt           = left.cnt + right.cnt;
  58.     res.best          = max(left.best, right.best);
  59.     res.best          = max(res.best, max(left.maxEndMinus + right.maxStartPlus, left.maxEndPlus + right.maxStartMinus));
  60.     res.maxStartMinus = max(left.maxStartMinus, left.sumStartMinus + ((left.cnt  % 2 == 0) ? right.maxStartMinus : right.maxStartPlus));
  61.     res.maxStartPlus  = max(left.maxStartPlus , left.sumStartPlus  + ((left.cnt  % 2 == 0) ? right.maxStartPlus  : right.maxStartMinus));
  62.     res.maxEndMinus   = max(right.maxEndMinus , right.sumEndMinus  + ((right.cnt % 2 == 0) ? left.maxEndMinus    : left.maxEndPlus));
  63.     res.maxEndPlus    = max(right.maxEndPlus  , right.sumEndPlus   + ((right.cnt % 2 == 0) ? left.maxEndPlus     : left.maxEndMinus));
  64.  
  65.     res.sumEndMinus   = right.sumEndMinus  + ((right.cnt % 2 == 0) ? left.sumEndMinus    : left.sumEndPlus);
  66.     res.sumEndPlus    = right.sumEndPlus   + ((right.cnt % 2 == 0) ? left.sumEndPlus     : left.sumEndMinus);
  67.     res.sumStartMinus = left.sumStartMinus + ((left.cnt  % 2 == 0) ? right.sumStartMinus : right.sumStartPlus);
  68.     res.sumStartPlus  = left.sumStartPlus  + ((left.cnt  % 2 == 0) ? right.sumStartPlus  : right.sumStartMinus);
  69.     return res;
  70. }
  71.  
  72. Node f[400333];
  73. int n, sz;
  74.  
  75. Node get(int v, int tl, int tr, int l, int r) {
  76.     if (l > tr || tl > r) {
  77.         Node tmp;
  78.         tmp.flag = false;
  79.         return tmp;
  80.     }
  81.     if (l <= tl && r >= tr) {
  82.         return f[v];
  83.     }
  84.     int c =(tl + tr) / 2;
  85.     return combine(get(v * 2, tl, c, l, r), get(v * 2 + 1, c + 1, tr, l , r));
  86. }
  87.  
  88. int main() {
  89.     ios_base::sync_with_stdio(false);
  90.     cin >> n;
  91.     sz = 1;
  92.     while (sz < n) {
  93.         sz += sz;
  94.     }
  95.     for (int i = 1; i <= n; i++) {
  96.         int value;
  97.         cin >> value;
  98.         f[i + sz - 1] = Node(value);
  99.     }
  100.     for (int i = n + 1; i <= sz; i++) {
  101.         f[i + sz - 1].flag = false;
  102.     }
  103.     for (int i = sz - 1; i > 0; i--) {
  104.         f[i] = combine(f[i * 2], f[i * 2 + 1]);
  105.     }
  106.     int q;
  107.     cin >> q;
  108.     while (q--) {
  109.         char c;
  110.         int l, r;
  111.         cin >> c >> l >> r;
  112.         if (c != 'Q') {
  113.             l = l + sz - 1;
  114.             f[l] = Node(r);
  115.             l /= 2;
  116.             while (l > 0) {
  117.                 f[l] = combine(f[l * 2], f[l * 2 + 1]);
  118.                 l /= 2;
  119.             }
  120.         } else {
  121.             cout << get(1, 1, sz, l, r).best << "\n";
  122.         }
  123.     }
  124.     return 0;
  125. }
Success #stdin #stdout 0s 34520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R82GiN
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!