PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Prefix sums, range maximum queries
PROBLEM:
You’re given an array A of length N. Answer Q queries on it: each query gives you a subarray, and you must find the minimum number of the following operation needed to make all its elements equal 0:
- Let B denote the subarray of A under consideration, and M be its length.
- Let S = \text{sum}(B).
- Choose an index i such that 1 \leq i \leq \min(M, |S|).
- Then, either increase or decrease B_i by 1.
EXPLANATION:
Recall how to solve for a single query from the easy version.
In short: assuming the sum is positive, take all negatives from left to right, then all positives from right to left; but some extra additions might be needed to the first element when doing this.
To adapt this to answering several queries, we’ll need to observe how exactly the extras are calculated - after all, the answer is simply the sum of absolute values of the array, plus twice the number of extras.
Let S denote the sum of the array, and x be the number of extras added to A_1.
Suppose i_1, i_2, \ldots, i_k are the indices of the negative elements in A.
Then, to ensure that all the negative elements are indeed reachable, we must have:
- S+x \geq i_1
- S+x-A_{i_1} \geq i_2 \implies S + x \geq i_2 + A_{i_1}
- S+x-A_{i_1}-A_{i_2} \geq i_3 \implies S + x \geq i_3 + A_{i_1} + A_{i_2}
\vdots
In general, we have S+x \geq i_j + A_{i_1} + A_{i_2} + \ldots + A_{i_{j-1}}.
This already gives us a lower bound on x, by taking the largest bound of this type.
Next, let’s look at the positive values.
When working with these, our sum has increased by the (absolute) sum of all the negative elements that have been used up, so that’s our new value of S - call it S'
But beyond that, the constraints end up being quite similar: if the positive integers are at j_1, j_2, \ldots, j_m then:
- S'+x - (A_{j_m} - 1) \geq j_m must hold, meaning S+x \geq j_m + A_{j_m} + 1.
- S'+x - A_{j_m} - (A_{j_{m-1}} - 1) \geq j_{m-1}, meaning S+x \geq j_{m-1} + A_{j_{m-1}} + A_{j_m} + 1.
\vdots
In general, we obtain S'+x \geq j_x + A_{j_x} + A_{j_{x+1}} + \ldots + A_{j_m} + 1 for each of the indices j_x.
Again, this gives us a lower bound on x, with the strictest one being the maximum value of the expression on the right.
With these two lower bounds on x, we can simply choose x to be the strictest one among them, and all the conditions are now guaranteed to be satisfied.
This method of computing x in terms of lower bounds is useful because we can avoid having to actually simulate the process.
In particular, suppose we’re solving for [L, R]. Let’s figure out what information is needed.
First, the negative part.
We need the sum S of all the elements in this range: that’s easily found using, say, prefix sums.
Then, for each negative number in the range, the bound on x obtained is its index (in [L, R]), minus the sum of negative numbers before it (again, in [L, R]), minus S.
We want to find the maximum of this across all negative numbers in [L, R].
To do that, let b be an array of length N such that b_i equals i minus the sum of negative numbers before index i.
If A_i \geq 0, set b_i to -\infty instead (practically, some very small number like -10^{18}).
Now, for [L, R], all we need to do is find the maximum value of b_i in this range; then subtract L-1 from it (to adjust indices to [L, R]) and also subtract all negative numbers before L from it (again to adjust to [L, R]).
The sum of negative numbers before L can be found using, once again, prefix sums.
This gives us one of the lower bounds on x.
A similar computation can be done to find the other bound, from the positive process: define c_i to be i plus the sum of positive elements at or after i, then we only want a range maximum of the c array, minus L-1 and minus all positive numbers after R.
The b and c arrays can be computed in linear time each, after which we only want range maximum queries on them, which is easily handled by a sparse table or segment tree.
Note that the above analysis was for the case when the subarray sum was positive.
If it’s negative, the analysis remains the same, just that positive and negative numbers swap roles.
To implement this without having to resort to extreme casework, write a method that deals only with positive sum subarrays and skips negative sums entirely.
Then, invoke this method once, after which you can simply negate all the elements of A and invoke it again - after all, negating all the elements of a subarray won’t change its answer.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct sparse_table {
/*============================*/
T merge(T a, T b) {
return max(a,b);
}
/*============================*/
vector<vector<T>> table;
vector<int> bin_log;
int LOG = 0;
sparse_table() {
}
sparse_table(vector<T> &a, int n) {
while ((1 << LOG) <= n) LOG++;
table = vector<vector<T>>(n, vector<T>(LOG));
bin_log = vector<int>(n + 1);
rep(i, n) table[i][0] = a[i];
rep1(j, LOG - 1) {
rep(i, n) {
int jump = 1 << (j - 1);
if (i + jump >= n) {
break;
}
table[i][j] = merge(table[i][j - 1], table[i + jump][j - 1]);
}
}
bin_log[1] = 0;
for (int i = 2; i <= n; ++i) {
bin_log[i] = bin_log[i / 2] + 1;
}
}
T query(int l, int r) {
int len = r - l + 1;
int k = bin_log[len];
T val1 = table[l][k];
T val2 = table[r - (1 << k) + 1][k];
return merge(val1, val2);
}
};
void solve(int test_case){
ll n,q; cin >> n >> q;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
vector<pll> queries(q+5);
rep1(i,q) cin >> queries[i].ff >> queries[i].ss;
vector<ll> ans(q+5);
auto go = [&](){
vector<ll> p(n+5), pp(n+5), pn(n+5), pabs(n+5), pnz(n+5);
rep1(i,n){
p[i] = p[i-1]+a[i];
pp[i] = pp[i-1], pn[i] = pn[i-1];
if(a[i] > 0) pp[i] += a[i];
else pn[i] += abs(a[i]);
pabs[i] = pabs[i-1]+abs(a[i]);
pnz[i] = pnz[i-1];
if(a[i]) pnz[i]++;
}
vector<ll> v1(n+5,-inf2), v2(n+5,-inf2);
rep1(i,n){
if(a[i] < 0){
v1[i] = i-pn[i-1];
}
if(a[i] > 0){
v2[i] = i-pp[i-1];
}
}
sparse_table<ll> st1(v1,n+1), st2(v2,n+1);
rep1(id,q){
auto [l,r] = queries[id];
ll s = p[r]-p[l-1];
if(!s){
ll c = pnz[r]-pnz[l-1];
if(c){
ans[id] = -1;
}
else{
ans[id] = 0;
}
conts;
}
if(s < 0) conts;
if(l == r){
ans[id] = abs(a[l]);
conts;
}
if(a[l] < 0){
s += abs(a[l]);
}
l++;
/*
ll mx1 = -inf2;
for(int i = l; i <= r; ++i){
if(a[i] < 0){
ll val = i-pn[i-1];
amax(mx1,val);
}
}
*/
ll mx1 = st1.query(l,r);
mx1 += -s+pn[l-1]-(l-2);
amax(mx1,0ll);
s += pn[r]-pn[l-1];
/*
ll mx2 = -inf2;
for(int i = l; i <= r; ++i){
if(a[i] > 0){
ll val = i-pp[i-1];
amax(mx2,val);
}
}
*/
ll mx2 = st2.query(l,r);
mx2 += -s+pp[r]-1-(l-2);
amax(mx2,0ll);
ans[id] = max(mx1,mx2)*2+pabs[r]-pabs[l-2];
}
};
go();
rep1(i,n) a[i] *= -1;
go();
rep1(i,q) cout << ans[i] << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
/**
* Point-update Segment Tree
* Source: kactl
* Description: Iterative point-update segment tree, ranges are half-open i.e [L, R).
* f is any associative function.
* Time: O(logn) update/query
*/
template<class T, T unit = T()>
struct SegTree {
T f(T a, T b) { return max(a, b); }
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<array<int, 2>> queries;
for (int i = 0; i < q; ++i) {
int l, r; cin >> l >> r;
queries.push_back({l, r});
}
vector<ll> ans(q);
for (int itr = 0; itr < 2; ++itr) {
vector<ll> pref(n + 1), abs_pref(n + 1);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i-1] + a[i-1];
abs_pref[i] = abs_pref[i-1] + abs(a[i-1]);
}
vector<int> next_nonzero(n + 1, n + 1);
for (int i = n; i >= 1; --i) {
if (a[i-1]) next_nonzero[i] = i;
else if (i < n) next_nonzero[i] = next_nonzero[i+1];
}
vector<ll> neg_val(n + 1, -1e18), neg_pref(n + 1);
ll npref = 0;
for (int i = 1; i <= n; ++i) {
if (a[i-1] < 0) {
neg_val[i] = i + npref;
npref += a[i-1];
}
neg_pref[i] = npref;
}
SegTree<ll, LLONG_MIN> nseg(n + 1);
for (int i = 1; i <= n; ++i)
nseg.update(i, neg_val[i]);
vector<ll> pos_val(n + 1, -1e18), pos_suf(n + 2);
ll psuf = 0;
for (int i = n; i >= 1; --i) {
if (a[i-1] > 0) {
psuf += a[i-1];
pos_val[i] = i + psuf;
}
pos_suf[i] = psuf;
}
SegTree<ll, LLONG_MIN> pseg(n + 1);
for (int i = 1; i <= n; ++i)
pseg.update(i, pos_val[i]);
for (int i = 0; i < q; ++i) {
auto [l, r] = queries[i];
ll sm = pref[r] - pref[l-1];
if (sm == 0) {
if (next_nonzero[l] > r) ans[i] = 0;
else ans[i] = -1;
continue;
}
if (sm < 0) continue;
ll extra = 0;
// lower bound on sm + x from negatives
auto neg_mx = nseg.query(l, r+1);
neg_mx -= neg_pref[l-1] + l-1;
extra = max(extra, neg_mx - sm);
sm -= neg_pref[r] - neg_pref[l-1];
// lower bound on sm + x + 1 from positives
auto pos_mx = pseg.query(l, r+1);
pos_mx -= pos_suf[r+1] + l-1;
extra = max(extra, pos_mx - sm - 1);
ans[i] = abs_pref[r] - abs_pref[l-1] + 2*extra;
}
for (auto &x : a) x *= -1;
}
for (auto x : ans) cout << x << '\n';
}
}