YNOI Wisdom Question
EasyVer1 [Ynoi Easy Round 2015] The happiest girl in the worldEasyVer2 Xiaobai visits the park
See firstEasyVer2
Single point modification interval query maximum sub-segment sum
Consider online segment tree maintenancePrefix max，Suffix max，sum,andansmax
Just discuss it when merging
Modify it directly and then return itpushupJust
Next isEasyVer1
Global modification interval query maximum sub-segment sum
Think about the essence of global modificationsumIt's easy to maintain
forPrefix maxandSuffix maxFor global modification, a function is added once.ansmaxIs it fromPrefix maxandSuffix maxLaunched
So the problem isPrefix maxandSuffix maxHow to maintain
Actually, this is a classic problem. It is often used in slope optimization.
It is to maintain an upper convex shell, which is fixed point based on the slope
But the problem arises again. We have two upper convex shells. Let's abstract the problem
We have 2 upper convex shells, please remember them as\(f(x)\)and\(g(x)\)We need to ask\(f(x) + g(x)\)Maximum value of
The problem becomesgeometry
This is one of the applications of Minkowski
We can directly merge the two convex hulls and then divide them into two parts in the new convex hull.
thenEasyVer2Just finished writing
Next is the boss battle
The typical idea is to useEasyVer2Global extra points
Then the whole piece becomesEasyVer2, block reconstruction line segment tree
Analysis complexity
- Complete modification\(O(1)\)
- Scattered block modification\(O(B\ log\ B)\)
- Whole query\(O(B\ log\ B)\)
- Scatter block query\(O(B\ log^2\ B)\)
To sum up\(O(n\sqrt n\log n)\)
1s 1e5 Is this right
Consider optimization
- Scattered modifications
We don't have to rebuild the entire line segment tree, but we consider hitting the subtreetag, but thistagCan't hit the node, which will interfere with the original mark. If you hit the convex hull, there will be no problem. - Whole query
Blocks, offline? Process it piece by piece! Press the querytagAfter sorting, process it. Just do it with a pointer. Linearity?
No, your sort does have log! But there will be no problem with the sorting of cardinality
This way we optimized\(O(m \sqrt n)\)。
Next, the constants are optimized.
Acknowledgement:getdiff luogu608273geomerty luogu765066