BZOJ_3207_花神的嘲讽计划1_(Hash+主席树)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=3207给出一个长度为\(n\)的串,以及\(m\)个长度为\(k\)的串,求每个长度为\(k\)的串在原串\([x,y]\)区间是否出现过.分析这道题要求对比长度为\(k\)的串,于是我们把这些串的...
【BZOJ5304】[HAOI2018]字串覆盖（后缀数组，主席树，倍增）
【BZOJ5304】[HAOI2018]字串覆盖（后缀数组，主席树，倍增）题面BZOJ洛谷题解贪心的想法是从左往右，能选就选。这个显然是正确的。题目的数据范围很好的说明了要对于询问分开进行处理。先考虑询问的模板串长比较大的情况。那么只需要每次找到一个范围内的最小位置然后接着暴力跳就可以了。这个这个过...
主席树+启发式合并（LT） BZOJ3123
好久没做题了，写道SBT又RE又T查询：主席树裸题。修改：对于两个树合并重建小的树。注意fa[x][i]重新计算时要清空#include<cstdio>#include<cctype>#include<cstring>#include<algorithm&g...
HDU 4348 To the moon（主席树区间修改）
题意给你一个区间，支持如下操作：在一段区间内加上一个值，并生成一个历史版本查询某个版本下一段区间内的和回到一个历史版本上并舍弃之后的版本做法这就是主席树区间修改裸题啦QwQ上一篇博客我讲了主席树可以资瓷单点修改，那么区间修改资不资瓷呢？那当然是资瓷的啦。就像一般的线段树一样，主席树的一个内部节点也可...
SPOJ DQUERY 求区间内不同数的个数 主席树
这题跟HDU3333差不多吧。离线的做法很简单，不再说了以前做过。主席树的做法就比较暴力了。。什么是主席树呢。。其实是某种称号。在该题中的体现是可持久化的线段树。对于一个数如果以前没出现过就插入到主席树中否则就删除以前那个。再插入主席树。注意，所有的更新和删除都是建立了新的节点来保持其历史状态的。。...
CF484E. Sign on Fence（主席树+二分）
CF484E. Sign on Fence CF484E. Sign on Fence 题目大意 给你n块木板，每块木板有高度Hi，q次询问每次询问在[l,r]区间中最大的长度为w的区间的最小值。 思路 将木板从大到小排序，建动态开点线段树维护区间最长子段，于是就可以二分高...
5333. 【NOIP2017提高A组模拟8.23】大新闻 主席树/树套树
数据结构学傻选手。。。 题意：给出一个序列，每次可以在开头添加或删除，以及查询区间k大。 一看添加无脑树套树，成功fst，事实上只要一个主席树就可以了，倒过来每次覆盖掉。。 #include<iostream>#include<cstdio>#include<a...
Count on a tree SPOJ - COT （主席树，LCA）
You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.We will ask you to perform the following o...
BZOJ 4539: [Hnoi2016]树 [主席树 lca]
4539: [Hnoi2016]树题意：不想写。复制模板树的子树，查询两点间距离。终于有一道会做的题了......画一画发现可以把每次复制的子树看成一个大点来建一棵树，两点的lca一定在大点的lca里然后每个大点维护一坨信息：节点编号的区间范围，到根的距离，大点对应子树的根，大点是接在了模板树里哪个...
UOJ#218. 【UNR #1】火车管理 线段树 主席树
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ218.html题解如果我们可以知道每次弹出栈之后新的栈顶是什么，那么我们就可以在一棵区间覆盖、区间求和的线段树上完成这个问题。于是本题的重点转到了如何求新的栈顶。考虑用一个主席树维护一下每一个时刻每一个位置...
【主席树维护mex】 【SG函数递推】 Problem H. Cups and Beans 2017.8.11
Problem H. Cups and Beans 2017.8.11原题：There are N cups numbered 0 through N − 1. For each i(1 ≤ i ≤ N − 1), the cup i contains Ai beans,and this cup i...
P1972 [SDOI2009]HH的项链[离线+树状数组/主席树/分块/模拟]
题目背景无题目描述HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为...
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]的值，改变后，程序还能针对...
[bzoj3295][Cqoi2011]动态逆序对_主席树
动态逆序对bzoj-3295Cqoi-2011题目大意：题目链接。注释：略。想法：直接建立主席树。由于是一个一个删除，所以我们先拿建立好的root[n]的权值线段树先把总逆序对求出来，接着没删一个数，我们就删掉这个点作为右端点的逆序对和作为左端点的逆序对。这个过程我们直接模拟树状数组。我们叫它阉割树...
BZOJ 2743: [HEOI2012]采花 [树状数组 | 主席树]
题意:查询区间中出现次数$>2$的颜色个数一眼主席树，区间中$l\lelast[i]\ler$的个数减去$l\lelast[last[i]]\ler$的个数，搞两颗主席树来做然后就T了因为bzoj上数据是1e6....还是离线树状数组吧....#include<iostream>#...
HDU 4251 --- 主席树（划分树是正解）
题意：查询区间中位数思路：模板题，相当于区间第K大的数，主席树可以水过，但划分树是正解。但还没搞明白划分树，先上模板#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#i...
bzoj 3489 A simple rmq problem —— 主席树套线段树
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3489题解：http://www.itdaan.com/blog/2017/11/24/9bc46b690756fe252e17fc3ca90aa01.html在我挣扎一下午时Narh早就A了....
bzoj3932 / P3168 [CQOI2015]任务查询系统（主席树+差分）
P3168[CQOI2015]任务查询系统看到第k小，就是主席树辣对于每一段任务(a,b,k)，在版本a的主席树+k，版本b+1的主席树-k同一时间可能有多次修改，所以开个vector存操作，再开个数组ti[p]保存时间点p最终的版本号注意longlong#include<iostream&g...
洛谷$P$3168 任务查询系统 $[CQOI2015]$ 主席树
正解:主席树解题报告:传送门!首先考虑如果是单点修改,那就是个线段树板子嘛$QwQ$然后现在是区间修改,对于区间修改,显然就考虑差分下,就变成单点修改辣$QwQ$同时单点查询前$k$小也就变成了区间查询前$k$小于是就主席树套下就好$QwQ$详细点儿说下趴$QwQ$.先考虑如果查询的不是前$k$小,...
【BZOJ5495】[十二省联考2019]异或粽子（主席树，贪心）
【BZOJ5495】[十二省联考2019]异或粽子（主席树，贪心）题面BZOJ洛谷题解这不是送分题吗。。。转异或前缀和，构建可持久化\(Trie\)。然后拿一个堆维护每次的最大值，每次如果取了一个数，就把它再在\(Trie\)树上查一次新建一个元素丢回堆里就行了。#include<iostre...