PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: d_k_7386, jalp1428
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
2632
PREREQUISITES:
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
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);
}
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
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);
long long res = stoll(readOne());
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++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
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++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
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 tt = in.readInt(1, 1e5);
in.readEoln();
int sn = 0, sm = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
in.readSpace();
int m = in.readInt(1, 2e5);
in.readEoln();
vector<int> a(m), b(m);
for (int i = 0; i < m; i++) {
a[i] = in.readInt(1, n);
in.readSpace();
b[i] = in.readInt(1, n);
in.readEoln();
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);
in.readEof();
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
inc_updates[pos+1].append(1)
if pos+x+1 < n: inc_updates[pos+x+1].append(-x-1)
if pos > 0: dec_updates[pos-1].append(1)
if pos-x-1 >= 0: dec_updates[pos-x-1].append(-x-1)
ans = [0]*n
ct, sm, sqsm = 0, 0, 0
for i in range(n):
sqsm += 2*sm + ct
sm += ct
for x in inc_updates[i]:
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
for x in dec_updates[i]:
if x == 1:
ct += 1
sm += 1
sqsm += 1
else:
ct -= 1
sm += x
sqsm -= x**2
ans[i] -= sm + sqsm
print(*ans)