Can anyone help me out in finding how the time complexity of erase in multiset is amortized constant when we erase by passing iterator to element we want to erase. Like I am getting the point that we are directly providing iterator to the element but I am thinking that after deleting that element, we have to maintain the red black tree (multiset is internally implemented as red black tree) which will have time complexity greater O(1). Then how comes the time complexity to be amortized constant. Thanks in advance.

An array is given (indexing starts with 1) of size S and N number of queries is given by user Ni=(M P R); 1<=i<=N. Print the Rth minimum element from the array after updating Mth index. Example :- Array : [2, 4, 6, 1, 7] S=5

Queries : N=3

2 5 3

5 3 2

4 8 4

Output :- 5

2

6

How to solve this question.

There are n commodities numbered from 1 to n . The commodities are traded at multiple exchanges where each exchange only allows a particular pair of commodities to be exchanged. There are total n-1 exchanges. The commodities and the exchanges form a tree structure.

ith exchange charges ti units as a transaction charge for its services, e.g. say a particular exchange allows trade between commodity a and b, and you are exchanging 10 units from a to b or vice versa and if it charges 2 units, then you can get 8 units of b corresponding to 10 units of a and vice versa. The trader performing the transaction earns pi profit as a result of transaction.

A trader wants to maximize the profit and is allowed to start with m units of any commodity of his/her choice.

Can you find the maximum profit the trader can earn if he/she can trade with any exchange at most once?

Input Format : The first line contains two integers n and m. Then n-1 lines follow. Each line describes an exchange allowing trade between two commodities It contains four integers, ui, vi, ti and pi. ui and vi are the numbers of two commodities traded at this exchange, ti is the transaction charge, and pi is the profit trader makes by trading at this exchange.

Output Format

An integer which is the maximum profit.

Sample Input :

5 4 1 2 1 2 1 3 2 3 1 4 2 4 4 5 2 2

Sample Output : 7

Explanation : You start with 4 units of commodity numbered 3 and exchange it with 1 at the expense of 2 units and earning 3 profit. Then, you exchange 1 with 4 at the expense of remaining 2 units and earning 3 profit. So, total profit earned is 7.

You have N candies distributed unevenly in N containers. You can move one candy from a container to an adjacent container. You have to make moves such that finally each container has one candy. What is the strategy that minimizes the number of moves to keep the time complexity O(N)?