7.6 simulation summary

Goo Goo Goo

I thought a car of people would pass

Because of the average 170+

I was a bit surprised

Time arrangement

7.30-9.00

Look at the question Feeling T1 Obviously, pressure T2 Almost 50 T3 It's just n^2 I thought about it for a long time. T2 What else do you do It feels monotonous But I didn't catch the idea

Call first T2 violence

9.00-10.00

It doesn't feel good Thought for a while T3 No idea

And then I hit T3 The violence of

10.00-10.40

I hit T1 The violence of Thought about it for a while Think T1 Is there any mysterious practice in the second gear of （ Because it's a picture ） It feels like a tree dp That smell But not very good

10.40-12.00

Recall T1 In response, the monotonicity of decision-making can be cut in blocks

Then try to recall how to maintain interval inverse ordinal numbers Here I made a mistake Because I heard it before noi That question I think the inverse number of intervals is very complex （ In fact, the field is pushed out ） After pushing it out, I still feel a little unclear, so （ Because noi That question has both range and range limits ）

Finally, there is not enough time （ There's nothing left 20 minute ） Just check the question

Topic analysis

T1

$f[S,op1,pos,op2]$ The status of the current point is $S$ Whether the status at the end is $op1$ At point $pos$ On The state of the last side is $op2$

Consider the transfer according to the situation

1. Normal analog transfer

2. $op1=0$ When I arrived at a marked point ： You can consider turning to $op1=1$ Plus contribution

3. $op1=1$ Enumerate a mark point that has not been passed as a new starting point Simultaneous direction $op2=1/0$ Transfer

It seems that I am better at making pressure dp One o'clock

T2

$f[i]$ It means that the last paragraph is divided into $i$ The minimum cost of

It can be noted that The price is the inverse sequence of intervals Then consider filling in each number Different positions in front From small to large The increased value is not increased Form like $5554444321111...$（ The position where the value changes is a larger number ）

Then you can $n^2$ do

Based on this property It can be proved that the decision is monotonous

So there is $nlogn\sqrt{n}$ Decision monotonicity nested block approach

upd

The exact solution is cdq Monotonicity of nested divide and conquer decision + Similar to Mo team method Maintain two pointers Violent jump interval reverse order pair

The reason why we need cdq Set it up Because the monotony of divide and conquer decision requires that there is no dependence between the contents And this depends So pass cdq Divide and conquer to get the front dp value

T3

This is really not I just want to n^2 Or sprinkle some