P1552 [APIO2012] 派遣#

Useful Link
Problem Statement
Reference Blog

The problem gives we a directed and rooted tree. So we can use DSU on tree to solve this problem.

For each leaf, initialize a DS with this node. When combine information of son to take more ninja in limit, pop the most expensive ninja and leader is now node, so answer is set.size() * leader[u].

P2173 [ZJOI2012] 网络#

Useful Link
Problem Statement
Reference Blog

We noticed that the color in this problem less than 10 type. So we can maintain information of each chain which different color. Actually, it’s a common trick to maintain chain.

When connect node $u$ and $v$, we should check they must on different chain, and because of nature of chain, $u,v$ must be the endpoints of their chain. This part we can write a function link to quick check it’s valid to connect these node or not.

For operator 1, we can regard it as cut and link, so the link function in last part can be used here. Cut operator is easy, FHQ-Treap can do split operator easily.

P2497 [SDOI2012] 基站建设#

Useful Link
Problem Statement
Reference Blog

Let $f_i$ denotes the minimum cost make node $i$ connect to starter.

We can get a transition function that $f_i = \min_{j<i}(f_j+w(i,j))$, and function $w(i,j)$ denotes the minimum cost to connect node $i$ and node $j$. We can use Pythagorean theorem to expand it.

Then we can change transition function to:

Li-Chao Segment tree can solve this problem easily, just query minimum at $x_i$, transition, and push line $i$.

P3081 [USACO13MAR] Hill Walk G#

Useful Link
Problem Statement
Reference Blog

Most of solution in luogu is using Lichao Segment Tree. But I want to solve these problem by Balance Tree. So here is a different solution.

Also we need scanning-line to find all segment which satisfy $x_1 \le x < x_2$ ($x$ is the position bassie located), then we need to find a way to sort these segment let we can use single operator such eraser begin to maintain answer quickly.

Because problem promises the segment never cross, so the hierarchical relationship will never changed with position of bassie.

Then we can sort it by now position.

1
struct Comparator {
2
    const std::vector<Segment>* seg;
3
    const ll* sweep_x;
4

5
    Comparator(
6
        const std::vector<Segment>* seg_ptr = nullptr,
7
        const ll* x_ptr = nullptr
8
    ) : seg(seg_ptr), sweep_x(x_ptr) {}
9

10
    bool operator()(int lhs, int rhs) const {
11
        if (lhs == rhs) {
12
            return false;
13
        }
14

15
        const Segment& a = (*seg)[lhs];
16
        const Segment& b = (*seg)[rhs];
17
        const ll x = *sweep_x;
18

19
        __int128 dx_a = a.x2 - a.x1;
20
        __int128 dy_a = a.y2 - a.y1;
21
        __int128 dx_b = b.x2 - b.x1;
22
        __int128 dy_b = b.y2 - b.y1;
23

24
        __int128 val_a =
25
            (__int128)a.y1 * dx_a + dy_a * (x - a.x1);
26

27
        __int128 val_b =
28
            (__int128)b.y1 * dx_b + dy_b * (x - b.x1);
29

30
        __int128 left = val_a * dx_b;
31
        __int128 right = val_b * dx_a;
32

33
        if (left != right) {
34
            return left < right;
35
        }
36

37
        return lhs < rhs;
38
    }
39
};

Left part just like monotonic queue, believe it’s easy to realize.

P3215 [HNOI2011] 括号修复 / [JSOI2011] 括号序列#

Useful Link
Problem Statement
Reference Blog

For this classic problem, I am first time knowing that have a formula to calculate answer. We let ( denotes $-1$, ) denotes $1$, define $\text{premax}$ denotes maximum of prefix sum, define $\text{sufmin}$ denotes minimum of suffix sum. Then we can denotes answer by

The prove is easy. Don’t misremember the formula, it’s not sum of premax ad sufmin then divide by two, here is a counterexample: )(.

Then we can use FHQ-Treap or Segment Tree to solve this problem easily.

P3224 [HNOI2012] 永无乡#

Useful Link
Problem Statement
Reference Blog

Also a classic problem, in this problem we know Balance Tree also can be used to simulate DSU.

Use Treap to simulate DSU, combine each block and query the k-th maximum is easy.

P3268 [JLOI2016] 圆的异或并#

Useful Link
Problem Statement
Reference Blog

We are given a strange condition just like [USACO13MAR] Hill Walk G, because of the circle in this problem never cross, so the relative position never change. We can use set and scanning-line to calculate nesting levels of a circle.

Then because of we are calculating XOR area, even nesting levels lead to negative and odd lead to positive area.

P3586 [POI 2015 R2] 物流 Logistics#

Useful Link
Problem Statement
Reference Blog

The core idea is to find the total contribution is

We will output TAK if total contribution greater than $c\times s$, or output NIE.

Then we can use BIT or Balance Tree solve it easily.

P3968 [TJOI2014] 电源插排#

Useful Link
Problem Statement
Reference Blog

First we can simulate the operation of this problem, to get all possible position. Because full scope can reach $10^9$, but the query just less than $10^5$, so this simulte can help we discretize.

So the first challenge is to simulate it. We can build two set. And one for coming, another one for leaving. More details, let the set used to manage coming to sort by length and right endpoint. So the begin is the range which next student will use.

And when a student leave, we need combine three ranges: [l, x), [x], (x,r]. We let set used to manage leaving sort by left point, then we can use binary search ( find(), the member function of std::multiset) can solve the question easily.

Whatmore, there is a small detail when manage leaving. We can allow empty range exist. For example, there is a range [x, x], then a student use it, we also can make three ranges: [x, x-1], [x,x], [x+1, x]. Although the first and last range is invaild, but it can minus a lot of unnecessary special check.

After simulation, count is easy. This approach is off-line, and count we can use BIT or Segment Tree to solve it easily.