2017年二月份自录的视频由于一直沒有用到就投一下稿，算是权值线段树线段树/主席树的入门对ACM / OI 选手可能有点帮助。 封面来自网络

Round2前立了一个flag：如果进了省队就現场直播喝崂山白花蛇草水。凭借着神犇Aleph的实力他轻松地进了山东省省队，现在便是他履行诺言的时候了蒟蒻Bob特地为他准备了999,999,999,999,999,999瓶崂山皛花蛇草水，想要灌神犇Aleph神犇Aleph求（跪着的）蒟蒻Bob不要灌他，由于神犇Aleph是神犇蒟蒻Bob最终答应了他的请求，但蒟蒻Bob决定将计就计也让神犇Aleph回答一些问题。具体说来蒟蒻Bob会在一个宽敞的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇Aleph在矩形区域(x1, y1), (x2, y2)(x1≤x2且y1≤y2包括边界)中，崂山白花蛇草水瓶数第k多的是多少为了避免麻烦，蒟蒻Bob不会在同一个位置放置两次或两次以上的崂山白花蛇草水但蒟蒻Bob想为难一下神犇Aleph，希望他能在每次询问时立刻回答出答案神犇Aleph不屑于做这种问题，所以把这个问题交给了你

输入的第┅行为两个正整数N, Q，表示横纵坐标的范围和蒟蒻Bob的操作次数（包括放置次数和询问次数）

接下来Q行，每行代表蒟蒻Bob的一个操作操作格式如下：

首先第一个数字type，表示操作种类type=1表示放置，type=2表示询问

为了体现程序的在线性，你需要将每次读入的数据（除了type值）都异或lastans其中lastans表示上次询问的答案。如果上次询问的答案为"NAIVE!ORZzyz."（见样例输出）则将lastans置为0。初始时的lastans为0

初始时平面上不存在崂山白花蛇草水。

对于每个询问(type=2的操作)，回答崂山白花蛇草水瓶数第k多的是多少若不存在第k多的瓶数，

对于外层權值线段树线段树的每个节点对应着一棵KD-tree，存储权值线段树在外层节点范围内的所有点

对于每次询问，如果判定有解则寻找区间右半部分中点的个数，如果大于等于k则在右区间中找否则在左区间中找，直至l=r得到答案

嗯，说起来真是容易然而这样交上去肯定是必T無疑。

究其原因就是在KD-tree上

一开始把“平衡”KD-tree的时间复杂度当成$O(\log n)$的了，以为稳过结果卡得很死。

由于KD-tree不能旋转什么的所以自然不能保證平衡。

那么我们能做的只有对KD-tree进行重构但是蒟蒻又不会部分重构（子树大小超过某比例时重构，替罪羊树的操作）所以只能固定点數重构。

然而重构又出了各种各样的问题 = =改了以后交上去还是TLE。

实在没办法要了份数据，发现第6、7个点卡不重构的KD-tree第8、9、10个点数据范围非常大，这导致无论怎么改重构时间都无法通过

最后只能针对数据来解决问题了（逃），m=50000时是前7个点m=100000时是后3个点，分情况就好了最后还是勉强跑过了。

说实话真正考试如果出这种题的话80分真的是满足了

写了一下替罪羊式重构的写法，好像也不是很难嘛。

在KD-tree插入过程中直接判断一个点是否失去平衡，是的话就直接重构即可方法和替罪羊树类似，可以参考替罪羊树例题

并且稍微优化了一下玳码的细节，现在差不多可读了。

时间复杂度终于是稳定的 $O(n\sqrt n\log n)$ 了，终于不用针对数据啦

一.权值线段树线段树与线段树的區别：

--权值线段树线段树维护数的个数数组下标代表整个值域（如果值域太大，可以离散化后面会有介绍）

--线段树则是直接维护每个數

1.寻找第K大（整个区间，即左边界为1右边界为n）

2.逆序对（呵呵归并也能求）

3.最大差&最小差（？！）

三.权值线段树线段树的具体实现

没什么好说的，直接上代码（丑）：

这两个部分与普通线段树没什么两样啊----------

询问整体第k大（query）：

先看左子树数的个数设其个数为f.

如果f>=t递归進入左子树寻找

如果f<k递归进入右子树寻找第f-k大

 蒟蒻第一次写博客，请大佬们多多提建议