There are $$$N$$$ persons. Each one of them has a friendship with zero or more of others. If $$$A$$$ is friend with $$$B$$$, then $$$B$$$ is also friend with $$$A$$$. Now they will have to form some teams, each containing two persons. Each member of a team must have a friendship with the other member of the team. The question is, what is the maximum number of teams that can be made?

For example,
$$$A$$$ is friend with $$$B$$$ and $$$D$$$.
$$$B$$$ is friend with $$$A$$$ and $$$C$$$.
$$$C$$$ is friend with $$$B$$$.
$$$D$$$ is friend with $$$A$$$.

Then, maximum two teams can be made: $$$(A,D)$$$ and $$$(B,C)$$$.

How to solve this if,

• the upper bound of $$$N$$$ is $$$100$$$?
• the upper bound of $$$N$$$ is $$$1000$$$?
• the number of team members is any number in the range $$$[2,N]$$$?

I have a grid containing $$$10^6$$$ rows and $$$10^6$$$ columns. I also have coordinates of $$$N$$$ cells of this grid each of which has either a red ball, or a blue ball, or both (one ball of each color). When a person visits a cell, he/she can collect all the balls from that cell. The target is to reach the bottom-right cell from the top-left cell by collecting at least one ball of each color. From one cell, it's only possible to visit the cell on its right or the cell below it. Upper bound of $$$N$$$ is $$$1000$$$.

The problem is to find the number of different paths that has at least one cell with blue ball and at least one cell with red ball in it. Two paths are different if there is at least one cell that belongs to only one of them.

How can I solve this efficiently?

I need some problems that involve Range Minimum/Maximum Query with single element update.

Since I need such problems for some testing and research purposes, it would be good if they are straight forward and don't require anything else other than RMQ (with update queries of course) to solve them. Update queries should be like changing single element. I have already searched on the internet and found many RMQ problems, but none of them involves update queries.

Please provide some links to such problems you know.