GM3379 【NOI2013 simulation 】 Inquire about

The question ：$m$ Queries , The union of multiple interval resettable is queried every time （ No weight removal ） No $p$ Small , The number of intervals in each query $k$ No more than $5$ individual ,$n,m\le 2\times 10^5$ .

Ideas ： Think of one in two $mid$ bring $\le mid$ Number $\ge p$ Then the chairman tree handles , But the time complexity is too high , yes $O(mk\log w\log n)$ , Cannot pass .

therefore , Look directly for No. on the chairman tree $p$ Small .

Isn't this the way we used to write the chairman tree ： Calculate the right root $size$ value , Subtract the left root , Then judge where you should be .

The same is true this time , Calculation all Right root Of $size$ , subtract all Left rooted $size$ value , Just fine .

prove ： Why is this right ？

Because it moves left and right at the same time , It's the same $l,r$ The pointer , Judgmental $mid$ It's the same , therefore All move towards a common goal .

as for In every specific tree Will there be an answer to the question , There is no such thing here , because The flow of the algorithm stipulates that it will not be affected by individuals to change the overall situation , Put overall interests first .

therefore , That's right .