浅谈线段树 Segment Tree
众所周知，线段树是algo中很重要的一项！ 一.简介线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结...
主席树（可持久化线段树）
主席树前言主席树也是一种数据结构，是线段树的进阶，作用是可以保留历史版本，支持回退，就是回到之前某个未修改的状态。就像我们在写博客时如果误删了重要的内容，就可以用 Ctrl + z 撤回一次操作，也可以用Ctrl + Shift +z 还原我们撤回的操作，这就需要存下每次编辑的操作。基本原理可持久化...
Educational Codeforces Round 69 E - Culture Code (最短路计数+线段树优化建图)
题意：有n个空心物品，每个物品有外部体积outi和内部体积ini,如果ini>outj,那么j就可以套在i里面。现在我们要选出n个物品的一个子集，这个子集内的k个物品全部套在一起，且剩下的物品都无法添加到这个子集中（没有空间塞进去）。定义浪费的空间为子集中空心的部分，即ini1+(ini2−o...
[Educational Codeforces Round 81 (Rated for Div. 2)]E. Permutation Separation（线段树，思维，前缀和）
[Educational Codeforces Round 81 (Rated for Div. 2)]E. Permutation Separation（线段树，思维，前缀和）E. Permutation Separationtime limit per test2 secondsmemory l...
Codeforces 1109E. Sasha and a Very Easy Test 线段树
原文链接https://www.cnblogs.com/zhouzhendong/p/CF1109E.html题意给定一个长度为 n 的数列 a，以及一个模数 M（不一定是质数）。要求支持 q 次以下操作：区间乘单点除（保证能够整除）区间求和，最终结果对 M 取模输出。$$n,q\leq 10^5$...
zkw线段树模板题
学了zkw线段树，觉得没什么必要刷专题的吧（切不动啊）。。那先放一个模板题吧（我绝不会和你说搬了一道树状数组模板题的！！！）题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某一个数加上x2.求出某区间每一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作...
ZOJ 1610.Count the Colors-线段树(区间染色、区间更新、单点查询)-有点小坑(染色片段)
ZOJ Problem Set - 1610Count the ColorsTime Limit: 2 Seconds Memory Limit: 65536 KBPainting some colored segments on a line, some previously paint...
ZOJ 1610——Count the Colors——————【线段树区间替换、求不同颜色区间段数】
Count the ColorsTime Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %lluSubmit Status Practice ZOJ 1610DescriptionPainting some ...
HDU 1255 覆盖的面积 （扫描线 线段树 离散化 矩形面积并）
题目链接题意：中文题意。分析：纯手敲，与上一道题目很相似，但是刚开始我以为只是把cnt》=0改成cnt>=2就行了，、但是后来发现当当前加入的线段的范围之前 还有线段的时候就不行了，因为虽然现在都不等于2，但是之前的那个线段加上现在的已经覆盖2次了。 #include <iostream...
HDU 4419 Colourful Rectangle --离散化+线段树扫描线
题意： 有三种颜色的矩形n个，不同颜色的矩形重叠会生成不同的颜色，总共有R,G,B,RG,RB,GB,RGB 7种颜色，问7种颜色每种颜色的面积。解法： 很容易想到线段树扫描线求矩形面积并，但是如何维护每种颜色的长度着实让我伤透了脑筋。后来看了一位朋友的题解，才幡然醒悟。开始想到了用二进制表示颜色，...
Sereja and Array-数组操作或者线段树或树状数组
CodeForces - 315BSereja and ArrayTime Limit: 1000MS Memory Limit: 262144KB 64bit IO Format: %I64d & %I64uSubmit StatusDescriptionSereja has got an...
HDU 1611 敌兵布阵 / HRBUST 1794 敌兵布阵（线段树）
HDU 1611 敌兵布阵 / HRBUST 1794 敌兵布阵（线段树）DescriptionC国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取...
hdu 5919 Sequence II （可持久化线段树）
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5919大致题意：给你一个长度为n的序列，q个询问，每次询问是给你两个数x,y，经过与上一次的答案进行运算会得到一个区间[x,y]，假设这个区间内有k个数，对k个数第一次出现的位置进行排序取第(k+1)/2个数...
NOIP 2013 货车运输【Kruskal + 树链剖分 + 线段树 】【倍增】
NOIP 2013 货车运输【树链剖分】树链剖分题目描述 DescriptionA 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。输入描述 Inp...
线段树---no end
额，还有:区间操作,交,并,补等区间合并扫描线这些问题有空再研究吧.... 先看j2ee了.....传送门版权声明：本文为博主原创文章，未经博主允许不得转载。
1650. Billionaires(线段树）
1650简单题 线段树的单点更新 就是字符串神马的 有点小繁琐 开两个map 一个存城市 一个存名字 #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> ...
HDU 3074 (线段树+模P乘法)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3074题目大意：单点更新。维护序列乘法。mod 1000000007。解题思路：1000000007*1000000007~10^18<9*10^18(int64)所以单步模P乘法可以直接计算。(...
【BZOJ】3339: Rmq Problem & 3585: mex（线段树+特殊的技巧）
http://www.lydsy.com/JudgeOnline/problem.php?id=3585好神的题。但是！！！！！！！！！！！！！！我线段树现在要开8倍空间才能过！！！！！！！！！！这什么梗。。。。。。。。。。。。。。。。。。。。。。我思考了很久空间的问题，因为我在pushdown的时...
Codeforces Round #223 (Div. 2) E. Sereja and Brackets 线段树区间合并
题目链接：http://codeforces.com/contest/381/problem/E E. Sereja and Bracketstime limit per test1 secondmemory limit per test256 megabytesinputstandard inpu...
Codeforces Round #312 (Div. 2) E. A Simple Task 线段树+计数排序
题目链接：http://codeforces.com/problemset/problem/558/EE. A Simple Tasktime limit per test5 secondsmemory limit per test512 megabytes#### 问题描述> This ta...