ok thanks i will look into it.

How to handle update in range[i+1 ,mx] using lazy?

You have to use set which are in policy based data structures because normal set don't tell you the index of the integer so out can't find the no of elements less than x just using binary search ie. upper_bound

For Policy based data structures: https://mirror.codeforces.com/blog/entry/11080

you will have to erase an element and insert an element for erasing a single element in multiset first you find that element which will return an iterator to that element then you erase that element and then you insert the element which you want to

you can also handle updates if you store a set or multiset(which are in policy-based data structures) in each node instead of storing a vector

You can read about many applications from this site :

http://e-maxx.ru/algo/segment_tree

in segment tree you have to keep a vector as a node element and each node of segment tree will have the sorted range of left and right sub tree. then you will have to query in L to R for that when you reach a segment that completely lies in the range you have to do a binary search for number of element less than x in that segment and like this you have to add the answers coming from all segments

you can have a look to this link : https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorial

You can solve each query in (logN)^2 using merge sort tree.

You can do the query two times in 1st query you will get previous min and in 2nd you will get 2nd previous min i have done only one time to show the sample.

There exists a solution using a min segment tree in O(NlogN) complexity.

Suppose you have 1st previous smaller stored and for index i , index j has value 1st previous smaller than A[i].

Now your answer for 2nd previous smaller than element A[i] is the 1st previous smaller than A[i] in range 1 to j-1.

You can find the largest index i in range L to R such that A[i] < X for any X by using segment tree in logN complexity.

Now you have a min segment tree , In query you can find if segment range lies totaly in range L to R and if it lies then you will check weather minimum of the segment is less than X or not if it is less than X then if this minimum coming from right you go to right otherwise left.

You can query for each element of array A and for each element complexity is logN so total complexity will be NlogN.

The code for segment tree is given below and in result array I am storing the largest index i such that A[i] < X that's why I am querying in range 1 to i-1 but you also perform the query in range from 1 to 1st previous smaller than A[i].

int n;
int tree[400020];
int A[100005];
int result[100005];

void build(int s, int e , int node)
{
	int mid = (s+e)/2;
	if(s==e)
	{
		tree[node] = A[s];
		return ;
	}
	build(s,mid,2*node);
	build(mid+1,e,2*node+1);
	tree[node] = min(tree[2*node],tree[2*node+1]);
}

int query(int  l ,int r ,int s ,int e, int node ,int x)
{
	if(r<s || e<l)
	{
		return -1;
	}
	if(l<=s && e<=r)
	{
		if(tree[node]>=x)
			return -1;
		else
		{
			if(s == e)
			{
				if(tree[node]<x)
					return tree[node];
			}

			int mid = (s+e)/2;

			if(tree[2*node+1]<x)
			{
				return query(l , r , mid + 1 , e , 2*node + 1 ,x);
			}
			else
			{
				return query(l ,r , s , mid  , 2*node , x );
			}
		}
	}
	int mid = (s+e)/2;
	int ans = query(l , r , mid+1 , e , 2*node+1 , x);
	if(ans == -1)
	{
	ans = query(l , r , s , mid , 2*node , x);
	}
	return ans;

} 

int main()
{

	cin>>n;

	for(int  i = 1 ; i<=n ;i++)
		cin>>A[i];
	
	build(1,n,1);

	for(int i = 1 ; i<=n ;i++)
	{
		result[i] = query(1 , i-1 , 1 , n , 1 , A[i]);

	}

	for(int i = 1 ;i<=n ;i++)
		cout<<result[i]<<" ";
	
	return 0;
	
}