势能线段树

看《区间最值操作与历史最值问题》 但是没有看懂。于是讨论了一下，总结摘抄至此, 不过我我感觉味道太大了。不是很爽。

Segment Tree Beats：标记类与回收 DFS 复杂度笔记

0. 讨论对象

这里讨论的是区间 chmin/chmax 的复杂度分析。

However, Register is now deprecated.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

C++ keyword: register

 C++ C++ language Keywords
Usage

- Automatic storage duration specifier (deprecated).
(until C++17)
- The keyword is unused and reserved. (since C++17)

See also
- auto (Automatic storage duration specifier)
(until C++11)

Recollect Numbers

有 2n 张卡片，上面分别写着数字 1,1,2,2,…,n,n。换句话说，对于每个 j=1,2,…,n，恰好有两张卡片写着 j。每张卡片正面只写了一个数字。 你要玩一个翻牌游戏。初始时，所有 2n 张卡片都背面朝上（没有数字的那一面）。每一回合，你恰好翻开两张卡片。如果这两张卡片上的数字相同，就把它们丢弃；否则，把它们翻回背面朝上。当所有 2n 张卡片都被丢弃时，你就赢了。注意：你不必同时翻开两张牌，所以在看到第一张牌的数字后，你可以根据它来决定第二张要翻哪一张。 考虑下面这个“贪心”算法来玩这个游戏。初始时，2n 张卡片以任意顺序排成一行。然后每回合的策略如下：

I mean is it true?

赛时不会做。知道3个数字时， k 可以等于第二小的，但是没办法推广了。

比如： 5,3,2 k = 2 的时候：

1
2
3
4

5,3,2
2,3,5
2,5,3
5,2,3

下面不会推广了。麻了。想了很多的错误答案。

2184E 寻找有多少个子数组满足 k-exquisite，即相邻数字的差 > k。对任意 k [0, n-1] 都要有个解。

题解

不难想到 k 可以从大到小构建。

先新建差分数组，再按照其值从大到小排序，差分值为第一关键字降序， pos 第二关键字升序 我们发现，比如假设我们算好了 k = n - 1，当 k = n - 2 的时候，可以通过算贡献的方式，计算出新增的贡献。