BZOJ3524[Poi2014]Couriers——主席树
题目描述给一个长度为n的序列a。1≤a[i]≤n。m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。输入第一行两个数n，m。第二行n个数，a[i]。接下来m行，每行两个数l,r，表示询问[l,r]这个区间。输出m行，...
BZOJ 4539: [Hnoi2016]树 [主席树 lca]
4539: [Hnoi2016]树题意：不想写。复制模板树的子树，查询两点间距离。终于有一道会做的题了......画一画发现可以把每次复制的子树看成一个大点来建一棵树，两点的lca一定在大点的lca里然后每个大点维护一坨信息：节点编号的区间范围，到根的距离，大点对应子树的根，大点是接在了模板树里哪个...
【树上主席树】BZOJ2588-Count on a tree
【题目大意】给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。【思路】这道题迷之好写，因为思路条理太清晰了！我们每个点就是一棵线段树，维护它到根...
维护前面的position+主席树 Codeforces Round #406 (Div. 2) E
http://codeforces.com/contest/787/problem/E题目大意：给你n块，每个块都有一个颜色，定义一个k，表示在区间[l,r]中最多有k中不同的颜色。另k=1,2,3...n，问在每一种情况下，输出能划分出的最小的段落数。例如：51 3 4 3 3ans = 4, 2...
洛谷 P1972"[SDOI2009]HH的项链"（离线+树状数组 or 在线+主席树）
传送门•题意给你一个包含 n 个数的数组 $a$；有 m 此操作，每次操作求区间 [l,r] 中不同数的个数；•题解（离线+树状数组）以样例 $[1,2,3,4,3,5]$ 为例，求解区间 $[2,6]$ 的不同数的个数；按照模拟思路，肯定是从后往前查找不同数的个数；从 $6$ 开始，向前查找的结...
【BZOJ1146】[CTSC2008]网络管理Network 树状数组+DFS序+主席树
【BZOJ1146】[CTSC2008]网络管理NetworkDescriptionM公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一...
BZOJ 1146: [CTSC2008]网络管理Network( 树链剖分 + 树状数组套主席树 )
树链剖分完就成了一道主席树裸题了, 每次树链剖分找出相应区间然后用BIT+(可持久化)权值线段树就可以完成计数. 但是空间问题很严重....在修改时不必要的就不要新建, 直接修改原来的..详见代码. 时间复杂度O(N*log^3(N))--------------------------------...
BZOJ 3514: Codechef MARCH14 GERALD07加强版( LCT + 主席树 )
从左到右加边, 假如+的边e形成环, 那么记下这个环上最早加入的边_e, 当且仅当询问区间的左端点> _e加入的时间, e对答案有贡献(脑补一下). 然后一开始是N个连通块, 假如有x条边有贡献, 答案就是N-x. 用LCT维护加边, 可持久化线段树维护询问. O(NlogN)--------...
hdu 4348 To the moon （主席树 区间更新）
链接： http://acm.hdu.edu.cn/showproblem.php?pid=4348题意：4种操作：C l r c 区间[l,r]加c，时间+1Q l r 询问当前时间区间[l,r]的和H l r c 询问在时间t时，区间[l,r]的和B x 回到时间x思路：涉及历史...
Codeforces Round #276 (Div. 1) E. Sign on Fence （二分答案 主席树 区间合并）
链接：http://codeforces.com/contest/484/problem/E题意：给你n个数的，每个数代表高度；再给出m个询问，每次询问[l,r]区间内连续w个数的最大的最小值；思路：因为查询的到的值一定是输入的其中一个，那么我们可以二分答案，判断二分得到的答案是否符合，那么在这里我...
[bzoj3932][CQOI2015][任务查询系统] （主席树）
Description最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行...
bzoj 3653: 谈笑风生【dfs序+主席树】
考虑b的两种情况，一种是p的祖先，这种点有min(k,de[p]-1)个，然后每个这种b都有si[p]-1个c点可选；另一种是p的子孙，要求是在p的子树内且deep在de[p]+1~de[p]+k之间，然后一个这样的b点贡献是si[b]-1，也就是在他的子树内选c点，考虑怎么算这个，用dfs序维护，...
[主席树 强制在线]ZOJ3888 Twelves Monkeys
题意：有n年，其中m年可以乘时光机回到过去，q个询问下面m行，x,y 表示可以在y年穿越回x年, 保证y>x下面q个询问， 每个询问有个年份k问的是k年前面 有多少年可以通过一种以上($\ge 2$)方法穿越回去的， 其中时光机只能用一次比如案例如图对于询问6这一年：1.穿越回第1年 2.等...
洛谷P2633 Count on a tree 主席树
传送门:主席树解题报告:传送门!就非常板子昂$QwQ$直接dfs,在dfs的过程中建树然后就直接查询就好其实我jio得就是个主席树板子题套在树上,,,?然后具体处理也不难想?就考虑树上差分,形式大概就是tr[r]+tr[l]-tr[lca]-tr[lca.fa]然后其他做法就都和主席树的板子一样辣辣...
【BZOJ2588】Count On a Tree（主席树）
【BZOJ2588】Count On a Tree（主席树）题面题目描述给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。输入格式：第一行两个整...
【BZOJ4408】[FJOI2016]神秘数（主席树）
【BZOJ4408】[FJOI2016]神秘数（主席树）题面BZOJ洛谷题解考虑只有一次询问。我们把所有数排个序，假设当前可以表示出的最大数是\(x\)。起始\(x=0\)。依次考虑接下来的每个数\(a_i\)，如果\(a_i\le x\)，那么没有啥问题，\(x+=a_i\)。如果\(a_i=x+...
2018湘潭邀请赛C题（主席树+二分）
题目地址：https://www.icpc.camp/contests/6CP5W4knRaIRgU 比赛的时候知道这题是用主席树+二分，可是当时没有学主席树，就连有模板都不敢套，因为代码实在是太长了。 题意：给你一些数字，要求你某些区间中找到一个h-index。 每次查找h-index复杂...
HDU-6278 Just h-index（2018湘潭邀请赛 C题---主席树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6278 题目大意：给n个数，q次询问，每次询问给出一个区间[l,r]，要你求出最大的h，使得在[l,r]这个区间内满足，有h个数的值大于等于h。 题目思路：因为数据范围是1e5，如果使用暴力求解肯定是不行...
bzoj 3932 [CQOI2015]任务查询系统（主席树）
Description最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行），其优先级为Pi。同一时间可能有多个任务同时执行...
[luogu3919]可持久化数组【主席树】
链接：https://www.luogu.org/problemnew/show/P3919分析很明显我们可以用主席树来维护，所谓主席树就是可持久化线段树，能够查询历史版本而且可以实现修改操作，反正就是复制了一遍。其原理就是动态开点复制前驱版本，在复制版本中做我们需要的所有的操作，然后我们需要记录每...