# TWOARM-EDITORIAL

Author: freemancs
Tester: pulkit_0110
Editorialist: freemancs

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};
{
while(i<N)
{
i+=(i&(-i));
}
}
int sum1(int i)
{
int s=0;
while(i>=1)
{
s+=fen1[i];
i=i-(i&(-i));
}
return s;
}
{
while(i<N)
{
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;
}

}
}

}
``````
1 Like

i guess u could have made much better editorialâ€¦lot of ppl make very descriptive i guess which is very helpfulâ€¦if u would have explained it in detail it would have helped a lotâ€¦so plss make the editorial a little bit descriptive not very much but thoda to rakho yrrâ€¦!!!