2022/3/11 exam summary

Match time arrangement

7:40~8:00

Read the question , Find out T3 It's the original question
Vaguely remember that polynomials accelerate the first kind of Stirling numbers
To be on the safe side, I wrote a violent calculation of the first kind of Stirling number
It's just a sample
Because there are lessons from the past , So I dare not write polynomials , Let's go to the first two questions

8:00~8:20

T2 Of $k\le 3$ It's strange
$k=1,k=2$ It's easy to do
however 3 There is no nature
A push , It is found that for a left endpoint , The change of the bitwise and of the continuous interval is $O(log{a}_i)$ Grade
Because if everyone becomes 0 It won't change
You can open a bucket for each binary bit , Looking for the first one after two points in the bucket will make the current from 1 become 0 The location of
Then the number of such intervals is $O(n\log a)$ Of
And then when you check , Take the inquiry offline , Just use a segment tree to maintain
Then write quickly

8:30~9:00

Write T2

9:00~9:40

After you've written , A violent confrontation
There is no problem with the accuracy , But the constant is very large , ran 2.3s
Plus fast reading , Change the line segment tree into a tree array , Found that only ran 1.7s
But there is still the risk of being stuck
After testing, I found that the output actually lost 800ms
Change to quick write , Just run in 1s Within

9:40~10:10

T1 No idea , Wrote a $O(n{m}^2)$ The practice of
Expected score 45pts

10:10~11:15

I quickly recalled how to find the first kind of Stirling number
It seems that only one is needed NTT And a multiplier
Just hurry , Take a picture after the yard , Then Kaka often , It shouldn't be a big problem

11:15~11:50

Check , Right beat

Summary of setting questions

T1
In fact, the essence is offline scanning line , Just keep adding , Become constantly deleted
however , It's the first time to see a trie The operation of merging the sons of trees
Then heuristic merge maintenance
It feels wonderful
T2T3 The train of thought is the same as the solution