线段树文章列表
[BZOJ4993||4990] [Usaco2017 Feb]Why Did the Cow Cross the Road II（DP + 线段树）
传送门 f[i][j]表示当前第i个，且最后一个位置连接到j 第一维可以省去，能连边的点可以预处理出来，dp可以用线段树优化 #include cstdio#include iostream#incl...DP,线段树
[BZOJ1582] [Usaco2009 Hol]Holiday Painting 节日画画（线段树）
传送门 线段树区间修改傻题 #include cstdio#include cstring#include iostream#define N 50001#define root 1, 1, n#de...线段树
[BZOJ3545] [ONTAK2010]Peaks（线段树合并 + 离散化）
传送门 由于困难值小于等于x这个很恶心，可以离线处理，将边权，和询问时的x排序。 每到一个询问的时候，将边权小于等于x的都合并起来再询问。 。。 有重复元素的线段树合并的时间复杂度是nlog^2n #...线段树,线段树合并,离散化
[BZOJ2733] [HNOI2012]永无乡（并查集 + 线段树合并）
传送门 一看到第k大就肯定要想到什么权值线段树，主席树，平衡树之类的 然后就简单了 用并查集判断连通，每个节点建立一颗权值线段树，连通的时候直接合并即可 查询时再二分递归地查找 时间复杂度好像不是很稳...线段树,线段树合并
[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））
传送门 蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。 首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径 因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs求出最短...dfs,stl,最短路,dijkstra,并查集
[BZOJ3339] Rmq Problem（线段树）
传送门 这个题的方法好像很多啊 1.莫队暴力 2.线段树 + 离线处理 先预处理出sg[i]表示前i个数的sg值，next[i]表示i的下一位置在哪里，如果后面再没有i，那么next[i] = n +...线段树,主席树,莫队
[BZOJ4756] [Usaco2017 Jan]Promotion Counting（线段树合并）
传送门 此题很有意思，有多种解法 1.用天天爱跑步的方法，进入子树的时候ansquery，出去子树的时候ans+query，query可以用树状数组或线段树来搞 2.按dfs序建立主席树 3.线段树的...线段树,线段树合并
[luoguP2672] 推销员（贪心 + 树状数组 + 优先队列）
传送门 贪心。。。蒟蒻证明不会。。。 每一次找最大的即可，找出一次最大的，数列会分为左右两边，左边用stl优先队列维护，右边用树状数组维护。。 （线段树超时了。。。。） 代码 #include que...堆,stl,线段树,树状数组,贪心
[luoguP1816] 忠诚（st表 || 线段树）
传送门 其实我就是想练练 st表 本以为学了线段树可以省点事不学 st表 了 但是后缀数组中用 st表 貌似很方便 所以还是学了吧，反正也不难 ——代码 1 #include cstdio 2 #de...线段树,st表,模板
[BZOJ3196] [Tyvj1730] 二逼平衡树（线段树 套 Splay）
传送门 至少BZOJ过了，其他的直接弃。 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的...线段树,splay,模板,树套树
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化