bzoj1901 [ Zju2112 ] --树状数组套主席树
树状数组套主席树模板题。。。 题目大意： 给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对...
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思路：涉及历史...
高级数据结构(树状数组套主席树)：ZOJ 2112 Dynamic Rankings
Dynamic RankingsTime Limit: 10 Seconds Memory Limit: 32768 KBThe Company Dynamic Rankings has developed a new kind of computer that is no longe...
洛谷P3168 [CQOI2015]任务查询系统 [主席树，差分]
题目传送门任务查询系统题目描述最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(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序维护，...
[JSOI2018]列队（主席树）
跟上次那道列队不一样，但都是九条可怜。。。（吉老师太强了）在主席树上统计答案，因为值域只有\(10^6\)甚至不用离散化。。。\(Code\Below:\)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constin...
洛谷P2633 Count on a tree 主席树
传送门:主席树解题报告:传送门!就非常板子昂$QwQ$直接dfs,在dfs的过程中建树然后就直接查询就好其实我jio得就是个主席树板子题套在树上,,,?然后具体处理也不难想?就考虑树上差分,形式大概就是tr[r]+tr[l]-tr[lca]-tr[lca.fa]然后其他做法就都和主席树的板子一样辣辣...
BZOJ3295: [Cqoi2011]动态逆序对（树状数组套主席树）
3295:[Cqoi2011]动态逆序对TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 7465 Solved: 2662[Submit][Status][Discuss]Description对于序列A，它的逆序对数定义为满足i<j，且Ai>A...
【bzoj 十连测】[noip2016十连测第三场]Problem C: 序列（静态主席树）
ProblemC:[noip2016十连测第三场]序列TimeLimit: 10Sec MemoryLimit: 256MBSubmit: 78 Solved: 32[Submit][Status][WebBoard]Description小A把自己之前得到的序列展示给了小B，不过这一次，他并不...
2018.07.01 BZOJ3295: [Cqoi2011]动态逆序对（带修主席树）
3295:[Cqoi2011]动态逆序对**TimeLimit:10SecMemoryLimit:128MBDescription对于序列A，它的逆序对数定义为满足i<j"role="presentation"style="position:relative;">i<ji&...
[bzoj3295][Cqoi2011]动态逆序对_主席树
动态逆序对bzoj-3295Cqoi-2011题目大意：题目链接。注释：略。想法：直接建立主席树。由于是一个一个删除，所以我们先拿建立好的root[n]的权值线段树先把总逆序对求出来，接着没删一个数，我们就删掉这个点作为右端点的逆序对和作为左端点的逆序对。这个过程我们直接模拟树状数组。我们叫它阉割树...
[BZOJ3207] 花神的嘲讽计划Ⅰ (主席树)
Description背景花神是神，一大癖好就是嘲讽大J，举例如下：“哎你傻不傻的！【hqz：大笨J】”“这道题又被J屎过了！！”“J这程序怎么跑这么快！J要逆袭了！”……描述这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录：1.“J你在讲什么！”“我...
BZOJ4299 Codechef FRBSUM（主席树）
感觉非常不可做，于是考虑有什么奇怪的性质。先考虑怎么求子集和mex。将数从小到大排序，假设已经凑出了0~n的所有数，如果下一个数>n+1显然mex就是n+1了，否则若其为x则可以凑出1~n+x所有数。对于区间查询，建棵主席树即可，每次查询权值线段树上lastn+2~n+1的区间，用区间和更新n...
主席树 || 可持久化线段树 || BZOJ 3653: 谈笑风生 || Luogu P3899 [湖南集训]谈笑风生
题面：P3899 [湖南集训]谈笑风生题解：我很喜欢这道题。因为A是给定的，所以实质是求二元组的个数。我们以A（即给定的P）作为基点寻找答案，那么情况分两类。一种是B为A的父亲，另一种是A为B的父亲。第一种情况很好处理，写法见代码，懒得讲，反正很简单的。第二种情况的话，按Dfs序建主席树，用主席树维...
BZOJ 2743: [HEOI2012]采花 [树状数组 | 主席树]
题意:查询区间中出现次数$>2$的颜色个数一眼主席树，区间中$l\lelast[i]\ler$的个数减去$l\lelast[last[i]]\ler$的个数，搞两颗主席树来做然后就T了因为bzoj上数据是1e6....还是离线树状数组吧....#include<iostream>#...
BZOJ_2223_[Coci 2009]PATULJCI_主席树
BZOJ_2223_[Coci2009]PATULJCI_主席树DescriptionInput1031212123233812131415252669710Outputnoyes1noyes1noyes2noyes3 区间众数，可以用主席树求。查询时判断那边大走哪边。 代码：#include<...
HDU 3333 & 主席树
题意:balabalaSOL:这题用主席树怎么做呢...貌似一模一样...一个一个建n棵的线段树.先把上一棵树复制下来,当a[i]出现过,就把这棵树里的那个位置去掉------一模一样的思维...就是用空间换时间达到在线罢了...然而他的在线比我的离线还快是什么鬼...线段树果然比树状数组慢不止一点...
HDU 4251 --- 主席树（划分树是正解）
题意：查询区间中位数思路：模板题，相当于区间第K大的数，主席树可以水过，但划分树是正解。但还没搞明白划分树，先上模板#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#i...
Codeforces 893F（主席树+dfs序）
在子树内和距离不超过k是一个二维限制，容易想到主席树，但主席树显然没法查最小值，因为不满足区间可减。kdtree和二维线段树可以干这事，但肯定会T飞。但事实上我们的问题有一个特殊性：对某个点x，查询其子树中的depth[x]~depth[x]+y和0~depth[x]+y这两种深度区间实际上是相同的...