2022/7/24 examination summary

Time arrangement

7:30~8:00

I saw T1, In reverse topological order dp, It's natural to think of root division , The code is easy to write , The constant is less than , I finished writing a large sample soon . Then I didn't see it

8:00 ~8:30

Yes T2 The search .

8:30~9:00

Yes T3 The search

9:00~9:30

Yes T3 Two points in second gear + Line segment tree , But after a tangle, I feel like I can run, but it doesn't matter .

9:30~10:10

T3 The third gear can lct Or segment tree divide and conquer , I feel that the segment tree divide and conquer has many details and poor complexity , So I wrote lct, Fortunately, I've done it again .

10:10~12:30

Think of the T3 Of $(n+q)\sqrt{q}$ How to do it , Operation block , Then build a virtual tree , because n,q Very small , So maybe I can pass , So I began to write .
There are many details , For a long time .

A summary after the exam

T1

Thanks to reading relevant blogs and topics before ： Graph theory is divided into blocks
HDU 6756 Finding a MEX
But at ordinary times, I also brush a lot of root division problems , It should not be too difficult to think of such an approach .

T2

A wonderful question ！
First of all 60 Separate ideas .
First, after factorization, it is related to two parameters , Then it is transformed into the coloring problem of two-dimensional meshes .
Because the parameter is exponential , So the grid is very small , Use the plug directly dp That's it .
If the solution is correct , The idea is very similar , How many pieces of the same color are there , The inclusion and exclusion can become a similar dyeing problem , The same applies to plugs dp solve .
The plug that has mastered the minimum representation dp.
But plug dp There are still too few exams , I don't think I can think of it in the examination room / finish writing sth. , Practice the plug dp.

T3

The ideas in the examination room are very similar .
Positive solutions are also virtual trees , It just takes advantage of the nature of partition , bring The complexity of each virtual tree is $O(m)$ Of , The complexity is $O(mlogm)$
This kind of partition is not very common , neither CDQ, It's not a whole dichotomy , Nor is it a segment tree divide and conquer , So it doesn't feel like .
There are really many details .
At the same time, you need to contact lct Operation of maintaining subtree , although NOI Not very good at the exam, but if you are proficient, you can still save time .