fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  12. typedef pair<int, int>pr;
  13. #define all(i)     i.begin() , i.end()
  14. #define ft     first
  15. #define sn     second
  16. #define pb push_back
  17.  
  18. #define totalone(mask) __builtin_popcount(mask)
  19. #define chkbit(mask,bit) (mask&(1LL << bit))
  20. #define setbit(mask,bit) (mask|(1LL << bit))
  21. #define cngbit(mask,bit) (mask^(1LL << bit))
  22.  
  23. #define en "\n"
  24. #define dbg(x) cerr<<#x<<" is : "<<x<<en;
  25. #define yes cout<<"YES\n"
  26. #define no cout<<"NO\n"
  27. #define report cout<<-1<<en
  28. #define sum(n) ((1LL*(n)*(n+1))/ 2LL)
  29. #define sqr(n) (1LL*(n)*(n))
  30. #define vag(a,b) ((a + b - 1)/b)
  31. #define coutv(v) for(auto i: v) cout<<i<<" ";cout<<en;
  32. #define cinv(v) for(auto &i: v) cin >> i;
  33.  
  34. #define MAXN 50010
  35. #define inf 1e6+5
  36. const int mod = 1e9 + 7;
  37.  
  38. ll n;
  39. ll a[MAXN];
  40.  
  41. struct segment_tree
  42. {
  43.     struct node {
  44.         ll suru , ses, suf, pre, an, sm;
  45.  
  46.         void init(ll l, ll r) {
  47.             suru = l, ses = r;
  48.             if (l == r) suf = pre = an = sm = a[l];
  49.         }
  50.     } g[4 * MAXN], ans;
  51.  
  52.     void fill_cn(node &cn, node &ln, node &rn) // fill_current_node
  53.     {
  54.         cn.sm = ln.sm + rn.sm;
  55.         cn.pre = max(ln.pre, ln.sm + rn.pre);
  56.         cn.suf = max(rn.suf, ln.suf + rn.sm);
  57.         cn.an = max({ln.an, rn.an, ln.suf + rn.pre});
  58.     }
  59.  
  60.     void build(ll cn, ll l, ll r)
  61.     {
  62.         g[cn].init(l, r);
  63.  
  64.         if (l == r ) return;
  65.         ll md = l + (r - l) / 2;
  66.  
  67.         build(cn * 2, l, md);
  68.         build(cn * 2 + 1, md + 1, r);
  69.  
  70.         fill_cn (g[cn], g[cn * 2] , g[cn * 2 + 1]);
  71.     }
  72.  
  73.     void update(ll cn, ll pos, ll val)
  74.     {
  75.         ll x = g[cn].suru;
  76.         ll y = g[cn].ses;
  77.  
  78.         if (y < pos || x > pos) return;
  79.         if (pos <= x && pos >= y ) {
  80.             g[cn].suf = g[cn].pre = g[cn].an = g[cn].sm = val;
  81.             return;
  82.         }
  83.  
  84.         update(cn * 2, pos, val);
  85.         update(cn * 2 + 1, pos, val);
  86.  
  87.         fill_cn(g[cn], g[cn * 2], g[cn * 2 + 1]);
  88.     }
  89.  
  90.     node make_node()
  91.     {
  92.         node cn;
  93.         cn.pre = cn.suf = cn.an = cn.sm = INT_MIN;
  94.         return cn;
  95.     }
  96.  
  97.     node merge(node ln, node rn)
  98.     {
  99.         // cout << ln.sm << " " << rn.sm << en;
  100.         node cn;
  101.         cn.sm = ln.sm + rn.sm;
  102.         cn.pre = max(ln.pre, ln.sm + rn.pre);
  103.         cn.suf = max(rn.suf, ln.suf + rn.sm);
  104.         cn.an = max({ln.an, rn.an, ln.suf + rn.pre});
  105.         return cn;
  106.     }
  107.  
  108.     node query(ll cn, ll l, ll r)
  109.     {
  110.         // cout << cn << en;
  111.         ll x = g[cn].suru;
  112.         ll y = g[cn].ses;
  113.         if (y < l || x > r) return make_node();
  114.  
  115.         if (l <= x && r >= y ) return g[cn];
  116.  
  117.         node _1 = query(cn * 2, l, r);
  118.         node _2 = query(cn * 2 + 1, l, r);
  119.         return merge(_1, _2);
  120.  
  121.     }
  122.  
  123. } stre;
  124. void solve()
  125. {
  126.     cin >> n;
  127.     for (ll i = 1; i <= n; i++) cin >> a[i];
  128.     stre.build(1, 1, n);
  129.  
  130.     ll q;
  131.     cin >> q;
  132.     while (q--)
  133.     {
  134.         ll ty, x, y;
  135.         cin >> ty >> x >> y;
  136.         if (ty == 1) {
  137.             stre.ans = stre.query(1, x, y);
  138.             cout << stre.ans.an << en;
  139.         }
  140.         else {
  141.             stre.update(1, x, y);
  142.         }
  143.     }
  144. }
  145. int main()
  146. {
  147.     IOS;
  148.     ll t;
  149.     t = 1;
  150.     // cin >> t;
  151.  
  152.     int c = 0;
  153.     while ( t-- )
  154.     {
  155.         // cout<<"Case "<<++c<<": ";
  156.         solve();
  157.     }
  158.     return 0;
  159. }
Runtime error #stdin #stdout 0.01s 7428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iN15Er
problem GSS3, based on SPOJ submission 31493145 (CPP14), 2023-06-15 04:31:33
language:
C++14 (gcc 8.3)
created:
1 year 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!