# BOMBBLAST - Editorial

Authors: d_k_7386, jalp1428
Tester: tabr
Editorialist: iceknight1093

2632

Sweep line

# PROBLEM:

Given an array of length N, initially filled with zeros, process Q updates on it of the following form:
Given an index i and a range x,

• For each 0 \leq j \leq x, add j\cdot (j+1) to A_{i+j}
• For each 0 \leq j \leq x, subtract j\cdot (j+1) from A_{i-j}

Print the final array after all updates are done.

# EXPLANATION:

Since we only need to find the final array after all operations are performed, the queries can be processed offline.

Notice that the addition/subtraction updates are symmetric, so let’s see how to handle only the addition updates; the subtractions can be handled similarly by reversing the array.

So, let’s look at a single update (i, x). We add j\cdot (j+1) to index A_{i+j}.
Let’s expand this into j^2 + j, which we’ll deal with separately.
As a result, we need to be able to:

• Add 1, 2, 3, \ldots to a range.
• Add 1^2, 2^2, 3^3, \ldots to a range.

Of course, this is doable using a segment tree; but below I’ll present a simpler solution without data structures.

First, let’s look at only adding 1, 2, 3, \ldots, R-L+1 to the range [L, R].
Let’s mark this update as starting at position L and ending at position R.

After doing this marking for every query, let’s iterate over positions of the array from 1 to N and analyze what happens.
Suppose we’ve computed the values of A_1, A_2, \ldots, A_i and now want to compute A_{i+1}.
When moving from index i to index i+1, we have the following changes:

• Every update that contributed a value of y to A_i will contribute a value of y+1 to A_{i+1}, since we’re moving one step right.
• That is, if A_i was affected by k distinct updates, i.e, A_i = y_1 + y_2 + \ldots + y_k, then these updates will contribute a value of (y_1 + 1) + (y_2 + 2) + \ldots + (y_k + 1), which simply equals A_i + k, to A_{i+1}.
• Notice that this change can be calculated in \mathcal{O}(1) if we know k, the number of ‘active’ updates. This can be easily maintained in a variable as we iterate.
• Second, every update that starts at index i+1 will contribute 1 to A_{i+1}.
• For each update that starts at index i+1, add 1 to A_{i+1}.
• Recall that we were also maintaining the number of ‘active’ updates, k. So, for each such new update, increase k by 1.
• Finally, every update that ends at index i should no longer be counted in the summation.
• For each update, we’ve already marked where it ends. When doing this, we can also store the final value of this update, at which point this final value can be directly subtracted from A_{i+1}.
• Once again, remember to subtract 1 from k so that the number of active updates is maintained correctly.

In this way, we can move from index i to index i+1 somewhat quickly.
Notice that each update is processed exactly twice: once when it starts, and once when it ends.
Apart from that, we do \mathcal{O}(1) work at each index, so the total complexity is just \mathcal{O}(N+Q).

Now, we’ve processed all updates of the form “add 1, 2, 3, \ldots, R-L+1 to [L, R]”.
We still need to process the updates of the form “add 1^2, 2^2, 3^2, \ldots, (R-L+1)^2 to [L, R]”.

In fact, that can be handled in almost the same way!

Recall that we had three separate parts when moving from index i to (i+1) — calculating the updated contribution of existing updates, dealing with updates that start at index i+1, and dealing with updates that ended at index i.

The second and third parts here are exactly the same: starting a new update adds 1 to the value of A_{i+1}, and when an update ends we’ve already stored its ending value, so just subtract its square from A_{i+1}.

The only difference here is the first part, i.e, updating the contribution of existing updates.
In particular, we have y_1^2 + y_2^2 + \ldots + y_k^2, and we want to compute (y_1 + 1)^2 + (y_2 + 1)^2 + \ldots + (y_k+1)^2.

This can be done by expanding out that summation to obtain

\sum_{i=1}^k \left (y_i+1 \right )^2 = \sum_{i=1}^k \left ( y_i^2 + 2y_i + 1\right) \\ = \sum_{i=1}^k y_i^2 + 2\sum_{i=1}^k y_i + k

Notice that we already know k and \sum_{i=1}^k y_i^2.
We also know \sum_{i=1}^k y_i, since that’s the value we were maintaining for the first part anyway!

So, once again all Q of the sum of squares updates can be processed in \mathcal{O}(N+Q) time.

Finally, do the same for the subtraction updates, and we’re done.

# TIME COMPLEXITY

\mathcal{O}(N + Q) per test case.

# CODE:

Setter's code (C++)
#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define s(a) (ll)a.size()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

ll add(ll x,ll y)  {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y)  {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y)  {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}

void solve(){
ll n,m; cin>>n>>m;
vector<pair<ll,pair<ll,ll>>> vec1,vec2;
vector<pair<ll,ll>> vec3;
loop(i,0,m){
ll a,b; cin>>a>>b;
vec1.pb({max(1ll,a-b),{a,b}});
vec2.pb({min(n,a+b),{a,b}});
vec3.pb({a,b});
}
ll i = 0,j = 0,k = 0;
sort(all(vec1));
sort(all(vec2));
sort(all(vec3));
ll sum1 = 0,sum2 = 0,sum3 = 0,sum4 = 0;
ll cnt1 = 0,cnt2 = 0;
loop(idx,1,n+1){
sum2-=(2*sum1 + cnt1);
sum1+=cnt1;
sum4+=(2*sum3+cnt2);
sum3+=cnt2;
while(i<m && vec1[i].fr == idx){
sum1-=vec1[i].sc.fr-idx;
sum2-=(vec1[i].sc.fr-idx)*(vec1[i].sc.fr-idx);
cnt1++;
i++;
}
cout<<sum1+sum2+sum3+sum4<<' ';
while(j < m && vec2[j].fr == idx){
cnt2--;
sum3-=idx-vec2[j].sc.fr;
sum4-=(vec2[j].sc.fr-idx)*(vec2[j].sc.fr-idx);
j++;
}
while(k < m && vec3[k].fr == idx){
cnt1--;
cnt2++;
k++;
}

}
cout<<endl;
}

int main()
{
fast
int t; cin>>t;
while(t--) solve();
return 0;
}

Tester's code (C++, segment tree)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int min_len, int max_len, const string &pattern = "") {
assert(min_len <= max_len);
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

struct segtree {
struct T {
long long c0;
long long c1;
long long c2;
long long l;
};

T e() {
return {0, 0, 0, 0};
}

T op(T x, T y) {
x.c0 += y.c0;
x.c1 += y.c0 * x.l;
x.c2 += y.c0 * (x.l * (x.l + 1) / 2);
x.c1 += y.c1;
x.c2 += y.c1 * x.l;
x.c2 += y.c2;
x.l += y.l;
return x;
}

int n;
int size;
vector<T> node;

segtree() : segtree(0) {}
segtree(int _n) {
build(vector<T>(_n, e()));
}
segtree(const vector<T> &v) {
build(v);
}

void build(const vector<T> &v) {
n = (int) v.size();
if (n <= 1) {
size = n;
} else {
size = 1 << (32 - __builtin_clz(n - 1));
}
node.resize(2 * size, e());
for (int i = 0; i < n; i++) {
node[i + size] = v[i];
}
for (int i = size - 1; i > 0; i--) {
node[i] = op(node[2 * i], node[2 * i + 1]);
}
}

void set(int p, T v) {
assert(0 <= p && p < n);
p += size;
node[p] = v;  // update
// node[p] += v;  // add
while (p > 1) {
p >>= 1;
node[p] = op(node[2 * p], node[2 * p + 1]);
}
}

T get(int l, int r) {
assert(0 <= l && l <= r && r <= n);
T vl = e();
T vr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) {
vl = op(vl, node[l++]);
}
if (r & 1) {
vr = op(node[--r], vr);
}
l >>= 1;
r >>= 1;
}
return op(vl, vr);
}

T get(int p) {
assert(0 <= p && p < n);
return node[p + size];
}
};

int main() {
input_checker in;
int sn = 0, sm = 0;
while (tt--) {
vector<int> a(m), b(m);
for (int i = 0; i < m; i++) {
a[i]--;
}
vector<long long> c(n);
for (int z = 0; z < 2; z++) {
segtree seg(n + 1);
for (int i = 0; i < n + 1; i++) {
seg.set(i, {0, 0, 0, 1});
}
vector<vector<int>> e(n);
for (int i = 0; i < m; i++) {
e[max(0, a[i] - b[i])].emplace_back(a[i]);
}
vector<int> f(n);
for (int i = 0; i < n; i++) {
for (int j : e[i]) {
f[j]++;
seg.set(j, {f[j], f[j], f[j], 1});
}
c[i] += seg.get(i + 1, n + 1).c2;
}
for (int i = 0; i < m; i++) {
a[i] = n - 1 - a[i];
}
reverse(c.begin(), c.end());
if (z == 0) {
for (int i = 0; i < n; i++) {
c[i] *= -1;
}
}
}
for (int i = 0; i < n; i++) {
cout << c[i] * 2 << " \n"[i == n - 1];
}
}
assert(sn <= 2e5);
assert(sm <= 2e5);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
inc_updates = [ [ ] for _ in range(n+1)]
dec_updates = [ [ ] for _ in range(n)]
for i in range(m):
pos, x = map(int, input().split())
pos -= 1

ans = [0]*n
ct, sm, sqsm = 0, 0, 0
for i in range(n):
sqsm += 2*sm + ct
sm += ct

if x == 1:
ct += 1
sm += 1
sqsm += 1
else:
ct -= 1
sm += x
sqsm -= x**2
ans[i] = sm + sqsm

ct = sm = sqsm = 0
for i in reversed(range(n)):
sqsm += 2*sm + ct
sm += ct

if x == 1:
ct += 1
sm += 1
sqsm += 1
else:
ct -= 1
sm += x
sqsm -= x**2
ans[i] -= sm + sqsm
print(*ans)


There is also a way to solve this using the difference array of A and two seg trees, in time O((N + Q)\log N). The unfortunate part is that this requires using __int128_t and is a bit slow (my solution ran in 0.87 seconds)

In particular, let B_j = A_j - A_{j-1}. Then, consider an update (X, Y) where for convenience let’s 0-index X. Then, if j\le X, it follows that A_j decreases by (X - j)(X - j + 1) and A_{j-1} by (X - j + 1)(X - j + 2). So, B_j increases by 2(X - j + 1) = 2(X + 1) - 2j. In the first seg tree, we will store updates of the first form (that is, adding 2(X + 1) to each entry in [X - Y, X] and in the second seg tree we will store updates of the second form (that is, subtracting 2 from each entry in [X - Y, X].

If j > X, then we can similarly find that B_j increases by 2j - 2X so update first seg tree by -2X and second segtree by +2.

Finally, we have the boundaries: at Z = max(0, X - Y), B_Z decreases by (X - Z)(X - Z+1) and at W = min(n - 1, X + Y), B_{W + 1} decreases by (W - X)(W - X + 1).

Now, after constructing the difference array we can query it and reconstruct the original array A as well.

2 Likes

on what test case my solution fails ?? . If it is an overflow how shall I fix it ? . why my code doesnt handles overflow (if any)?

#include<bits/stdc++.h>
using namespace std;

int getl(int xi,int xj){
return max(1,xi-xj);
}
int getr(int xi,int xj,int n){
return min(xi+xj,n);
}

int main(){
int t,n,m,xi,yi,l,r;
cin>>t;
while(t–){
cin>>n>>m;
long long int p1_l[n+2]={0};
long long int p2_l[n+2]={0};
long long int p1_r[n+2]={0};
long long int p2_r[n+2]={0};
int f_l[n+2]={0};
int f_r[n+2]={0};
for(int i=0;i<m;i++){
cin>>xi>>yi;

  l=getl(xi,yi);
r=getr(xi,yi,n);
if(l<xi){
p1_l[l]+=xi;
p1_l[xi+1]-=xi;

p2_l[l]-=static_cast<long long int>(xi)*xi;
p2_l[xi+1]+=static_cast<long long int>(xi)*xi;

f_l[l]-=1;
f_l[xi+1]+=1;

}
if(r>xi){
f_r[xi]+=1;
f_r[r+1]-=1;

p2_r[xi]+=static_cast<long long int>(xi)*xi;
p2_r[r+1]-=static_cast<long long int>(xi)*xi;

p1_r[xi]-=xi;
p1_r[r+1]+=xi;
}
}

for(int i=1;i<n+2;i++){
p1_l[i]+=p1_l[i-1];
p1_r[i]+=p1_r[i-1];
p2_l[i]+=p2_l[i-1];
p2_r[i]+=p2_r[i-1];
f_l[i]+=f_l[i-1];
f_r[i]+=f_r[i-1];
}

long long int ans =0;
for(int j=1;j<=n;j++){
ans = (static_cast<long long int>(f_l[j])*(j*j-j));
ans += (static_cast<long long int>(2*j-1)*(p1_l[j]));
ans += p2_l[j];
ans += p2_r[j];
ans += (static_cast<long long int>(p1_r[j]*(2*j+1)) );
ans += (static_cast<long long int>(f_r[j])*(j*j+j));
cout << ans << " ";
}
cout <<"\n";


}
}

Here is a short implementation of mine, I hope it is easy to understand

Can someone explain how to add 1,2,3… in range using segment trees?

Arithmetic Progression Range Update/(Max,Min) Query - Codeforces refer to this blog.