fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class SegmentTree {
  5. public:
  6.     int n;
  7.     vector<int> maxTree, minTree;
  8.  
  9.     SegmentTree(int size) {
  10.         n = size;
  11.         maxTree.resize(4 * n, INT_MIN);
  12.         minTree.resize(4 * n, INT_MAX);
  13.     }
  14.  
  15.     void build(vector<int>& a, int v, int tl, int tr) {
  16.         if (tl == tr) {
  17.             maxTree[v] = a[tl];
  18.             minTree[v] = a[tl];
  19.         } else {
  20.             int tm = (tl + tr) / 2;
  21.             build(a, v * 2, tl, tm);
  22.             build(a, v * 2 + 1, tm + 1, tr);
  23.             maxTree[v] = max(maxTree[v * 2], maxTree[v * 2 + 1]);
  24.             minTree[v] = min(minTree[v * 2], minTree[v * 2 + 1]);
  25.         }
  26.     }
  27.  
  28.     void update(int v, int tl, int tr, int pos, int newVal) {
  29.         if (tl == tr) {
  30.             maxTree[v] = newVal;
  31.             minTree[v] = newVal;
  32.         } else {
  33.             int tm = (tl + tr) / 2;
  34.             if (pos <= tm) {
  35.                 update(v * 2, tl, tm, pos, newVal);
  36.             } else {
  37.                 update(v * 2 + 1, tm + 1, tr, pos, newVal);
  38.             }
  39.             maxTree[v] = max(maxTree[v * 2], maxTree[v * 2 + 1]);
  40.             minTree[v] = min(minTree[v * 2], minTree[v * 2 + 1]);
  41.         }
  42.     }
  43.  
  44.     pair<int, int> query(int v, int tl, int tr, int l, int r) {
  45.         if (l > r) return {INT_MIN, INT_MAX};
  46.         if (l == tl && r == tr) {
  47.             return {maxTree[v], minTree[v]};
  48.         }
  49.         int tm = (tl + tr) / 2;
  50.         auto left = query(v * 2, tl, tm, l, min(r, tm));
  51.         auto right = query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  52.         return {max(left.first, right.first), min(left.second, right.second)};
  53.     }
  54. };
  55.  
  56. void solve() {
  57.     int t;
  58.     cin >> t;
  59.     while (t--) {
  60.         int n, q;
  61.         cin >> n >> q;
  62.         vector<int> a(n);
  63.         for (int i = 0; i < n; i++) {
  64.             cin >> a[i];
  65.         }
  66.  
  67.         SegmentTree segTree(n);
  68.         segTree.build(a, 1, 0, n - 1);
  69.  
  70.         auto getMaxConvenience = [&]() -> int {
  71.             int maxConvenience = INT_MIN;
  72.             for (int l = 0; l < n; l++) {
  73.                 for (int r = l; r < n; r++) {
  74.                     auto [mx, mn] = segTree.query(1, 0, n - 1, l, r);
  75.                     int convenience = mx - mn - (r - l);
  76.                     maxConvenience = max(maxConvenience, convenience);
  77.                 }
  78.             }
  79.             return maxConvenience;
  80.         };
  81.  
  82.         cout << getMaxConvenience() << "\n";
  83.  
  84.         for (int i = 0; i < q; i++) {
  85.             int p, x;
  86.             cin >> p >> x;
  87.             segTree.update(1, 0, n - 1, p - 1, x);
  88.             cout << getMaxConvenience() << "\n";
  89.         }
  90.     }
  91. }
  92.  
  93. int main() {
  94.     ios::sync_with_stdio(false);
  95.     cin.tie(nullptr);
  96.     solve();
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
2 2
1 10
1 10
2 2
5 3
1 2 3 4 5
3 7
1 4
5 2
8 5
7 4 2 4 8 2 1 4
5 4
1 10
3 2
8 11
7 7
stdout
copy 
8
0
7
0
4
4
4
5
3
6
6
9
7
https://ideone.com/1Evcsw
language:
C++ (gcc 8.3)
created:
13 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!