• 局面 $(x,y)~~~ x,y>0$
• 操作 $(x,y)\rightarrow(a,b)~~~a+b=x$ 或 $a+b=y$

$x,y\le 2\times 10^9$

先手必败还是必胜？

• 局面 $(x,y)~~~x,y\geq0$
• 操作 $(x,y)\rightarrow(x-\lambda y, y)~~(x-\lambda y,y\geq0)$
• $(x,0)$ 是败

给出 $(x,y)$ 求是否为先手必胜

给定长度为 $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