[learning notes] segment tree selection

It's all violence

It's tiring to hit the line tree

Fibonotci

At first glance, this linear recurrence relationship is obviously matrix multiplication

The code ...

call .. Finished writing .

Two Permutations

Sequence hash ？

Rather, it is called segment tree maintenance sequence hash Worth a good question

analogy Permutation . The essence is to express complex states as an integer , This complexity is better .

Strange Addition

Obviously, segment tree maintenance dp .

Attention to detail . And don't be too heavy .

If the implementation is fine, you don't need to go to the leading zero . Slight seizure .

Strange Array

Worship wicton .

This question is not so obvious .

Consider from [i,i] Expand

Discussion on parity between partitions

Consider one $<a_i$ The sum of $>a_i$ The number of will offset

hold $a_i$ as $<a_i$ and $>a_i$ Consider two cases twice , In this way, equal elements will not appear

take $\le a_i$ The number of $1$ ,$>a_i$ The number of $-1$

Expand left and right respectively , Find the largest sub segment and $ans$ , Contribution: $\lfloor \frac{ans-1}{2}\rfloor$

take $\ge a_i$ The number of $1$ , $<a_i$ The number of $-1$

Expand left and right respectively , Find the largest sub segment and $ans$ , Contribution: $\lfloor \frac{ans}{2}\rfloor$

The code ...

call .. Finished writing .

Phoenix and Memory

He who travels a hundred miles , Half 90 .

First, greedy for a group of solutions

If you want to get different sequences , There must be $(i,j)$$(i\ne j)$ bring $l_i\le a_j\le r_i$ also $l_j\le a_i\le r_j$

Perceptual understanding , If you change more on the greedy optimal plan , The plan is even worse .

Proof omitted .