题面 传送门:洛谷 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)…
题面 传送门:洛谷 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)…
什么是淀粉质点分治? 就是把分治搬到树上,以某个点为根,分别分治处理子树的答案,再计算子树与子树间的答案的玄学算法。 举个例子: 如何求出一颗树上距离为K且所经过的点最少的点对? 对于这种题,我们可以把某个点(一般为重心)作为根,然后对左右子树递归处理,先分别得出左右子树的答案,再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题,如果我们用传统的暴力做法,最优的复杂度只能得到O(n2)的暴力枚举,但是如果我们用淀粉质来搞,我们就可以做到O(n∗logn)的复杂度(如果K很大的话,我们可能还得套个…
COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.
Theme Kratos Made By Seaton Jiang