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...
Codeforces Round #337 (Div. 2) D. Vika and Segments 线段树扫描线
D. Vika and Segments题目连接：http://www.codeforces.com/contest/610/problem/DDescriptionVika has an infinite sheet of squared paper. Initially all squares ...
Codeforces Round #321 (Div. 2) E. Kefa and Watch 线段树hash
E. Kefa and WatchTime Limit: 1 SecMemory Limit: 256 MB题目连接http://codeforces.com/contest/580/problem/EDescriptionOne day Kefa the parrot was walking do...
Codeforces Round #538 (Div. 2) F 欧拉函数 + 区间修改线段树
https://codeforces.com/contest/1114/problem/F欧拉函数 + 区间更新线段树题意对一个序列(n<=4e5,a[i]<=300)两种操作:1. 将a[l,r]的数字乘以x(x<=300)2. 求\(\varphi(\prod_{i=l}^ra...
Codeforces Round #250 (Div. 1) D. The Child and Sequence（线段树）
D. The Child and Sequencetime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAt the children's day, ...
《完全版线段树》——notonlysuccess
转载自：NotOnlySuccess的博客【完全版】线段树很早前写的那篇线段树专辑至今一直是本博客阅读点击量最大的一片文章,当时觉得挺自豪的,还去pku打广告,但是现在我自己都不太好意思去看那篇文章了,觉得当时的代码风格实在是太丑了,很多线段树的初学者可能就是看着这篇文章来练习的,如果不小心被我培养...
[BZOJ4592][SHOI2015]脑洞治疗仪(线段树)
线段树基础操作题，唯一需要思考下的是将区间的前k个0覆盖为1。线段树上二分，先递归到左子树覆盖，回溯时返回还剩多少个0未被覆盖，在根据这个信息递归到右子树。注意特判k=0的情况。要维护的信息有：区间左边最长0连续段，右边最长0连续段，区间整体最长0连续段，区间内1的个数，以及一个记录是否被区间覆盖的...
HDU 1828 Picture (线段树+扫描线)(周长并)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1828给你n个矩形，让你求出总的周长。类似面积并，面积并是扫描一次，周长并是扫描了两次，x轴一次，y轴一次。每次加起来的无非都是新加的边(flag为1)或者是新减的边(flag为-1)，即加起来的是此时的...
Codeforces 588E. A Simple Task (线段树+计数排序思想)
题目链接：http://codeforces.com/contest/558/problem/E题意：有一串字符串，有两个操作：1操作是将l到r的字符串升序排序，0操作是降序排序。题解：建立26棵线段树，类似计数排序思想。 #include <bits/stdc++.h> using n...
BZOJ 5249: [2018多省省队联测]IIIDX(贪心 + 线段树)
题意这一天，\(\mathrm{Konano}\) 接到了一个任务，他需要给正在制作中的游戏 \(\mathrm{《IIIDX》}\) 安排曲目 的解锁顺序。游戏内共有\(n\) 首曲目，每首曲目都会有一个难度 \(d\) ，游戏内第 \(i\) 首曲目会在玩家 Pass 第 \(\lfloor \...
【arc073e】Ball Coloring（线段树，贪心）
【arc073e】Ball Coloring（线段树，贪心）题面AtCoder洛谷题解大型翻车现场，菊队完美压中男神的模拟题首先钦定全局最小值为红色，剩下的袋子按照其中较大值排序。枚举前面连续的一段是什么颜色，那么此时我们就知道了两种颜色的\(max\)，那么只需要考虑蓝色的\(min\)就好了。答...
[YNOI2017][bzoj4811][luogu3613] 由乃的OJ/睡觉困难综合症 [压位+树链剖分+线段树]
题面BZOJ题面，比较不清晰Luogu题面，写的比较清楚思路原题目我们先看这道题的原题目NOI2014起床困难综合症的确就是上树的带修改版本那么我们先来解决这个原版的序列上单次询问二进制的这些操作，我们把操作数和符号一起（比如xor 7,and 31）挪动的话，答案是会改变的，不同符号之间不满足交换...
BZOJ4530 BJOI2014大融合（线段树合并+并查集+dfs序）
易知所求的是两棵子树大小的乘积。先建出最后所得到的树，求出dfs序和子树大小。之后考虑如何在动态加边过程中维护子树大小。这个可以用树剖比较简单的实现，但还有一种更快更优美的做法就是线段树合并。对每个点开权值线段树，维护当前时刻这棵点为根的子树中，已经和其相连的点的dfs序情况。合并时直接将表示两棵子...
hdu 1540 Tunnel Warfare (区间线段树（模板）)
http://acm.hdu.edu.cn/showproblem.php?pid=1540Tunnel WarfareTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total ...
bzoj 1067: [SCOI2007]降雨量 (离散化+线段树)
链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1067思路： 毒瘤题，写的自闭，改了一晚上，注意要理清题目的逻辑 x小于等于y,x,y之间的数严格小于x，不能等于；分类讨论懒得写的，很简单的分类讨论。实现代码：#include<bits...
线段树入门&lazy思想
线段树将区间分成若干个子区间，子区间又继续分，直到区间为一个点（区间左值等于右值）对于父区间[a,b]，其子区间为[a,(a+b)/2]和[(a+b)/2+1,b] 用于求区间的值，如区间最值、区间的和等。代码实现中，约定结点下标从1开始，所以某结点下标为x，那么左儿子下标为2x，右儿子下标为2x+...
nowcoder 211E - 位运算？位运算！ - [二进制线段树][与或线段树]
题目链接：https://www.nowcoder.com/acm/contest/211/E题目描述请实现一个数据结构支持以下操作：区间循环左右移，区间与，区间或，区间求和。输入描述:第一行n,q表示数列长度及操作次数。第二行n个数表示初始序列。接下来q行表示操作。操作格式如下：一行表示一个操作。...
Codeforces Round #337 (Div. 2) D. Vika and Segments 线段树 矩阵面积并
D. Vika and SegmentsVika has an infinite sheet of squared paper. Initially all squares are white. She introduced a two-dimensional coordinate system o...
数据结构1 线段树查询一个区间的O(log N) 复杂度的证明
线段树属于二叉树, 其核心特征就是支持区间加法，这样就可以把任意待查询的区间$[L, R]$分解到线段树的节点上去，再把这些节点的信息合并起来从而得到区间$[L,R]$的信息。下面证明在线段树上查询任意区间的复杂度是$O(\log{N})$的，$N$是区间总长度。由于访问一个节点（即获得一个节点内与...