起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭 可持久化线段树的本质是很多棵形态完全相同的线段树。 也可以理解成是，保存了不同时刻版本的线段树的数据结构。 如果没有可持久化线段树，那么我们如果需要不同时刻的线段树，无脑的做法可能是，需要多少个时刻的线段树，就建多少棵线段树。 但是空间绝对gg，我们考虑每次修改，其实对于一次修改，线段树上只有很少一部分被修改了，其他部分都一样。 因此，我们很容易想到，我们何不只考虑修改的部分，其他部分共用，以减少时间和空间消耗呢？ * 可持久化线段树是利用函数式编程的思想，对记录的数据只赋值不修改，每次插入一个数据后保存一个历史版本，然后利用线段树的结构完全相同，可以 …

题目链接 题意： 给定一个序列 n，有 m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。 思路： 先分解一下问题，我们要求一段区间位置的中位数，其实可以分解成，求区间中不同数的个数+求区间中第k大的下标。 对于求区间中不同数的个数，离线可以随便线段树，树状数组，或者莫队也行（观察到数据范围<=2E5) 在线的话，就只能可持久化线段树了。 看到一些题解中说要倒序处理...但是之前写求区间不同数的个数，我都是倒序处理的啊？ （回想一下，当时似乎正序处理也行... 倒序处理是为了，处理到第i个的时候，第i个一定是当前后缀区间中，第一个出现的... 然后第二个问题，求区间中第k大的下 …

Description 给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1 ],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改 变后的a继续回答上面的问题。 Input 第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。 分别表示序列的长度和指令的个数。 第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。 接下来的m行描述每条指令 每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数 …

题意： 求区间第k大数 思路： 可持久化线段树。 其实这东西在国内更常见的名字应该是 zhu xi 树？应该是由于“中国高端数据结构领导者”的hjt比较早得引入（？推广？）而得来的。 不过之前没写什么东西都被封，写个zhu xi 树，怕是政治敏感够枪毙100回了orz 似乎也叫函数式线段树。 写个模板题练下手。学习笔记之后补。 /* *********************************************** Author :111qqz Created Time :2017年10月16日 星期一 21时51分55秒 File Name :2104.cpp …

题目链接 题意： 给定二维平面的n个点，要求一个面积最小的正方形，使其能覆盖所有的点。 思路： 先考虑如果水平竖直地放置正方形（边和坐标轴平行）圈住所有点的最小正方形的边长是: L=max(xmax−xmin,ymax−ymin) 然后考虑如果正方形旋转的话，能圈住所有点的正方形边长是随着角度先减后增的，有凸性，可以三分。。。 但是枚举角度计算正方形的话比较麻烦，可以选择旋转平面上的点，使得正方形仍然是水平竖直放置的，因为这样计算正方形的边长比较方便。 如果把点表示成极坐标形式: x=r×cosθ,y=r×sinθ,，θ是极角 那么顺时针旋转 α 角度后： x′=r×cos(θ−α),y=r×sin(θ−α) 化简一下 …

题目链接 题意： 有n个点，表示n个圆的圆心，问一组圆的半径，满足相邻(i,i+1)或者(n,1) 圆相外切。 思路： 我们发现确定第一个半径之后，其他的圆的半径似乎能解出来？ 然后发现，其实只有n为奇数的时候能解出来，n为偶数不行。 那么我们可以奇数偶数分别处理。 对于奇数，直接解出来。式子不写了，很好推。 对于偶数，我们发现，最后会是一个关于r1的二次表达式。 一眼三分。然后训练的时候我就直接三分了。。？？？ 三分的过程中判断一下是否所有圆的半径都满足实际意义。。。 然而这是错得，而且错得很显然。因为。。如果不满足实际意义，是根本没办法判断，该往哪个方向继续三分的。 然而这是错得，而且错得很显然。因为。。如果不满足实际意义，是根 …

题意： 给定一个 N∗N(N≤4e9) 的矩阵，现在经过这样一个变换：将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0≤x<N,0≤y<N) 现在求经过多少次这样的变换之后在回到 N∗N 的原始矩阵。 思路： 在模n的剩余系下可以写成(fib(n)x+fib(n+1)y,fib(n+1)x+fib(n+2)y)的形式fib(n)表示Fibonacci数列的第n项 所以就成了斐波那契数列循环节。。经典题。注意会爆long long,要用ULL 又写了遍板子，去年的东西都忘得差不多了orz /* *********************************************** Author …

题意： 有一棵树，水源在根节点1，房子在叶子节点。有若干操作，操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水，可以通过切断边实现（如果某个叶子节点到根节点的路径上有一条边被切掉，那么就不能供水了。）对于每次操作后，问不给所有歹徒供水最少要切多少条边，并且问在切满足前面最小的情况下，最少使得多少个良民受影响。初始没有歹徒。 思路： 我们先考虑第一个问题。容易知道，假设与根相连的有k条边，那么最多只需要切k次，就切断了所有房子的水源。 也就是说，从最少切的次数角度的考虑，切与水源相连的边一定是最优的。 我们可以考虑把树根1去掉，这样得到k棵子树 然后可以预处理出，对于每个叶子节点，其非根的最远祖先是谁，也就是k棵子树的根节点都是 …

题目链接 题意： 在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。 思路： 训练的时候一眼二分，但是求圆并的时候gg了。。毫无思路。 搞定了多个圆面积并。。这题就很easy了。。 需要注意，每次二分的时候，记得初始化圆的d... /* *********************************************** Author :111qqz File Name :H.cpp …

题目链接 题意&思路： 给出n个圆 求恰好k个圆相交的面积，k属于1..n 先放个别人的代码。。。 我真是体会到了。。。软件工程这门课的重要性。。。 这代码真是烂得印象深刻。。。几何题全是面向过程？ circle和point 类写在一起。。。感觉所有糟糕的写法这份代码全都占了。。。 /* *********************************************** Author :111qqz Created Time :2017年10月11日 星期三 19时53分30秒 File Name :ciru.cpp ************************************************ …