Original link: https://www.shuizilong.com/house/archives/luogu-p8500-noi2022-%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/
Intersections of intervals are of course troublesome. . A few days ago when I was in CF #875 C, I was able to use the hash method to get away with it. . It will definitely not work this time. .
Let’s deal with this situation at the end first, and write a 28-point code first.
Lemma 1. We only need to utilize the value present in the condition.
This property can guide us to discretize, so as to facilitate the use of various data structures.
Lemma 2. For the case of property B, the undetermined number increases monotonically.
It can be obtained by simple adjustment. In this case, we can not count the reverse order pairs between undetermined numbers and undetermined numbers, because it must be 0, but this property is not universal. We might as well fill in all the numbers first, and finally run together The code to find the reverse order pair once can reduce the discussion.
Lemma 3. When scanning from left to right, for the number that can be filled, try to fill in a smaller value under optimal conditions.
This is an extension of the above properties, obviously more useful to us.
So to sum up, we only need to open a line segment tree, record the cost of filling each number at present, and then every time the interval is modified, the minimum value of the interval can be calculated.
Finally, just consider interval crossing.
Our ultimate goal is to process two arrays, A[] represents all the numbers that have been filled, and B[] represents the lower bound of the unfilled numbers.
Then scan it with the line segment tree to get the complete A[].
Look at the property A again. In the case of 1, all can only be filled with 1, and directly filled in A[]. For the case of 0, we hope to continue to use Lemma 3, scan the interval from right to left, and fill in the number as late as possible .
Finally, to remove property A, you only need to go from large to small according to the weight, and use the union search to dig out each processed position.
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p8500-noi2022-%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/
This site is only for collection, and the copyright belongs to the original author.