来自 [PhoenixGS] 的全部文章

BZOJ3572 [Hnoi2014]世界树

题目大意 一棵树,边权为1。次询问。 每次给出个关键点,树上的每一个点被离它最近的关键点管理,如果两个关键点和它距离相等,那么取序号小的那个关键点。 问每个关键点管理多少点。 $ n, q \leq 300000, \sum{m} \leq 300000 $ 题解 建完虚树后跑DP算出每个关键点被哪个点管理以及距离。 然后对虚树中的每条边计算答案,以及计算不再虚树中的点的答案。 代码 C++ #include <cstdio> #include <cstring> #include <algorithm> const int INF = 1e9; int n, m; int x[8000 ......

BZOJ4736 温暖会指引我们前行

原题链接 http://www.lydsy.com/JudgeOnline/problem.php?id=4736 http://uoj.ac/problem/274 题解 维护关于温度的最大生成树 用LCT来维护 啦啦啦,草率的题解 代码 C++ #include <cstdio> #include <algorithm> const int INF = 1e9; int n, m; int uuu[400000], vvv[400000]; int x[500000], tem[500000]; int minx[500000], pos[500000], sum[500000], rev[500000]; int fa[500000], ch[500000][2]; int top; int stack[500000]; int f[500000]; char st[100]; inli ......

BZOJ3545 Peaks

题目大意 在Bytemountains有N座山峰,每座山峰有他的高度h_i。有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1。 N,Q<=100000 题解 对路径按困难值排序 对询问按x排序 然后可以用平衡树合并也可以线段树合并 所以当然是写简单易懂的线段树合并啦 我们要来膜拜一下hjq大佬 代码 C++ #include <cstdio> #include <algorithm> str ......

BZOJ3196 Tyvj 1730 二逼平衡树

题目大意 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x,且最大的数) 5.查询k在区间内的后继(后继定义为大于x,且最小的数) 题解 我过的第一题树套树吧QWQ 第一维用区间线段树,第二维用权值线段树,开始要离散化 第一个操作就是求和 第二个操作二分 第三个操作是修改 第四五个操作可以直接用一二两个操作来实现 好吧就是一道裸题,但有点难写 代码 ......

BZOJ3626 LCA

题目大意 给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1 设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先 有q次询问,每次询问给出l r z,求$\sum_{i=l}^{r}deep[LCA(i,z)]$ 题解 做这题,首先要发现一个事实:两个点的LCA的深度就是两个点分别到根的链的公共点 所以,对于一次询问,可以将[l,r]区间内的点到根的链的每一个的权值+1,答案即为z到根的链上的点的权值和 这个是可以用树链剖分维护的 对于多次询问,我们将一个询问变成[1,l-1]和[1,r]两个询问,将询问排序,一边更新 ......

BZOJ2286 消耗战

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 C++ #include <cstdio> #include <algorithm> #include <cstring> const long long INF = 1e18; int edgenum; int vet[600000], val[600000], nextx[600000], head[300000]; int fa[300000][22]; long long f[300000]; int cnt; int ......