PROBLEM LINK:
Author: Bhavik Jain
Tester: Dhrub Kumar
Editorialist: Bhavik Jain
DIFFICULTY:
HARD
PREREQUISITES:
Segment Tree, Priority Queue
PROBLEM:
There are n planets in a sequence from 1, 2,…,n and each planet has a certain number of trees with some heights (heights may be same or different).
There are q queries and each query maybe of the following two types :
- Type 1 : 1 l r : First integer specifies that the query is of type 1. Next two integers l and r specify a range of planets from l and r inclusive. You have to remove a single tree having the highest height among all the trees present in planets from range l and r. You have to output the height of that tree.
- Type 2 : 1 p h : First integer specifies that the query is of type 2. Next two integers p and h specify the planet number and height of a new tree respectively. You have to add the tree to the specified planet p.
NOTE :
- If not a single tree exists for a particular range of planets given in any query of type 1, then output 0 for that particular query.
- There may exist multiple trees with same height on a planet.
- Given a range of planets in any query of type 1, if there are multiple trees with same maximum height then remove the tree present on the lower numbered planet. For example : If there are two planets, planet 1 having 1 tree of height 6 and planet 2 also having 1 tree with height 6 and a query is given with l = 1 and r = 2 then remove the tree with height 6 on planet 1.
EXPLANATION:
The solution is a combination of segment tree and priority queue.
Create an array of n max priority queues representing each planet and store the heights of trees on a planet in its respective priority queue.
Pop the first element from each priority queue and store it in an array.
This array will be used to construct a max segment tree, where each node of the array consists of a pair ( height, num ) where height is the maximum height of the tree of planet num.
Now we have the required data structures ready for processing the queries :
- Type 1 : rangeQuery the segment tree with range l and r to obtain the tree with maximum height. Print the height and then using num, pop the priority queue of planet num and update the segment tree with the height obtained after popping the priority queue. If the priority queue is empty, then update the segment tree with zero.
- Type 2 : rangeQuery the segment tree with range p and p to obtain the tree with maximum height on planet p. If the queried height (x) is lower then h then add x back to the priority queue of planet p and update x with h in the segment tree. Else, just add h to the priority queue of planet p.
This forms the solution to the problem.
SOLUTIONS:
Setter's Solution (Python)
import heapq
class MaxSegmentTree:
def buildSegTree(self,arr,seg,idx,low,high):
if low==high:
seg[idx]=[arr[low],low]
return
mid=(low+high)//2
self.buildSegTree(arr,seg,2*idx+1,low,mid)
self.buildSegTree(arr,seg,2*idx+2,mid+1,high)
if max(seg[2*idx+1][0],seg[2*idx+2][0])==seg[2*idx+1][0]:
seg[idx]=[seg[2*idx+1][0],seg[2*idx+1][1]]
else:
seg[idx]=[seg[2*idx+2][0],seg[2*idx+2][1]]
def rangeQuery(self,seg,l,r,low,high,idx):
if r<low or l>high:
return -float('inf'),0
if low>=l and high<=r:
return seg[idx][0],seg[idx][1]
mid=(low+high)//2
left = self.rangeQuery(seg,l,r,low,mid,2*idx+1)
right = self.rangeQuery(seg,l,r,mid+1,high,2*idx+2)
if max(left[0],right[0])==left[0]:
return left[0],left[1]
return right[0],right[1]
def updateQuery(self,seg,low,high,idx,i,val):
if low==high:
seg[idx][0]=val
return
mid=(low+high)//2
if i<=mid:
self.updateQuery(seg,low,mid,2*idx+1,i,val)
else:
self.updateQuery(seg,mid+1,high,2*idx+2,i,val)
if max(seg[2*idx+1][0],seg[2*idx+2][0])==seg[2*idx+1][0]:
seg[idx]=[seg[2*idx+1][0],seg[2*idx+1][1]]
else:
seg[idx]=[seg[2*idx+2][0],seg[2*idx+2][1]]
n,q=map(int,input().split())
data=[0]*n
maxi=[0]*n
for i in range(n):
a=list(map(int,input().split()))
data[i]=[0]*a[0]
for j in range(1,a[0]+1):
data[i][j-1]=-a[j]
heapq.heapify(data[i])
maxi[i]=-1*heapq.heappop(data[i])
seg=[0]*(4*n)
tree = MaxSegmentTree()
tree.buildSegTree(maxi,seg,0,0,n-1)
ans=[0]*q
for i in range(q):
x=list(map(int,input().split()))
if x[0]==1:
l,r=x[1],x[2]
val,idx=tree.rangeQuery(seg,l-1,r-1,0,n-1,0)
ans[i]=val
if len(data[idx])>0:
temp=-1*heapq.heappop(data[idx])
tree.updateQuery(seg,0,n-1,0,idx,temp)
else:
tree.updateQuery(seg,0,n-1,0,idx,0)
else:
planet,new=x[1],x[2]
val,idx=tree.rangeQuery(seg,planet-1,planet-1,0,n-1,0)
if new>val:
tree.updateQuery(seg,0,n-1,0,idx,new)
heapq.heappush(data[idx],-1*val)
else:
heapq.heappush(data[idx],-1*new)
ans[i]=-1
for i in ans:
if i!=-1:
print(i,end=" ")
print()
Tester's Solution (C++)
#include<bits/stdc++.h>
using namespace std;
typedef int lli;
typedef long double ld;
#define plli pair<lli,lli>
#define pb push_back
#define fir first
#define sec second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
constexpr lli mod=(1000*1000*1ll*1000)+7;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
constexpr lli N=100100;
vector<priority_queue<lli> > s(N);
template<class T>
class segment
{
private :
T zero;
vector<T> st;
lli n;
public :
segment(){}
segment(lli _n)
{
n=_n;
zero={0,n+1};
//zero={-mod,-mod,-mod,-mod};
// zero is element to be returned on out of query
st.resize(_n<<2,zero);
}
T comb(T x,T y){
if(x[0]>y[0] or (x[0]==y[0] and x[1]<y[1]))
return x;
return y;
}
void upds(lli ss,lli se,lli v,lli q,T val)
{
if(ss==se)
{
st[v]=val;
return ;
}
else
{
lli mid = (ss + se) / 2;
if(q<=mid)
upds(ss,mid,v*2,q,val);
else
upds(mid+1,se,v*2+1,q,val);
st[v] = comb(st[v*2],st[v*2+1]);
}
}
T querys(lli ss,lli se,lli v,lli qs,lli qe)
{
if((ss>qe)||(se<qs))
return zero;
if((qs<=ss)&&(qe>=se))
return st[v];
lli mid=(ss+se)/2;
T l,r;
l=querys(ss,mid,v*2,qs,qe);
r=querys(mid+1,se,v*2+1,qs,qe);
return comb(l,r);
}
void upds(lli pos,T val)
{
upds(0,n-1,1,pos,val);
}
T querys(lli l,lli r)
{
return querys(0,n-1,1,l,r);
}
};
int main(){
fastio
lli T,i=0,j;
T=1;
while(T--){
lli n,q;
cin>>n>>q;
// assert(n>=1 and n<=100000 and q>=1 and q<=100000);
lli summ=0;
segment<array<lli,2>> seg(n+1);
for(i=1;i<=n;i++){
lli m;
cin>>m;
for(j=0;j<m;j++){
lli x;
cin>>x;
s[i].push(x);
}
summ+=m;
lli ele=0;
if(!s[i].empty())
ele=s[i].top();
seg.upds(i,array<lli,2>{ele,i});
}
// assert(summ<=100000);
while(q--){
lli x,y,z;
cin>>x>>y>>z;
if(x==1){
// assert(y<=z and y<=100000 and z<=100000);
array<lli,2> p=seg.querys(y,z);
cout<<p[0]<<" ";
if(!s[p[1]].empty())
s[p[1]].pop();
lli ele=0;
if(!s[p[1]].empty())
ele=s[p[1]].top();
seg.upds(p[1],array<lli,2>{ele,p[1]});
}
else{
// assert(y<=100000 and z<=mod-7);
s[y].push(z);
lli ele=0;
if(!s[y].empty())
ele=s[y].top();
seg.upds(y,array<lli,2>{ele,y});
}
}
}
return 0;
}