PROBLEM LINK:
Author: Vaishakh SM
Tester: Smit Mandavia
Editorialist: Vaishakh SM
DIFFICULTY:
Easy
PREREQUISITES:
Knowledge of prefix sums
PROBLEM:
Given an array, A of size N initially filled with 0's, for each query containing two integers L,R add 1 to A[L] , 2 to A[L+1] … R-L+1 to A[R]. In general, add i+1 to A[L+i] for every L\leq i \leq R.
QUICK EXPLANATION:
- In an array initially filled with 0's, use standard prefix sums to first add 1 to each L,R query, let this array be B.
- Subtract R-L+1 from A[R+1] for each query (store the queries beforehand)
- Take prefix sum of B and print B[1] to B[N]
EXPLANATION:
Let us first try to solve a simpler question, how can we add 1 to each L,R query, we will later see how the original question is essentially the same as this simpler question.
For adding 1 to each L,R query, we first start with an array filled with 0's (say A), then we add 1 to each A[L] and subtract 1 from each A[R]. Then we take the prefix sum of A.
Now, observe that if we take the prefix sum of 1,1,1,-3, we get 1,2,3,0. Hence we have added 1,2,3 to A[0], A[1],A[2] respectively. Using this logic we can see that in general if we have M, 1's in an array followed by -M and if we take the prefix sum of the array we have added 1,2,... M to the first M indices of the array.
Hence, we will first add 1 in an initially empty array for each L,R query, then we will subtract R-L+1 from A[R+1] for each query and take prefix sum again to get the desired result.
TIME COMPLEXITY
Time complexity is O(N + Q), where N is size of array and Q is number of queries for each testcase.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main()
{
lli t,n,q,l,r;
cin>>t;
while(t--)
{
cin>>n>>q;
vector<lli> arr(n+3);
vector<pair<lli,lli>> Indices;
while(q--)
{
cin>>l>>r;
arr[l]++;
arr[r+1]--;
// Adding 1 to arr[l] and subtracting 1
// from arr[r+1] as mentioned in editorial
Indices.push_back({l,r+1});
}
for(int i =1;i<=n;i++)
{
arr[i]+=(arr[i-1]);
}
// Taking prefix sum to add 1 to each L,R query
for(auto x:Indices) arr[x.second]-=(x.second-x.first);
// After generating the array where the queries are increased with 1
// I am subtracting R-L+! to r+1th index
for(int i =1;i<=n;i++)
{
arr[i]+=(arr[i-1]);
}
// Taking prefix sum again
for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
//Final output
cout<<endl;
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
cerr << (int)g << "\n";
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int main()
{
FIO;
int t,n,q,k,i,j,sum_n,sum_q;
t=readIntLn(1,1000);
sum_n=0;
sum_q=0;
while(t--){
n=readIntSp(1,100000);
q=readIntLn(1,100000);
sum_n+=n;
sum_q+=q;
ll arr[n+3]={0};
while(q--){
j=readIntSp(1,n);
k=readIntLn(j,n);
arr[j]++;
arr[k+1]--;
arr[k+1]-=(k-j+1);
arr[k+2]+=(k-j+1);
}
for(i=1;i<=n;i++)
arr[i]+=arr[i-1];
for(i=1;i<=n;i++)
arr[i]+=arr[i-1];
for(i=1;i<=n;i++)
cout << arr[i] << " ";
cout << "\n";
}
assert(getchar()==-1);
assert(sum_n<=1000000);
assert(sum_q<=1000000);
return 0;
}