Utkarsh and Party Row House
In the college where Utkarsh studies, all the students live in N Row Houses. The colony containing the Row Houses is a straight line = x axis. Ith Row House is located at x = i and Ai students live in it.
Every week the students of some Row House at x=K organize a party and invite all the students living in Row Housesfrom x=L to x=R.
Utkarsh wants you to handle Q events. An event can be one of the following 2 types.
- 1 K L R: Row House at x=K organizes a party and invites all students living in Row House from x=L to x=R. Tell thesum of distance traveled by all the guests.
If a guest is at x=i and party is at x=j then distance travelled by him alone is |i - j|. - 2 K S: S new students are admitted into the college and all of them start to live in Row House at x=K
Input format:
The first line contains 2 integers N and Q.
The second line contains N integers denoting entries of A.
The first line contains 2 integers N and Q.
The second line contains N integers denoting entries of A.
Output format:
Print the result to all events of type 1.
Print the result to all events of type 1.
Constraints:
1 ≤ N, Q ≤ 105
1 ≤ L ≤ R ≤ N
1 ≤ K ≤ N
1 ≤ Ai, S ≤ 105
1 ≤ N, Q ≤ 105
1 ≤ L ≤ R ≤ N
1 ≤ K ≤ N
1 ≤ Ai, S ≤ 105
NOTE: Row Houses are 1-indexed
Sample Input
(Plaintext Link)6 4 1 1 1 1 1 1 1 1 5 6 1 6 1 5 2 1 1 1 6 1 5
Sample Output
(Plaintext Link)9 15 20
----------------------------------------------------------editorial----------------------------------------------------------------------------------------------
SUPPOSE the given array is a1,a2,a3,a4,a5,a6,a7 ...........ak
l=2, r=6 and party is organise at he index k soo tha answer will be
a2*(2-k)+ a3*(3-k)+a4*(4-k)+a5*(5-k)+a6*(6-k)
if we simplify this equation than we find it as
abs( (a3+a4+a5+a6)*k -- (2*a2+ 3*a3+4*a4+5*a5+6*a6) )
so we can do this usinh 2 segment tree first seg tree will containg sum of l to r and 2nd segment tree contain sum of i to r multiply with its index(ie. l*al+(l+1)*al+1.......)
we need to maintain special case if k is in mid of l t to r
than we need to call 2 segment call on each segment tree ie query1(l,k-1) , query2(l,k-1) , query1(k+1,r) query2(k+1,r)
---------------------------------------------------------------event editorial---------------------------------------------------------------------------
Let's consider an example query of the first type with K < L < = R. We should calculate sum a[i]*(i - K) where L <= i <= R. We can rewrite it as sum a[i]*i over L <= i <= R minus sum of a[i] L <= i <= R multiply K. So from this form we can notice that if we can calculate sum of a[i] * i qucily we can answer the queriers of the type 1 qucickly.
So we need some data structure which can do 2 operations in reasonable time:
1) find sum on segment 2) update value in some node
Fenwick tree or segment tree will do the job perfectly. We have 3 Fenwick tree
1) for going to the left each node has value a[i]*i
2) for going to the right each node has value a[i]*(n - i + 1)
3) for usual sum on segment each node has value a[i] So how we do process queries:
1) 1 L R K the answer will be sum in our Fenwick tree over the nodes L <= i <= R minus sum of K*a[i] for L <= i <= R.
2) 2 K S. We add K*S to the node K in the first Fenwick tree, (N - K + 1)*S to the node K in the second Fenwick tree andS to the node K in the third Fenwick tree.
-------------------------------------------------------------------code-----------------------------------------------------------------------------------------
#include<iostream>typedef long long int lli;
#include<bits/stdc++.h>
#include<string.h>
long long int arr[1000005],seg1[10000005],seg2[10000005];
using namespace std;
#define inf 100000001
int ups,upe,qs,qe;
long long int val;
long long int qry1(int index,int start,int end)
{
if(start>end || end<qs || start>qe)
{
return 0;
}
if(start>=qs && end<=qe)
{
return seg1[index];
}
long long int q1=qry1(2*index,start,(start+end)/2);
long long int q2=qry1(2*index+1,((start+end)/2)+1,end);
return q1+q2;
}
long long int qry2(int index,int start,int end)
{
if(start>end || end<qs || start>qe)
{
return 0;
}
if(start>=qs && end<=qe)
{
return seg2[index];
}
long long int q1=qry2(2*index,start,(start+end)/2);
long long int q2=qry2(2*index+1,((start+end)/2)+1,end);
return q1+q2;
}
void build1(int index,int start,int end)
{
if(start>end ) return;
else if(start==end)
{
seg1[index]=arr[start];
return ;
}
else
{
int mid=(start+end)/2;
build1(2*index,start,mid);
build1(2*index+1,mid+1,end);
seg1[index]=seg1[2*index]+seg1[2*index+1];
return ;
}
}
void build2(int index,int start,int end)
{
if(start>end ) return;
else if(start==end)
{
seg2[index]=arr[start]*(start+1);
return ;
}
else
{
int mid=(start+end)/2;
build2(2*index,start,mid);
build2(2*index+1,mid+1,end);
seg2[index]=seg2[2*index]+seg2[2*index+1];
return ;
}
}
void update1(int index,int start,int end)
{
if(start>end || start>upe || end<ups) return ;// if(range in complitly out of range sooo need not to update ;;;;)
if(start>=ups && end<=upe)// ( means if range (start and end ) is complitle within the update qry )...
{
seg1[index]+=(end-start+1)*val;// just update the parent and make its chile lzy so thate will be update latter
return;
}
update1(2*index,start,(start+end)/2);
update1(2*index+1,((start+end)/2)+1,end);
seg1[index]=seg1[2*index]+seg1[2*index+1];
}
void update2(int index,int start,int end)
{
if(start>end || start>upe || end<ups) return ;// if(range in complitly out of range sooo need not to update ;;;;)
if(start>=ups && end<=upe)// ( means if range (start and end ) is complitle within the update qry )...
{
seg2[index]+=val;// just update the parent and make its chile lzy so thate will be update latter
return;
}
update2(2*index,start,(start+end)/2);
update2(2*index+1,((start+end)/2)+1,end);
seg2[index]=seg2[2*index]+seg2[2*index+1];
}
int main()
{
int n,q;
cin>>n>>q;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
build1(1,0,n-1);
build2(1,0,n-1);
while(q--)
{
int t;
cin>>t;
if(t==1)
{
int k,l,r;
cin>>k>>l>>r;
l--;
k--;
r--;
lli sub=0;
lli add=0;
if(r<k || l>k)
{
qs=l;
qe=r;
sub=qry1(1,0,n-1);
add=qry2(1,0,n-1);
cout<<abs(add-(k+1)*sub)<<endl;
}
else
{
lli sub1=0,sub2=0,add1=0,add2=0;
qs=l;
qe=k-1;
sub1+=qry1(1,0,n-1);
add1+=qry2(1,0,n-1);
// cout<<sub1<<" "<<add1<<endl;
qs=k+1;
qe=r;
sub2+=qry1(1,0,n-1);
add2+=qry2(1,0,n-1);
// sub1*=(k+1);
lli t1=abs(add1-(k+1)*sub1);
lli t2=abs(add2-(k+1)*sub2);
lli res=t1+t2;
// cout<<t1<<" "<<t2<<endl;
cout<<res<<endl;
}
}
else
{
cin>>ups>>val;
ups--;
upe=ups;
update1(1,0,n-1);
val*=(ups+1);
update2(1,0,n-1);
}
}
}
No comments:
Post a Comment