#include<iostream>
#include<string.h>
long long int arr[1000005],seg[10000005],lzy[10000005];
using namespace std;
#define inf 100000001
int ups,upe,qs,qe;//qs = query start index , qe= query end index
long long int val;// ups = update start index , upe =update end index
long long int qry(int index,int start,int end)
{
if(lzy[index]!=0)
{
seg[index]+=lzy[index]*(end-start+1);
if(start!=end)
{
lzy[2*index]+=lzy[index];
lzy[2*index+1]+=lzy[index];
}
lzy[index]=0;
}
if(start>end || end<qs || start>qe)
{
return 0;
}
if(start>=qs && end<=qe)
{
return seg[index];
}
long long int q1=qry(2*index,start,(start+end)/2);
long long int q2=qry(2*index+1,((start+end)/2)+1,end);
return q1+q2;
}
void update(int index,int start,int end)
{
if(lzy[index]!=0)// means index contain some un updated range so update seg tree and make its child lazy if have child
{
seg[index]+=lzy[index]*(end-start+1);
// checking if having child than make it lzy
if(start!=end)// adding lzy[index] bcos making parent unlaxy and if parent have any child tnhan mak it lazy equal
// exactly to its parent amount .......
{
lzy[2*index]+=lzy[index];
lzy[2*index+1]+=lzy[index];
}
lzy[index]=0;
}
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 )...
{
seg[index]+=(end-start+1)*val;// just update the parent and make its chile lzy so thate will be update latter
if(start!=end)/// adding only val sice it is new dew it is not propogating from parent
{
lzy[2*index]+=val;
lzy[2*index+1]+=val;
}
return;
}
update(2*index,start,(start+end)/2);
update(2*index+1,((start+end)/2)+1,end);
seg[index]=seg[2*index]+seg[2*index+1];
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,q;
cin>>n>>q;
memset(seg,0,10000001);
memset(lzy,0,10000001);
while(q--)
{
int qq;
cin>>qq;
if(qq==0)
{
cin>>ups>>upe>>val;
ups-=1;
upe-=1;
update(1,0,n-1);
}
else
{
cin>>qs>>qe;
qs-=1;
qe-=1;
long long int ans= qry(1,0,n-1);
cout<<ans<<endl;
}
}
}
return 0;
}
#include<string.h>
long long int arr[1000005],seg[10000005],lzy[10000005];
using namespace std;
#define inf 100000001
int ups,upe,qs,qe;//qs = query start index , qe= query end index
long long int val;// ups = update start index , upe =update end index
long long int qry(int index,int start,int end)
{
if(lzy[index]!=0)
{
seg[index]+=lzy[index]*(end-start+1);
if(start!=end)
{
lzy[2*index]+=lzy[index];
lzy[2*index+1]+=lzy[index];
}
lzy[index]=0;
}
if(start>end || end<qs || start>qe)
{
return 0;
}
if(start>=qs && end<=qe)
{
return seg[index];
}
long long int q1=qry(2*index,start,(start+end)/2);
long long int q2=qry(2*index+1,((start+end)/2)+1,end);
return q1+q2;
}
void update(int index,int start,int end)
{
if(lzy[index]!=0)// means index contain some un updated range so update seg tree and make its child lazy if have child
{
seg[index]+=lzy[index]*(end-start+1);
// checking if having child than make it lzy
if(start!=end)// adding lzy[index] bcos making parent unlaxy and if parent have any child tnhan mak it lazy equal
// exactly to its parent amount .......
{
lzy[2*index]+=lzy[index];
lzy[2*index+1]+=lzy[index];
}
lzy[index]=0;
}
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 )...
{
seg[index]+=(end-start+1)*val;// just update the parent and make its chile lzy so thate will be update latter
if(start!=end)/// adding only val sice it is new dew it is not propogating from parent
{
lzy[2*index]+=val;
lzy[2*index+1]+=val;
}
return;
}
update(2*index,start,(start+end)/2);
update(2*index+1,((start+end)/2)+1,end);
seg[index]=seg[2*index]+seg[2*index+1];
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,q;
cin>>n>>q;
memset(seg,0,10000001);
memset(lzy,0,10000001);
while(q--)
{
int qq;
cin>>qq;
if(qq==0)
{
cin>>ups>>upe>>val;
ups-=1;
upe-=1;
update(1,0,n-1);
}
else
{
cin>>qs>>qe;
qs-=1;
qe-=1;
long long int ans= qry(1,0,n-1);
cout<<ans<<endl;
}
}
}
return 0;
}
No comments:
Post a Comment