D
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