D

 avatar
meda
c_cpp
a month ago
3.1 kB
5
Indexable
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;using namespace __gnu_pbds;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
void printff(vector<T>& v) {
  for (auto k : v) cout << k << " ";
  cout << endl;
}

struct item{
    ll prefix, suffix, answer, sum;
    item(){}
    item(ll p, ll s, ll ans, ll ss){
        prefix = p;
        suffix = s;
        answer = ans;
        sum = ss;
    }
};
item NEUTRAL(0, 0, 0, 0);
struct segment_tree{
    int n;
    vector<item> tree;
    segment_tree(int n_){
        n = 1;
        while (n < n_) n <<= 1;
        tree = vector<item>(2 * n, NEUTRAL);
    }
    item f(item a, item b){
        item ret;
        ret.prefix = max(a.prefix, a.sum + b.prefix);
        ret.suffix = max(b.suffix, b.sum + a.suffix);
        ret.answer = max({a.answer, b.answer, a.suffix + b.prefix});
        ret.sum = a.sum + b.sum;
        return ret;
    }
    void set(int i, ll val, int node, int l, int r){
        if (r - l == 1){
            tree[node] = item(max(val, 0LL), max(val, 0LL), max(val, 0LL), val);
            return;
        }

        int mid = (l + r) >> 1;
        if (i < mid)
            set(i, val, 2 * node + 1, l, mid);
        else
            set(i, val, 2 * node + 2, mid, r);
        
        tree[node] = f(tree[2 * node + 1], tree[2 * node + 2]);
    }
    void set(int i, ll val){
        set(i, val, 0, 0, n);
    }
    item query(int l, int r, int node, int l_node, int r_node){
        if (l_node >= r || l >= r_node)
            return NEUTRAL;
        if (l_node >= l && r_node <= r)
            return tree[node];
        
        int m = (l_node + r_node) >> 1;
        return f(query(l, r, 2 * node + 1, l_node, m), query(l, r, 2 * node + 2, m, r_node));
    }
    item query(int l, int r){ // [l, r] inclusive
        return query(l, r + 1, 0, 0, n);
    }
};
void SOLVE(){
    int n, q; cin >> n >> q;
    vector<ll> a(n);
    for(auto & val : a) cin >> val;
    segment_tree ones(n), zeros(n), twos(n);
    for(int i = 0; i < n; i++){
        int val = a[i];
        zeros.set(i, (val == 0 ? 1 : -1e13));
        ones.set(i, (val == 1 ? 1 : -1e13));
        twos.set(i, (val == 2 ? 1 : -1e13));
    }

    while(q--){
        int i, x; cin >> i >> x;
        i--;
        ll val = a[i] + x;
        zeros.set(i, (val == 0 ? 1 : -1e13));
        ones.set(i, (val == 1 ? 1 : -1e13));
        twos.set(i, (val == 2 ? 1 : -1e13));
        a[i] = val;
        cout << max({zeros.query(0, n - 1).answer, twos.query(0, n - 1).answer , ones.query(0, n - 1).answer, 0LL}) << endl;
    }
} 
int main() {
  ios_base::sync_with_stdio(false), cout.tie(nullptr);
  int o_o = 1; cin >> o_o;
  while(o_o --) SOLVE();
  return 0;
}
Editor is loading...
Leave a Comment