给定长度为 $n\le10^5$ 的序列 $a$ ，统计满足以下条件的子区间数量

区间 $[l, r]$ 中，存在一个数 $x$ ，它的出现次数为 $m$，并且 $2m>r-l+1$

给定两个长度为 $n$ 的序列 $a,b$ ，定义 $c_{i,j} = a_i+b_j$ ，输出 $c$ 的 $n\times n$ 个元素中前 $k$ 小

$n\le10^5$

题目链接

第 $i$ 个点，给定 $x_i\le i\le y_i$ 和权值 $a_i$

$q$ 个询问，回答

$n,q\le 10^6$

我们称一个排列是合法的，当且仅当每一个数都满足这个数比它相邻的数都要大或都要小。

求长度为 $N$ 的合法排列数量。

给定 $n\times m$ 整数矩阵，选取 $k\times k$ 正方形区域，使其中「最大值减最小值」最小

给定 $n\times m$ 棋盘，每格只能放 $1$ 个棋子，每行每列最多放 $2$ 个棋子，问方案数量

给定一个只含 B, L 的字符串序列

定义一次变换为：B 扩展为 BL，L 变成 B，例如 BBLBL -> BLBLBBLB

求经过无数次变换后，$\sum_{i=l}^r [s_i=\text{B}]$ $(~l\le r\le 2^{63})$

首先感受到这是数据结构题

然后发现你需要用数据结构维护序列，支持

• 删除第 $k$ 个数
• 在末尾加入一个数

考虑用平衡树维护

注意到 $n=m=q=3\times 10^5$ ，肯定不能把点一个一个开出来，所以一个节点就表示一个区间 $[l, r]$ ，用 prefix 表示 $l$ 的编号

发现 FHQ-Treap 可以比较自然地维护 因为我只会写无旋 Treap

新增一种操作 unfold(u, x) ，调用时保证 u->l <= x <= u->r

表示将 $u$ 分裂成 $[l,x-1]~~[x, x]~~[x+1, r]$ 三部分，且 $[x,x]$ 为子树的根

并且保证分裂后 u->l == u->r == x

首先发现 $k$ 很小，自然地想到 DP

令 $d$ 表示最短路

$f_{u, x}$ 代表从 $s$ 到 $u$ 路径长为 $d_u + x$ 的方案数量

称贝壳的种类为颜色

考虑离线做法，将询问按照 $r$ 升序排序

发现只需要维护每个颜色的目前最右出现位置（ $\le r$ ）

每个颜色只在最后出现的地方进行统计，显然可以保证最优（因为离线）

举个例子

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

颜色序列为
1 3 1 2 1

扫到 1 （位置）
1 0 0 0 0
扫到 2
1 1 0 0 0
扫到 3
0 1 1 0 0
扫到 4
0 1 1 1 0
扫到 5
0 1 0 1 1

0/1 序列用树状数组维护即可，答案即是 0/1 序列 $sum(l, r)$

在线做法，用可持久化线段树即可