# Light OJ: 1267 – Points in Rectangle (II)

0

Solution Idea:

This problem is similar to Codeforces gym 101484: B. Nicoleta’s Cleaning. We need a line sweep technique and some data structure to solve this problem. We need to convert each rectangle to opening and closing with respect to its x coordinates. Then we need to sort all points and open and close together. then for each opening element we need to count how many points are before opening point let is is X and for each closing, we need to count how many points are before and on the closing point in the range, lower y coordinate to upper y coordinate let it is Y. Then the number of points inside the rectangle is Y-X. For each given point we need to update it when we find it through scan line in x coordinate of it.

```#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
int type,x,st,ed,id;
};

vector<int>x,y;
vector<data>v;

bool cmp(data a, data b)
{
if(a.x<b.x) return true;
if(a.x==b.x)
return a.type<b.type;
return false;
}

#define mx 300005

int tree[mx];

void update(int idx, int val)
{
for(; idx<mx && idx; idx+=(idx&-idx))
tree[idx]+=val;
}

int query(int idx)
{
int ret=0;
for(; idx; idx-=(idx&-idx))
ret+=tree[idx];
return ret;
}

int ans[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
int t;
sf(t);
TEST_CASE(t)
{
int n,m;
sff(n,m);
for(int i=0; i<n; i++)
{
int a,b;
sff(a,b);
data temp;
temp.type=2;
temp.x=a;
temp.ed=temp.st=b;
v.pb(temp);
x.pb(a);
y.pb(b);
}

for(int i=0; i<m; i++)
{
int a,b,c,d;
sff(a,b);
sff(c,d);
x.pb(a);
x.pb(c);
y.pb(b);
y.pb(d);
data temp;
temp.type=3;
temp.x=c;
temp.st=b;
temp.ed=d;
temp.id=i;
v.pb(temp);
data temp1;
temp1.type=1;
temp1.x=a;
temp1.st=b;
temp1.ed=d;
temp1.id=i;
v.pb(temp1);
}

//    sort(all(x));
sort(all(y));
sort(all(v),cmp);

for(int i=0; i<SZ(v); i++)
{
data temp=v[i];
if(temp.type==1)
{
int a=lower_bound(all(y),temp.st)-y.begin()+1;
int b=lower_bound(all(y),temp.ed)-y.begin()+1;
int xx=query(b);
int yy=query(a-1);
ans[temp.id]=xx-yy;
}
else if(temp.type==3)
{
int a=lower_bound(all(y),temp.st)-y.begin()+1;
int b=lower_bound(all(y),temp.ed)-y.begin()+1;
int xx=query(b);
int yy=query(a-1);
ans[temp.id]=(xx-yy)-ans[temp.id];
}
else
{
int a=lower_bound(all(y),temp.st)-y.begin()+1;
update(a,1);
//            int yy=query(a-1); // Never do this while range update on BIT -_-
//            ans[temp.id]=xx;
}
}

LINE_PRINT_CASE;
for(int i=0; i<m; i++)
printf("%d\n",ans[i]);
ms(tree,0);
x.clear();
y.clear();
v.clear();
}
return 0;
}```

# Codeforces gym 101484: B. Nicoleta’s Cleaning

1

Solution Idea:

To solve this problem we need line sweep technique and some data structure. At first convert each rectangle in two element with respect to it x coordinate which both x coordinate have same y coordinates. Now call first x point opening and 2nd x point closing of a rectangle. Now take a array of custom data type. and store every opening and closing of rectangles and the query points and sort the the array in the basis of x coordinate of each element and in case of a tie take closing element first then query point and then opening point.

Now run a loop on the x axis and update every range by 1 if we find a opening and by -1 if we find a closing and if we find a query point just query the value of that point.

Handle the boundary condition carefully.

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
int type,x,st,ed,id;
};

vector<int>x,y;
vector<data>v;

bool cmp(data a, data b)
{
if(a.x<b.x) return true;
if(a.x==b.x)
return a.type<b.type;
return false;
}

#define mx 300005

int tree[mx];

void update(int idx, int val)
{
for(; idx<mx && idx; idx+=(idx&-idx))
tree[idx]+=val;
}

int query(int idx)
{
int ret=0;
for(; idx; idx-=(idx&-idx))
ret+=tree[idx];
return ret;
}

int ans[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

int n,m;
sff(n,m);
for(int i=0; i<n; i++)
{
int a,b;
sff(a,b);
data temp;
temp.type=2;
temp.x=a;
temp.ed=temp.st=b;
temp.id=i;
v.pb(temp);
x.pb(a);
y.pb(b);
}

for(int i=0; i<m; i++)
{
int a,b,c,d;
sff(a,b);
sff(c,d);
x.pb(a);
x.pb(c);
y.pb(b);
y.pb(d);
data temp;
temp.type=1;
temp.x=c;
temp.st=b;
temp.ed=d;
v.pb(temp);
data temp1;
temp1.type=3;
temp1.x=a;
temp1.st=b;
temp1.ed=d;
v.pb(temp1);
}

//    sort(all(x));
sort(all(y));
sort(all(v),cmp);

for(int i=0; i<SZ(v); i++)
{
data temp=v[i];
if(temp.type==1)
{
int a=lower_bound(all(y),temp.st)-y.begin()+1;
int b=lower_bound(all(y),temp.ed)-y.begin()+1;
update(a+1,-1);
update(b,+1);
}
else if(temp.type==3)
{
int a=lower_bound(all(y),temp.st)-y.begin()+1;
int b=lower_bound(all(y),temp.ed)-y.begin()+1;
update(a+1,+1);
update(b,-1);
}
else
{
int a=lower_bound(all(y),temp.st)-y.begin()+1;
int xx=query(a);
//            int yy=query(a-1); // Never do this while range update on BIT -_-
ans[temp.id]=xx;
}
}

for(int i=0; i<n; i++)
printf("%d\n",ans[i]);

return 0;
}

```

# Hackerrank: Solve the Queries!

0

Solution Idea:

The main observation in this problem is the given numbers are <=100 and there are 25 prime number less than 100. As we need to answer whether a range multiplication is multiple of another range multiplication or not.

We know when we multiply two number their prime power is added. For example 12*18 = (2^2 * 3^1) * (2^1 * 3^2)
= (2^(2+1) * 3^(1+2))
= (2^3 * 3^3)
= 216

So we can store prime factors of every given number in each segment tree leaf. And while merging two leaf node we need to add each prime power between two two leafs. So a node in the segment tree hold the information about the nubmer in the subtree of this node has how many ith prime divisor.

Now for each query we can get the power factor of each range from the segment tree and check whether they divides or not and produce the required answer from this prime factors.

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int prime[30]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int mp[100];

#define mx 50005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
int lazy;
int ara[25];
};

data ret;

int numbers[mx];
data tree[3*mx];

void func(int n, data &temp, int mul)
{
ms(temp.ara,0);
for(int i=0; i<25 && prime[i]*prime[i]<=n; i++)
{
if(n%prime[i]==0)
{
while(n%prime[i]==0)
{
n/=prime[i];
temp.ara[i]++;
}
temp.ara[i]*=mul;
}
}

if(n>1)
temp.ara[mp[n]]+=mul;
}

void push_up(data &a, data &b, data &c)
{
for(int i=0; i<25; i++)
a.ara[i]=b.ara[i]+c.ara[i];
}

void push_down(int n, int b, int e)
{
if(tree[n].lazy)
{
segment_tree;
func(tree[n].lazy,tree[l],mid-b+1);
func(tree[n].lazy,tree[r],e-mid);
tree[l].lazy=tree[n].lazy;
tree[r].lazy=tree[n].lazy;
tree[n].lazy=0;
}
}

void init(int n, int b, int e)
{
if(b==e)
{
tree[n].lazy=0;
func(numbers[b],tree[n],1);
return;
}
segment_tree;
init(l,b,mid);
init(r,mid+1,e);
push_up(tree[n],tree[l],tree[r]);
}

void update(int n, int b, int e, int i, int j, int val)
{
if(b>j || e<i) return;
if(b>=i && e<=j)
{
func(val,tree[n],e-b+1);
tree[n].lazy=val;
return;
}
segment_tree;
push_down(n,b,e);
update(l,b,mid,i,j,val);
update(r,mid+1,e,i,j,val);
push_up(tree[n],tree[l],tree[r]);
}

data query(int n, int b, int e, int i, int j)
{
if(b>j || e<i) return ret;
if(b>=i && e<=j)
{
return tree[n];
}
push_down(n,b,e);
segment_tree;
data p=query(l,b,mid,i,j);
data q=query(r,mid+1,e,i,j);
data xx;
push_up(xx,p,q);
return xx;
}

ll bigmod(ll n, ll pow, ll mod)
{
ll rett=1;
while(pow)
{
if(pow%2)
rett=(rett*n)%mod;
n=(n*n)%mod;
pow/=2;
}
return rett;
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
for(int i=0; i<25; i++) mp[prime[i]]=i;

int n;
sf(n);
loop1(i,n) sf(numbers[i]);

init(1,1,n);

int q;
sf(q);
while(q--)
{
int a;
sf(a);
if(a==1)
{
int l,r,x;
sfff(l,r,x);
update(1,1,n,l,r,x);
}
else
{
int l, r, p, q, m;
sff(l,r);
sff(p,q);
sf(m);

data x=query(1,1,n,l,r);
data y=query(1,1,n,p,q);
bool valid=1;
for(int i=0; i<25 && valid; i++)
{
x.ara[i]-=y.ara[i];
if(x.ara[i]<0)
valid=0;
}

if(valid==0)
{
printf("-1\n");
continue;
}

ll ans=1;

for(int i=0;i<25;i++)
{
if(x.ara[i])
{
ans*=bigmod(prime[i],x.ara[i],m);
ans%=m;
}
}

printf("%lld\n",ans);

}
}

return 0;
}

```

# Hackerrank: Lexicographically Smaller or Equal Strings

0

Solution Idea:

This problem is an example of basic merge sort tree problem. Merge Sort tree is a segment tree in which every node contains a vector. In this problem we can store string in every leaf node of segment tree as the size of the string is <=15. And while merging two leaf node we will merge them in sorted order. Now as the vectors of every node in the segment tree is sorted we can apply binary search on segment tree node to get how many string is lexicographically smaller than the given string.

So after building merge sort tree we can easily answer every query using binary search.

If you want to learn some wonderful application of segment tree or merge sort tree you can see this article.

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

vector<string>tree[3*mx],v;

void init(int n, int b, int e)
{
if(b==e)
{
tree[n].pb(v[b]);
return;
}
int l=n*2,r=l+1,mid=(b+e)/2;
init(l,b,mid);
init(r,mid+1,e);
merge(all(tree[l]),all(tree[r]),back_inserter(tree[n]));
//    cout<<n<<" "<<b<<" "<<e<<endl;
//    for(int i=0;i<SZ(tree[n]);i++)
//        cout<<tree[n][i]<<endl;
//    cout<<"-----------------------------"<<endl;
}

int query(int n, int b, int e, int i, int j, string &str)
{
if(b>j || e<i) return 0;
if(b>=i && e<=j)
{
//        int x=upper_bound(all(tree[n]),str)-tree[n].begin();
//        int y=lower_bound(all(tree[n]),str)-tree[n].begin();
//        int z=x-y;
//        return z;
return upper_bound(all(tree[n]),str)-tree[n].begin();
}
int l=n*2,r=l+1,mid=(b+e)/2;
int p=query(l,b,mid,i,j,str);
int q=query(r,mid+1,e,i,j,str);
return p+q;
}

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

int n;
sf(n);

v.pb("");
char sss[30];

for(int i=0;i<n;i++)
{
scanf(" %s",sss);
v.pb(string(sss));
}

init(1,1,n);

int q;
sf(q);
while(q--)
{
int a,b;
sff(a,b);
scanf(" %s",sss);

string str=string(sss);
//        cout<<str<<endl;
int ans=query(1,1,n,a,b,str);
printf("%d\n",ans);
}

return 0;
}

```

# Toph: Another Update-Query Problem

0

Solution Idea:

The main idea behind the solution of this problem is simplifying the equation. For a query operation we need the answer of this equation-
1A_l + (1+d)A_l+1 + (1+2d)A_l+2 + (1+3d)A_l+3 + … + (1+(r-l)d)A_r
Now let the query range l r is 1 3. and the given array is A=[a1,a2,a3,a4,…]

So our quation will be-
1*a1 + (1+d)*a2 + (1+2d)*a3 + (1+3d)*a4
= a1 + a2 + d*a2 + a3 + 2d*a3 + a4 + 3d*a4
= (a1+a2+a3+a4) + d*(a2+ 2*a3 + 3*a4)

Now We can see that first part of this equation is only sum query which can be done using a segment tree and for 2nd part we can use a trick. We can pree calculate the sequence like this-
1*a1 + 2*a2 + 3*a3 + 4*a4 + 5*a5 + 6*a6 + 7*a7 + ……
When we need the 2nd part of the equation we can use this equation. We can get the 2nd part of the equation from this equation by this way-
(2*a2 + 3*a3 + 4*a4)-(a2+a3+a4) = (a2+ 2*a3 + 3*a4).

Now the above equation is also only a sum equation. We can apply any range sum query or range sum update on this equation and the the first sum equation.

So if we store this two equation in two segment tree then we can perform range update or query on the segment tree and get any range sum query from the segment tree and using the equation we can answer each query of the problem correctly.

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
ll sum, ssum, prop;
data()
{
sum=0,ssum=0,prop=0;
}
};

data tree[3*mx];

ll ara[mx];

ll interval_sum(ll b, ll e)
{
ll x=(e*(e+1))/2;
ll y=(b*(b-1))/2;
return (x-y+MOD)%MOD;
}

void push_down(int n, int b, int e)
{
if(tree[n].prop)
{
segment_tree;
tree[l].sum+=((mid-b+1)*tree[n].prop)%MOD;
tree[r].sum+=((e-mid)*tree[n].prop)%MOD;
tree[l].ssum+=(interval_sum(b,mid)*tree[n].prop)%MOD;
tree[r].ssum+=(interval_sum(mid+1,e)*tree[n].prop)%MOD;
tree[l].prop+=tree[n].prop%MOD;
tree[r].prop+=tree[n].prop%MOD;
tree[l].sum%=MOD;
tree[l].ssum%=MOD;
tree[l].prop%=MOD;
tree[r].sum%=MOD;
tree[r].ssum%=MOD;
tree[r].prop%=MOD;
tree[n].prop=0;
}
}

void init(int n, int b, int e)
{
if(b==e)
{
tree[n].sum=ara[b]%MOD;
tree[n].ssum=((ll)b*ara[b])%MOD;
tree[n].prop=0;
return;
}
segment_tree;
init(l,b,mid);
init(r,mid+1,e);
tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
tree[n].prop=0;
}

void update(int n, int b, int e, int i, int j, ll val)
{
if(b>j || e<i) return;
if(b>=i && e<=j)
{
tree[n].sum+=((ll)(e-b+1)*val)%MOD;
tree[n].ssum+=(interval_sum(b,e)*val)%MOD;
tree[n].prop+=val;
tree[n].sum%=MOD;
tree[n].ssum%=MOD;
tree[n].prop%=MOD;
return;
}
push_down(n,b,e);
segment_tree;
update(l,b,mid,i,j,val);
update(r,mid+1,e,i,j,val);
tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
}

data query(int n, int b, int e, int i, int j)
{
if(b>j || e<i) return data();
if(b>=i && e<=j)
return tree[n];
push_down(n,b,e);
segment_tree;
data p=query(l,b,mid,i,j);
data q=query(r,mid+1,e,i,j);
data ret;
ret.ssum=(p.ssum+q.ssum)%MOD;
ret.sum=(p.sum+q.sum)%MOD;
return ret;
}

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

int t;
sf(t);
TEST_CASE(t)
{
int n,q;
sff(n,q);
loop1(i,n) sfl(ara[i]);
init(1,1,n);
LINE_PRINT_CASE;
while(q--)
{
int a,b,c,d;
sfff(a,b,c);
sf(d);
if(a==1)
{
update(1,1,n,b,c,d);
}
else
{
data ret=query(1,1,n,b,c);
ll sum=ret.sum;
ret=query(1,1,n,b+1,c);
ll ssum=(ret.ssum-(((ll)(b)*ret.sum)%MOD)+MOD)%MOD;
ssum*=(ll)d%MOD;
ssum%=MOD;
ll ans=(sum+ssum)%MOD;
printf("%lld\n",ans);
}
}

}

return 0;
}

```

# SPOJ: SEGSQRSS – Sum of Squares with Segment Tree

0

Solution Idea:

This problem is a nice example of segment tree with lazy propagation. All you need to solve this kind of problem is to do some experiment with the formula and convert them into a suitable form. From which we can drive the segment tree solution.

In this problem given an integer array A=[a1,a2,a3,a4…]. You need to perform 3 kinds of operation on it.

type 0: Set all the element in the interval l to r to x.
type 1: Increase all the element in the interval l to r by x.
type 2: Print the value of square sum of the interval l to r. For example let l=1 and r=3. then you need to print a1^2 + a2^2 + a3^2.

At first think we have a pre-calculated square sum array. Then if we perform type 1 operation which is increase it by x then what scenario will happen?

Our sum now become (a1+x)^2 + (a2+x)^2 + (a3+x)^2. Let expand this equation-

(a1+x)^2 + (a2+x)^2 + (a3+x)^2
= a1^2+ 2*a1*x + x^2 + a2^2+ 2*a2*x + x^2 + a3^2+ 2*a3*x + x^2
= (a1^2 + a2^2 + a3^2) + 3*x^2 + 2*x*(a1 + a2 + a3)

for a range l to r the generalized equation is –

(a_l^2 + a_l+1^2 +….+ a_r^2) + (r-l+1)*x^2 + 2*x*(a_l + a_l+1 +….+ a_r)

We can store the information about sum, square_sum, type_0 lazy and type_1 lazy of an interval in each segment tree node. And perform type 1 operation then we can calculate then sum value for a node over a range by multiplication and square sum value by above equation.

For every type 0 operation we can simply put the value of sum and square sum by using some basic calculation and arithmetic multiplication operation.

And for every type 2 operation we just need to get the sum of square sum value over a range l to r.

So we can perform each of 3 operation using a segment tree with lazy propagation.

```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
ll sum,sqrsum,lazy,upd;
};

data tree[3*mx];

ll ara[mx];

void push_down(int n, int b, int e)
{
segment_tree;
if(tree[n].upd)
{
tree[l].lazy=0;
tree[r].lazy=0;
tree[l].sum=(mid-b+1)*tree[n].upd;
tree[l].sqrsum=(mid-b+1)*sqr(tree[n].upd);
tree[r].sum=(e-mid)*tree[n].upd;
tree[r].sqrsum=(e-mid)*sqr(tree[n].upd);
tree[l].upd=tree[n].upd;
tree[r].upd=tree[n].upd;
tree[n].upd=0;
}
if(tree[n].lazy)
{
//        tree[l].lazy+=tree[n].lazy;
//        tree[l].status=1;
//        tree[r].lazy+=tree[n].lazy;
//        tree[r].status=1;
//        tree[n].status=0;
tree[l].sqrsum+=(tree[l].sum*(2*tree[n].lazy))+(mid-b+1)*sqr(tree[n].lazy);
tree[r].sqrsum+=(tree[r].sum*(2*tree[n].lazy))+(e-mid)*sqr(tree[n].lazy);
tree[l].sum+=(mid-b+1)*tree[n].lazy;
tree[r].sum+=(e-mid)*tree[n].lazy;
tree[l].lazy+=tree[n].lazy;
tree[r].lazy+=tree[n].lazy;
tree[n].lazy=0;
}
}

void init(int n, int b, int e)
{
if(b==e)
{
tree[n].sum=ara[b];
tree[n].sqrsum=sqr(ara[b]);
tree[n].lazy=0;
tree[n].upd=0;
return;
}
segment_tree;
init(l,b,mid);
init(r,mid+1,e);
tree[n].sum=tree[l].sum+tree[r].sum;
tree[n].sqrsum=tree[l].sqrsum+tree[r].sqrsum;
tree[n].lazy=0;
tree[n].upd=0;
}

void update(int n, int b, int e, int i, int j, ll val, int type)
{
if(b>j || e<i) return;
if(b>=i && e<=j)
{
if(type==0)
{
tree[n].sum=(e-b+1)*val;
tree[n].sqrsum=(e-b+1)*sqr(val);
tree[n].lazy=0;
tree[n].upd=val;
}
else
{
tree[n].sqrsum+=(tree[n].sum*2*val)+((e-b+1)*sqr(val));
tree[n].sum+=(e-b+1)*val;
tree[n].lazy+=val;
}
return;
}

push_down(n,b,e);

segment_tree;

update(l,b,mid,i,j,val,type);
update(r,mid+1,e,i,j,val,type);
tree[n].sum=tree[l].sum+tree[r].sum;
tree[n].sqrsum=tree[l].sqrsum+tree[r].sqrsum;
}

ll query(int n, int b, int e, int i, int j)
{
if(b>j || e<i) return 0;
if(b>=i && e<=j)
return tree[n].sqrsum;
push_down(n,b,e);
segment_tree;
ll p=query(l,b,mid,i,j);
ll q=query(r,mid+1,e,i,j);
return p+q;
}

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

int t;
sf(t);
TEST_CASE(t)
{
int n,q;
sff(n,q);
loop1(i,n) sfl(ara[i]);
init(1,1,n);
LINE_PRINT_CASE;
while(q--)
{
int a,b,c,d;
sfff(a,b,c);
if(a==2)
{
ll ans=query(1,1,n,b,c);
printf("%lld\n",ans);
}
else
{
sf(d);
if(a==1)
update(1,1,n,b,c,d,1);
else
update(1,1,n,b,c,d,0);
}
}
}

return 0;
}

```