PROBLEM LINK:
Author: freemancs
Tester: pulkit_0110
Editorialist: freemancs
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Basic observations, segment tree or fenwick tree
PROBLEM:
You have to update your array based on the given values in each query,and
output certain soldiers strength
EXPLANATION:
(approach using segment tree)
Create two different arrays for each army and initialize it with 1
(this arrays signify multiplication factor of each soldier)
now update the range based on queries
update range of winning kingdom by increasing their factor by 1 and
update range of losing kingdom by decreasing their factor by 1.
Both these operations can be done in O(Logn) time
and finally output the soldiers current strength by quering the multiplication factor in O(Logn) time and multiplying it with initital strength of that soldier
ALTERNATE EXPLANATION:
The same thing can be done using Fenwick tree
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int n,m,q;
vector<int> army1;
vector<int> army2;
vector<int> delta1 , delta2;
void update1(int l ,int r, int curr,int a ,int b ,int val){
//no overlap
if(a > r || b < l){
return ;
}
//complete overlap
if(l >= a && r <= b){
delta1[curr] += val;
return ;
}
//partial overlap
int mid = l + (r-l)/2;
if(delta1[curr] != 0){
delta1[2*curr] += delta1[curr];
delta1[2*curr+1] += delta1[curr];
delta1[curr] = 0;
}
update1(l,mid,2*curr, a, b, val);
update1(mid+1,r ,2*curr+1,a,b,val);
return;
}
void update2(int l ,int r, int curr,int a ,int b ,int val){
//no overlap
if(a > r || b < l){
return ;
}
//complete overlap
if(l >= a && r <= b){
delta2[curr] += val;
return;
}
//partial overlap
int mid = l + (r-l)/2;
if(delta2[curr] != 0){
delta2[2*curr] += delta2[curr];
delta2[2*curr+1] += delta2[curr];
delta2[curr] = 0;
}
update2(l,mid,2*curr, a, b, val);
update2(mid+1,r ,2*curr+1,a,b,val);
return;
}
int query1(int l ,int r ,int curr ,int pos){
//no overlap
if(l > pos || r < pos){
return 0;
}
//complete overlap
if(l == r && l == pos){
return delta1[curr];
}
//partial overlap
int mid = l + (r-l)/2;
if(delta1[curr] != 0){
delta1[2*curr] += delta1[curr];
delta1[2*curr+1] += delta1[curr];
delta1[curr] = 0;
}
int num = query1(l , mid , 2*curr , pos) + query1(mid + 1, r , 2*curr+1 , pos);
return num;
}
int query2(int l ,int r ,int curr ,int pos){
//no overlap
if(l > pos || r < pos){
return 0;
}
//complete overlap
if(l == r && l == pos){
return delta2[curr];
}
//partial overlap
int mid = l + (r-l)/2;
if(delta2[curr] != 0){
delta2[2*curr] += delta2[curr];
delta2[2*curr+1] += delta2[curr];
delta2[curr] = 0;
}
int num = query2(l , mid , 2*curr , pos) + query2(mid + 1, r , 2*curr+1 , pos);
return num;
}
void build1(int l ,int r ,int curr){
if(l == r){
delta1[curr] = 1;
return ;
}
int mid = l + (r-l)/2;
build1(l,mid , 2*curr);
build1(mid+1, r , 2*curr+1);
}
void build2(int l ,int r ,int curr){
if(l == r){
delta2[curr] = 1;
return ;
}
int mid = l + (r-l)/2;
build2(l,mid , 2*curr);
build2(mid+1, r , 2*curr+1);
}
int main(){
cin >> n >> m >> q;
army1.resize(n+1);
army2.resize(m+1);
for(int i =1 ; i<=n ;i++)cin >> army1[i];
for(int i =1 ; i<=m ;i++)cin >> army2[i];
delta1.assign(4*n+1, 0);
delta2.assign(4*m+1 ,0);
build1(1, n , 1);
build2(1, m , 1);
while(q--){
int a,b,c,d,k,pos;
cin >> a >> b >> c >> d >> k >> pos;
ll ans;
if(k == 1){
update1(1,n,1,a,b,1);
update2(1,m,1,c,d,-1);
//cerr<<"hi\n";
ans = (ll)query1(1,n,1,pos)*(ll)army1[pos];
}
else{
update1(1,n,1,a,b,-1);
update2(1,m,1,c,d,1);
ans = (ll)query2(1,m,1,pos)*(ll)army2[pos];
}
cout<<ans<<"\n";
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pb push_back
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const int N=200000+10;
//={0};
int fen1[N]={0};
int fen2[N]={0};
void update1(int i,int add)
{
while(i<N)
{
fen1[i]+=add;
i+=(i&(-i));
}
}
int sum1(int i)
{
int s=0;
while(i>=1)
{
s+=fen1[i];
i=i-(i&(-i));
}
return s;
}
void update2(int i,int add)
{
while(i<N)
{
fen2[i]+=add;
i+=(i&(-i));
}
}
int sum2(int i)
{
int s=0;
while(i>=1)
{
s+=fen2[i];
i=i-(i&(-i));
}
return s;
}
main()
{
fast();
int t=1;
// cin>>t;
while(t--)
{
int n,m,q;
cin>>n>>m>>q;
int arr1[n+1];
for(int i=1;i<=n;i++)
cin>>arr1[i];
int arr2[m+1];
for(int i=1;i<=m;i++)
cin>>arr2[i];
while(q--)
{
int a,b,c,d,k,pos;
cin>>a>>b>>c>>d>>k>>pos;
if(k==1)
{
update1(a,1);
update1(b+1,-1);
update2(c,-1);
update2(d+1,1);
}
else
{
update1(a,-1);
update1(b+1,+1);
update2(c,1);
update2(d+1,-1);
}
if(k==1)
{
cout<<arr1[pos]+sum1(pos)*arr1[pos]<<endl;
}
if(k==2)
{
cout<<arr2[pos]+sum2(pos)*arr2[pos]<<endl;
}
}
}
}