Category Archives: 主席树

CodeForces 484E Sign on Fence (二分,主席树)

给出一个由n块木板构成的栅栏,每块木板的高度hi,有m个询问,l, r, w,计算第l块到第r块栅栏之间能放长 …

CCPC长春I题 (主席树,水)

n个数字,m个询问,询问[l, r],k表示[l, r]区间 不同数字的个数,将每个不同数字第一次出现的次数记 …

2016 Multi-University Training Contest 5

1001 – ATM Mechine 一个有在ATM机偷钱,他只知道钱的上限是K,他每次可以选择取 …

51nod 1249 近似有序区间 (单调栈,主席树)

一个1到N的排列S,S的近似有序的区间满足如下性质: 1、是S的连续子序列。 2、第一个数是最小的。 3、最后 …

HDU 5678 ztr loves trees (可持久化线段树)

给出n个点的树,每个点有一个权值,有m个询问,每个询问计算以rt为根的子树所有节点权值的中位数(偶数个时要去平 …

ZOJ 2112 Dynamic Rankings (树状数组套可持久化线段树)

计算区间第k大数,存在动态修改区间某个点的数. 用树状数组套上一个主席树,主席数维护的是区间不同数子的个数,用 …

SPOJ TTM To the moon (主席树,区间更新)

给出n个数字,每次对其进行操作,支持时间回滚 1. C l r d 将区间l,r加上d,同时时间+1 2. Q …

SPOJ D-query (主席树)

求区间不同数的个数。 好好理解下利用历史版本解决问题的办法,对于区间询问[l, r],只要处理历史版本root …

poj 2104 K-th Number (可持久化线段树/主席树)

静态求区间第k大。 主席树入门题。 首先讲下个人对主席树的理解,主席树 <==> 可持久化线段树, …