标签为 [主席树] 的文章

BZOJ3123 森林

题目大意 给一个森林,森林有n个节点m条边。 现在有两种操作: Q x y k 表示询问x-y这条链上点权的第k小。保证x,y在同一个连通块里。 L x y 表示链接x,y两点。保证x,y在不同的连通块里。 总共有T次操作,要求强制在线,last表示上一次的答案,每次x,y,k都要异或last.last初始为0. 对于所有的数据,n,m,T<=8*10^4 . Solution 因为有连接两个点的操作,所以xqj大神一眼就报出了题解:LCT。 可是我这个菜鸡怎么都想不出LCT的做法。因为还要询问点权的第k小,还要在splay上套一棵线段树。用树套树维护LCT,反正我是不会。但我相 ......

BZOJ2653 middle(主席树+二分答案)

题目大意 一个长度为n的序列a,设其排过序(从大到小)之后为b,其中位数定义为b[n/2] 给定n个数有q个询问,每次询问中位数最大的连续一段的数[l…r],满足a<=l<=b,c<=r<=d。输出最大中位数。 n,q<=100000 Solution 如果给定一个数x,怎样快速判断比较大于x的数的个数和小于x的数的个数?可以把小于x的数的定为-1,大于等于x的数定为1,求所有数的和。 若和>=0,说明大于等于它的数较多,中位数应>=x,否则中位数<=x,如果能快速知道这个1/-1数列,就可以二分中位数。实现时只要比较合法区间的最大和。若 ......

SPOJ3267 D-query

题目大意 给你一串数,每次询问区间中不重复的数的个数。 Solution 对于这种问题,很想用莫队水过。关于莫队算法,请参考PhoenixGS的一篇博客。莫队算法 但如果询问强制在线的话,就不能用莫队做了。如果我们可以从每个点为结束点,都维护一棵线段树的话,就可以做到查询了。 暴力建树肯定不行,但可以发现,右端点从r变成r+1时,只有最多两个点发生了改变。所以只要改变这两个节点,并将线段树改以前的状态记下来。不在原线段树上修改,而是新开几个节点修改。说白了,就是维护一棵可持久化线段树,用主席树就可以。具体实现时和 ......