线段树 HDU-1754 I Hate It
附上原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754Problem Description很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，...
HDU 2795 Billboard（线段树的另类应用）
BillboardTime Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 19225 Accepted Submission(s): 804...
线段树(区间合并) LA 3989 "Ray, Pass me the dishes!"
题目传送门题意：动态最大连续子序列和，静态的题目分析：nlogn的归并思想。线段树维护结点的三个信息，最大前缀和，最大后缀和，该区间的最大和的两个端点，然后答案是三个的better。书上用pair保存端点，用自带的<来得到最优。#include <bits/stdc++.h>usi...
hiho一下21周 线段树的区间修改 离散化
离散化时间限制:10000ms单点时限:1000ms内存限制:256MB描述小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看...
HDU 3642 - Get The Treasury - [加强版扫描线+线段树]
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3642Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Problem Descriptio...
【BZOJ3958】[WF2011]Mummy Madness 二分+扫描线+线段树
【BZOJ3958】[WF2011]Mummy MadnessDescription在2011年ACM-ICPC World Finals上的一次游览中，你碰到了一个埃及古墓。不幸的是，你打开了坟墓之后，才发现这是一个坏主意：突然之间，原本空无一物的沙漠上已经爬满了暴躁的木乃伊。（如果你也沉睡几千年...
P3722 [AH2017/HNOI2017]影魔（单调栈+扫描线+线段树）
题面传送门首先我们把这两个贡献翻译成人话：区间 \([l,r]\) 产生 \(p_1\) 的贡献当且仅当 \(a_l,a_r\) 分别为区间 \([l,r]\) 的最大值和次大值。区间 \([l,r]\) 产生 \(p_2\) 的贡献当且仅当 \(a_l\) 为区间 \([l,r]\) 的最大值且 ...
【bzoj4491】我也不知道题目名字是什么 离线扫描线+线段树
题目描述给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串输入第一行n，表示A数组有多少元素接下来一行为n个整数A[i]接下来一个整数Q，表示询问数量接下来Q行，每行2个整数l，r输出对于每个询问，求[l,r]内最长子串，使得该子串为不上升子串或不下降子...
【BZOJ-3673&3674】可持久化并查集 可持久化线段树 + 并查集
3673: 可持久化并查集 by zkyTime Limit: 5 Sec Memory Limit: 128 MBSubmit: 1878 Solved: 846[Submit][Status][Discuss]Descriptionn个集合 m个操作操作：1 a b 合并a,b所在集合2 k...
CF719E（线段树+矩阵快速幂）
题意：给你一个数列a，a[i]表示斐波那契数列的下标为a[i]，求区间对应斐波那契数列数字的和，还要求能够维护对区间内所有下标加d的操作分析：线段树线段树的每个节点表示（f[i],f[i-1]）这个数组因为矩阵的可加性，所以可以进行lazy操作我最开始的想法是每个节点lazy表示该区间下标加了多少，...
【BZOJ-3779】重组病毒 LinkCutTree + 线段树 + DFS序
3779: 重组病毒Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 224 Solved: 95[Submit][Status][Discuss]Description黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。...
PYOJ 44. 【HNSDFZ2016 #6】可持久化线段树
#44. 【HNSDFZ2016 #6】可持久化线段树统计描述提交自定义测试题目描述现有一序列 AA。您需要写一棵可持久化线段树，以实现如下操作：A v p x：对于版本v的序列，给 ApAp 增加 xx.Q v l r：对于版本v的序列，询问 A[l,r]A[l,r] 的区间和。C v：拷贝一份版...
Gym 102091K The Stream of Corning 2【线段树】
<题目链接>题目大意：进行两种操作：1.给定一个数的出现时间、价值、消失时间；2.进行一次询问，问你当前时间，第K大的数的价值。解题分析：采用离线集中处理，将每个数的出现时间和它的消失时间分组存下，并且存下所有的询问。然后就是依次进行所有询问，将这些询问时间点之前的点插入，将已经消失的点...
Codeforces446C DZY Loves Fibonacci Numbers(线段树 or 分块？)
第一次看到段更斐波那契数列的，整个人都不会好了。事后看了题解才明白了一些。首先利用二次剩余的知识，以及一些数列递推式子有下面的至于怎么解出x^2==5(mod 10^9+9)，我就不知道了，但是要用的时候可以枚举一下，把这些参数求出来之后就题目就可以转化为维护等比数列。由于前面的常数可以最后乘，所以...
[SNOI2017]炸弹[线段树优化建图]
[SNOI2017]炸弹线段树优化建图，然后跑一边tarjan把点全部缩起来，炸一次肯定是有连锁反应的所以整个连通块都一样…于是就可以发现有些是只有单向边的不能忘记更新,没了。#include <bits/stdc++.h>#define ls(x) ch[x][0]#define rs...
BZOJ5017 [SNOI2017]炸弹 - 线段树优化建图+Tarjan
Solution一个点向一个区间内的所有点连边， 可以用线段树优化建图来优化 ： 前置技能传送门然后就得到一个有向图， 一个联通块内的炸弹可以互相引爆， 所以进行缩点变成$DAG$然后拓扑排序。 由于一次引爆的炸弹 一定是一个连续的区间内， 所以只需要记录左右边界， 并将左右边界转移给能到达它的联通...
BZOJ5017 [Snoi2017]炸弹[线段树优化建边+scc缩点+DAG上DP/线性递推]
方法一：朴素思路：果断建图，每次二分出一个区间然后要向这个区间每个点连有向边，然后一个环的话是可以互相引爆的，缩点之后就是一个DAG，求每个点出发有多少可达点。然后注意两个问题：上述建边显然$n^2$爆炸。因为是区间建边，所以用线段树建边优化，不过这题比较特殊，只是点向区间连边，分析线段树建边原理，...
模拟赛T2 线段树优化建图+tarjan+拓扑排序
然而这只是 70pts 的部分分，考场上没想到满分怎么做（现在也不会）code:#include <cstdio>#include <string>#include <stack>#include <queue>#include <cstring...
炸弹:线段树优化建边+tarjan缩点+建反边+跑拓扑
这道题我做了有半个月了...终于A了...有图为证一句话题解:二分LR线段树优化建边+tarjan缩点+建反边+跑拓扑统计答案首先我们根据题意,判断出来要炸弹可以连着炸,就是这个炸弹能炸到的可以是由它能炸到的其他炸弹来炸到.也就是说具有拓扑性.(a->b,b->c==a->c)所以...
HDU1394(线段树||树状数组)
Minimum Inversion NumberTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 17870 Accepted Subm...