青竹qingzhu

主席树

AC自动机(3) KMP(3) tarjan(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / 主席树（共2篇）

P2633 Count on a tree 树上主席树

树上主席树在树上根据dfs序建立主席树。题目给定一棵 n 个节点的树，每个点有一个权值。有 m 个询问，每次给你 u,v,k，你需要回答 u xor last 和 v 这两个节点间第 k 小的点权。其中 last是上一个询问的答案，定义其初始为 0，即第一个询问的 u 是明文。维护主席树...

2020-07-13

0 417

hdu5919 Sequence Il 主席树

题目链接题意给出一个序列，问区间[l, r]中所有不同元素出现的第一个位置（取最左）组成的序列中的第k/2个，k是区间不同数的个数。第i个询问区间依赖于第i-1个询问的答案，所以是强制在线的。思路区间第k个，显然是主席树，和查询区间不同数的个数一样，都是相同的数只取一个，但这个是取相同数的...

2020-07-13

0 533