题目中说明了 $y_1 \thicksim y_n$ 是的一个排列，我们把这 $N$ 个点按照横坐标排序后的纵坐标排列记为 $a$。

根据题意要找的图腾这样是，很明显可以看出要我们求逆序对。

在求逆序对中，我们可以求得一个序列中每个数后面有多少个数比它小，类似地，我们可以：

1.倒序扫描序列a，利用树状数组求出每个 $a[i]$ 后边有几个数比它大，记为 $right[i]$；

这道题没想象那么难，其实就是一个极其简单的对树状数组的运用。

可能一开始看到题目要求的是左下方的星星，你可能会立刻想到用二维树状数组，但是请你不要像我这么浮躁，认真看完题目。

注意，每一个点上只有一个星星，按 $Y$ 的升序给出坐标，如果 $Y$ 相同，则按照 $X$ 的升序给出！！！

树状数组是一个很简洁很方便很好用的一个结构，相比起线段树有如下几个优点：

1. 节约空间：树状数组规模为 $n$ ，但是线段树至少有 $2n$ 个节点，再算上其他维护的数据域，空间一般比树状数组大 $10$ 倍；
2. 编程复杂度低：线段树比树状数组编码复杂度要高许多，这一点大家自己编程体会；
3. 时间复杂度低：线段树维护的数据域太多，操作的时间复杂度要比树状数组高。

并查集($\text{Disjoint-Set}$)是一种较为简单的数据结构，主要用于解决连通性及动态维护集合的一些问题。

一、操作

并查集主要有两个操作：

1. 查询($\text{Get}$)，查询一个元素属于哪个集合；

2. 合并($\text{Merge}{}$)，把两个集合合并成一个大集合。

这题是楼教主男人八题之一！！

这道题看起来比普通的取石子游戏要难，其实要简单的多。

从简单开始推起。

首先假设只有一堆石子，那么显然先手必胜。

再来看假设有两堆数目相同，那么按照两者都按最优策略来取石子，显然后手必胜。

那么如果是两堆石子数目不同的石子呢？

很显然，先手可以先取多的那一堆把他变成两堆数目相同的石子，然后就变成了上一种情况，此时先手又是必胜。

_{一道基本跟博弈论毫无关系的题。}

维护一个保护集合 $S$ ，表示哪些点 $A$ 可能胜利。

首先将所有绿点加入 $S$ 。

1. 对于一个不在 $S$ 的 $A$ 点，若它存在某个后继在 $S$ 中，则将其加入 $S$ 。
2. 对于一个不在 $S$ 的 $B$ 点，若它所有后继都在 $S$ 中，则将其加入 $S$。

博弈论做法！！

题面可以简化为，有一堆石子，两个人轮流取紧邻的 $c,z,n$ 个石子，谁不能取了谁就输了。

然后就很明显的套SG函数做。

注意！！！：

1. 枚举要拼凑布条的起点，可以从 $1 \rightarrow \text{终点}-\text{长度}+1$ 。

2. 注意要提前预处理，否则每次时间复杂度太高，会爆。

3. 每个局面包含的子状态有两种，比如起点枚举到 $j$，若不取则为 $j-1$，取了下一段的长度就变为了 $i-(j+a-1)=i-j-a+1$，即另一个子状态，两者异或即为此状态的 $SG$ 值，然后 $mex$ 运算求解。

潘老师镇楼

在很久很久以前，有这样一个广为流传的小游戏：

给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜，两人都采取最优策略，问先手能否必胜。

这其实就是著名的采石子游戏。

由此引来第一个知识点：

例：给出 $n$ 个数对，$a_i$，$b_i$，选出 $m$ 个数对，使得 $\sum \frac{a[i]}{b[i]}$ 达到最大值。

思路：

首先如果选取 $i$，定义 $x[i]=1$ 否则 $x[i]=0$。

$R=\sum \frac{a[i]\times x[i]}{b[i]\times x[i]}$。

生平罕见，竟会有如此思维难度如此高的题

这道题很难很难，非常难，但是题目很简短，代码也很简短，一道递推。

题目大意：对于一个 $4n$ 的图求哈密顿回路。

---

前置知识

1. 哈密顿路：由一个点出发到另外一个点结束，要求经过图中所有的点的一条路（不能重复经过点）。

2. 哈密顿回路：从一个点出发再回到此点，经过图中所有点的一条路（不能重复经过点）。