How to do this question?

rock2000 · September 25, 2019, 4:36am

Please guide me on how to this question using segment trees.

Robin_rst · September 25, 2019, 11:29am

Segment tree with node as a vector. Instead of a single element at every node, you need to have a vector which contains elements of that interval in sorted order or you can also use policy base data structure for the same. All you have to do is just binary search on that vector containing that interval and return the vector size - first index where you find the element or element greater than element given in query.

rock2000 · September 25, 2019, 1:43pm

Sir I am getting TLE with this approach

rock2000 · September 25, 2019, 1:48pm

my solution: https://ide.codingblocks.com/s/135727

Robin_rst · September 25, 2019, 3:50pm

STL has inbuilt merge function for merging.
See this implementation and you will get it.

github.com

robinrst/HackerBlocks/blob/master/MaxQuery1.cpp

#include "bits/stdc++.h"

using namespace std;

#define  f first
#define  lgn 25
#define  endl '\n'
#define  sc second
#define  N (int)2e5+5
#define  sz(x) x.size()
#define  int long long int
#define  ld long double
#define  vi vector<int>
#define  vs vector<string>
#define  vc vector<char>
#define  mii map<int,int>
#define  pii pair<int,int>
#define  vpii vector<pii>
#define  test(x) while(x--)
#define  pb push_back

This file has been truncated. show original