题面 洛谷P3285 Solution 这是一道数据结构大暴力题。 我们可以很显然的发现对于询问排名，维护排名的操作，我们可以直接上一个维护下标的splay。 因为点的数量奇多，这让我们回想起NOIP2017 列队，我们可以用“splay 动态开点”这样的操作来解决，即一开始我们把所有信息全部压到一个点里面去（即一个点代表一段区间），需要的时候再用“拆点”把点拆开。 问题是这破题很让人讨厌地出了两个基于编号的操作。因为我们的splay是以下标做为权值来的，失去了维护编号的能力。 怎么办呢？我们可以考虑直接记录每个编…

题面 洛谷P4197 Solution 这题的确是可以用库鲁斯卡尔重构树+主席树来搞，但是本蒟蒻太菜了并不会，因此只能给大家讲讲离线+splay启发式合并的搞法。 首先，我们考虑把询问离线下来并按限制从小到大排序。然后我们可以考虑把边一条一条插入到图里面去，直到某个询问的限制。这样子，问题就变为了询问某一个连通块的K小值，连通块可以合并。 这个问题就肥肠简单了，我们可以用各种各样的数据结构来处理，线段树合并，splay启发式合并都可以。 考虑到每个点期望加入$logn$次，时间复杂度为$O(nlogn)$ Code…

题面 传送门：洛谷 Solution 首先，长成这样的题目一定是淀粉质跑不掉了。 考虑到我们不知道K的大小，我们可以开一个splay来统计比某个数小的数的数量。 不会点分治的戳我 Code #include<iostream> #include<vector> #include<cstdio> using namespace std; long long read() { long long x=0,f=1; char c=getchar(); while(!isdigit(c)…