Hello @waqar_ahmad224 Array Manipulation | HackerRank this question can be done with the help of segment trees right? If yes, then guide me a lil bit how to maintain maximum as there are many range queries and one more doubt is can we create an array of size 4*(10**7) ?
Waiting for your reply 
Hi, Thanks for these amazing lectures.!
I was trying to solve the question “Multiple of 3” using lazy propagation…but I’m getting TLE using python(i know cpp is fast…).but have a look at my code and correct me if i am doing something wrong.
Code : https://ideone.com/w7pck3
i’ll try to code it in cpp…
Thanks again.!
Please add GSS1 from spoj
I think you should make a separate article asking help because I don’t code in python so it would be hard for me to tell you which part is consuming time.
I thought this was an easy problem , are you sure you want an editorial for this?
if anyone else wants this too please let me know , the more the merrier.
yes …i am unable to solve it
Hi codeNcode, I watched the number theory playlist videos, one of the hackerearth problems, I followed the video but I get WA in 3 testcases https://www.hackerearth.com/pt-br/submission/46336891/ what’s wrong?
#include<bits/stdc++.h>
using namespace std;
const int MX=1e5;
const int INF=INT_MAX;
vector a(MX+1);
vector seg(4*MX+1);
struct SGT{
void build(int si ,int ss ,int se){
if(ss == se){
seg[si] = a[ss];
return;
}
int mid = (ss + se) / 2;
build(2*si ,ss ,mid);
build(2*si+1 ,mid+1, se);
seg[si] = min(seg[2*si] , seg[2*si+1]);
}
void build(vector<int> &a,int n){
return build(1,1,n);
}
int query(int si, int ss, int se, int qs, int qe){
//completely outside
if(qs > se || qe < ss){
return INF;
}
//completely inside
if(ss >= qs && se <= qe){
return seg[si];
}
int mid = (ss + se) / 2;
int l = query(2*si, ss, mid, qs, qe);
int r = query(2*si+1, mid+1, se, qs, qe);
return min(l,r);
}
int query(int l,int r,int n){
return query(1,1,n,l,r);
}
};
int main(){
SGT sgt;
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
sgt.build(a,n);
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
cout<<sgt.query(l+1,r+1,n)<<"\n";
}
return 0;
}
i was trying to solve the RMQSQ problem from SPOJ using this solution but it is isn’t working and i am unable to find my mistake
for input
3
1 4 1
2
1 1
1 2
output is 4,1
but my output is 1,0
the only problem you are having is in input.
you are reading the input using 0-based index system (i is running from 0 to n-1 while reading input) and all other operations (query , build etc.) are using 1-based index system.
just read the input from 1 to n and everything else is absolutely correct
2 Likes
I am trying to solve Multiple of 3 question
I am using 0 based indexing here. But I am getting TLE .
Can anyone help me in figuring out the issue with it.
[MY Code]
(CodeChef: Practical coding for everyone)
#include <bits/stdc++.h>
using namespace std;
int seg[400004][3] ; int lazy[400004];
void bulilSegtree(int index , int low , int high)
{
if (low == high)
{
seg[index][0] = 1;
seg[index][1] = 0;
seg[index][2] = 0;
return;
}
int mid = (low + high) / 2;
bulilSegtree(2 * index + 1, low , mid);
bulilSegtree(2 * index + 2, mid + 1, high);
seg[index][0] = (seg[2 * index + 1][0] + seg[2 * index + 2][0]);
seg[index][1] = (seg[2 * index + 1][1] + seg[2 * index + 2][1]);
seg[index][2] = (seg[2 * index + 1][2] + seg[2 * index + 2][2]);
}
void shift(int index)
{
int temp = seg[index][2];
seg[index][2] = seg[index][1];
seg[index][1] = seg[index][0];
seg[index][0] = temp;
}
int query(int index , int low , int high , int &l , int &r)
{
if (lazy[index] != 0)
{
int dx = lazy[index];
lazy[index] = 0;
if (low != high)
lazy[2 * index + 1] += dx , lazy[2 * index + 2] += dx;
int totalCycle = dx%3;
for(int i=0;i<totalCycle;i++)
shift(index);
}
if (l > high || r < low)
return 0;
if (low >= l && high <= r)
return seg[index][0];
int mid = (low + high) / 2;
int left = query(index * 2 + 1, low, mid, l, r);
int right = query(index * 2 + 2, mid + 1, high, l, r);
return (left + right);
}
void rangeUpdate(int index , int low , int high , int &l , int &r)
{
if (lazy[index] != 0)
{
int dx = lazy[index];
lazy[index] = 0;
if (low != high)
lazy[2 * index + 1] += dx , lazy[2 * index + 2] += dx;
int totalCycle = dx%3;
for(int i=0;i<totalCycle;i++)
shift(index);
}
if (l > high || r < low)
return ;
if (low >= l && high <= r)
{
shift(index);
if (low != high)
lazy[2 * index + 1] += 1 , lazy[2 * index + 2] += 1;
return;
}
int mid = (low + high) / 2;
rangeUpdate(2 * index + 1, low , mid , l , r);
rangeUpdate(2 * index + 2 , mid + 1 , high , l , r);
seg[index][0] = seg[2 * index + 1][0] + seg[2 * index + 2][0];
seg[index][1] = seg[2 * index + 1][1] + seg[2 * index + 2][1];
seg[index][2] = seg[2 * index + 1][2] + seg[2 * index + 2][2];
}
void solveTestCases()
{
int n;
cin>>n;
int q;
cin>>q;
bulilSegtree(0 , 0 , n-1);
while (q--)
{
int type;
cin>>type;
int a , b;
cin>>a>>b;
if(type == 0)
{
rangeUpdate(0,0,n-1,a,b);
}else if(type ==1 )
{
cout<<query(0,0,n-1,a,b)<<endl;
}
}
return;
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
solveTestCases ();
return 0;
}
brother can you please explain why my python solution is giving TLE in the question “multiples of 3” which you have covered in your youtube channel by applying the same approach you have taught, and with the same approach in C++ it’s giving AC.
CodeChef: Practical coding for everyone please some one help how to solve this using merge sort tree…
You are given an array A of N integers and Q queries. Queries are of two types:
- l r v -> decrement the values of A between index l and r (both inclusive)
by v. - v -> print the index of the leftmost element whose value is less than v. If
no such element exists then print -1.
Input :
First line contains two integers -> value of N and Q;
Second line contains N space separated integers -> A[0] A[1] ------ A[N - 1]
Each of the next Q lines contain queries.
Query is of type - t l r v
- t v
Here t is the type of query (1 or 2).
Output
Print answer for every query of type 2.
Limits :
1 <= N, Q <= 100,000
-1000,000,000 <= A[i] <= 1,000,000,000
-1000,000,000 <= v <= 1,000,000,000
0 <= l <= r < N
1 <= t <= 2
Can anyone help me in this question.
I got AC for K-Query in Spoj, where same code is giving TLE on Codeforces.
Submission link on Codeforces:
Codeforces
Code:
#include <bits/stdc++.h>
#include <ext/rope>
#define pb push_back
#define ll long long
#define endl “\n”
#define MX 30005
#define W(t) while(t–)
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define rep(i,a,b) for(ll i = a; i <= b; i++)
using namespace std;
using namespace __gnu_cxx;
int a[MX], n, q, k;
vector segTree[4*MX];
void build(int node, int b, int e)
{
if (b == e) {
segTree[node].pb(a[b]);
return;
}
int mid = (b + e) / 2;
int left = node << 1;
int right = (node << 1) + 1;
build(left, b, mid);
build(right, mid + 1, e);
int i = 0, j = 0;
while (i < segTree[left].size() && j < segTree[right].size()) {
if (segTree[left][i] <= segTree[right][j])
segTree[node].pb(segTree[left][i]), i++;
else
segTree[node].pb(segTree[right][j]), j++;
}
while (i < segTree[left].size())
segTree[node].pb(segTree[left][i]), i++;
while (j < segTree[right].size())
segTree[node].pb(segTree[right][j]), j++;
}
int Query(int node, int b, int e, int l, int r, int k)
{
if (b > r || e < l) return 0;
if (b >= l && e <= r) {
int indx = upper_bound(all(segTree[node]), k) - segTree[node].begin();
if (indx == segTree[node].size()) return 0;
else return (segTree[node].size() - indx);
}
int mid = (b + e) / 2;
int left = node << 1;
int right = (node << 1) + 1;
int r1 = Query(left, b, mid, l, r, k);
int r2 = Query(right, mid + 1, e, l, r, k);
return r1 + r2;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
rep(i, 1, n) cin >> a[i];
build(1, 1, n);
cin >> q;
W(q)
{
int l, r, k; cin >> l >> r >> k;
cout << Query(1, 1, n, l, r, k) << endl;
}
return 0;
}
Any kind of help would be obliged. Thank you. 
Hi @waqar_ahmad224,
Thank you very much for your sequence of videos related to segment trees. These are very well explained! I just understood lazy propagation for segment trees for the first time :). May I ask if you have the code in Python for the lazy propagation?
Thanks again for these great videos.
#(Number of odd, Number of even)
def build(a, v, sl, sr):
if sl == sr:
if a[sl] % 2 == 1:
st[v] = [1, 0]
else:
st[v] = [0, 1]
return
else:
m = (sl+sr) // 2
build(a, 2*v, sl, m)
build(a, 2*v + 1, m+1, sr)
st[v][0] = st[v*2][0] + st[v*2 + 1][0]
st[v][1] = st[v*2][1] + st[v*2 + 1][1]
def update(a, v, sl, sr, qi, nval):
if sl == sr:
a[sl] = nval
if a[sl] % 2 == 1:
st[v] = [1, 0]
else:
st[v] = [0, 1]
#a[sl] = nval
return
m = (sl+sr) // 2
if qi <= m:
update(a, v*2, sl, m, qi, nval)
else:
update(a, v*2+1, m+1, sr, qi, nval)
st[v][0] = st[v*2][0] + st[v*2 + 1][0]
st[v][1] = st[v*2][1] + st[v*2 + 1][1]
def getodd(v, sl, sr, l, r):
if sl > r or sr < l: return 0
if sl >= l and sr <= r: return st[v][0]
m = (sl + sr) // 2
return getodd(2*v, sl, m, l, r) + getodd(2*v+1, m+1, sr, l, r)
def geteven(v, sl, sr, l, r):
if sl > r or sr < l: return 0
if sl >= l and sr <= r: return st[v][1]
m = (sl + sr) // 2
return geteven(2*v, sl, m, l, r) + geteven(2*v+1, m+1, sr, l, r)
a = [1, 2, 3, 4, 5, 6]
st = [[None, None]]*len(a)*4
build(a, 0, 0, len(a)-1)
Here is my python code for finding number of even and odd numbers within a range. Everything is working find except the update function. It is returning wrong results. Could anyone please help me with that?
This is Solution of Problem Help Ashu Hackerearth
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1000000000
pair<ll,ll> seg[400004];
ll a[100001];
void build(ll s, ll e , ll tidx)
{
if(s==e)
{
if(a[s]%2==0)
{
seg[tidx].first=1;
seg[tidx].second=0;
}
else
{
seg[tidx].first=0;
seg[tidx].second=1;
}
return;
}
ll mid = (s+e)/2;
build(s,mid,2tidx);
build(mid+1,e,2tidx +1);
seg[tidx].first = seg[2tidx].first+seg[2tidx + 1].first;
seg[tidx].second = seg[2tidx].second+seg[2tidx + 1].second;
}
void update(ll s, ll e , ll tidx , ll id ,ll val)
{
if(s==e)
{
a[s]=val;
if(a[s]%2==0)
{
seg[tidx].first=1;
seg[tidx].second=0;
}
else
{
seg[tidx].first=0;
seg[tidx].second=1;
}
return;
}
ll mid=(s+e)/2;
if(mid>id)
{
update(mid+1,e,2tidx+1,id,val);
}
else
{
update(s,mid,2tidx,id,val);
}
seg[tidx].first = seg[2tidx].first+seg[2tidx + 1].first;
seg[tidx].second = seg[2tidx].second+seg[2tidx + 1].second;
}
ll queryeven(ll s, ll e , ll tidx , ll left ,ll right)
{
if(s>right||e<left)
{
return 0;
}
if(s>=left&&e<=right)
{
return seg[tidx].first;
}
ll mid=(s+e)/2;
ll a1=queryeven(s,mid,2tidx,left,right);
ll a2=queryeven(mid+1,e,2tidx +1,left,right);
return a1+a2;
}
ll queryodd(ll s, ll e , ll tidx , ll left ,ll right)
{
if(s>right||e<left)
{
return 0;
}
if(s>=left&&e<=right)
{
return seg[tidx].second;
}
ll mid=(s+e)/2;
ll a1=queryodd(s,mid,2tidx,left,right);
ll a2=queryodd(mid+1,e,2tidx +1,left,right);
return a1+a2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
ll q;
cin>>q;
while(q–)
{
ll l,r,type;
cin>>type>>l>>r;
if(type==0)
{
if((a[l] % 2) == (r % 2)) continue;
update(1,n,1,l,r);
}
if(type==1)
{
cout<<queryeven(1,n,1,l,r)<<endl;
}
if(type==2)
{
cout<<queryodd(1,n,1,l,r)<<endl;
}
}
}
Please tell why I am getting wrong answer