[luoguP3960] 列队（动态开点线段树）传送门有splay的做法，有树状数组的做法。。。最好理解的还是线段树的做法。一开始我是这样想的，如果移动某一个人，只有当前行和最后一列会受到影响，感觉就像是个线段树，树状数组
[luoguP2221] [HAOI2012]高速公路（线段树）传送门考虑每一段对答案的贡献用每一段的左端点来表示当前这一段，那么区间就变成了[1,n1]如果询问区间[l,r]，其中一个点的位置为x，则它对答案的贡献为(xl)*(rx)*s[x]（s[x]为这一
[BZOJ3339] Rmq Problem（线段树）传送门
这个题的方法好像很多啊
1.莫队暴力
2.线段树 + 离线处理
先预处理出sg[i]表示前i个数的sg值，next[i]表示i的下一位置在哪里，如果后面再没有i，那么next[i] = n + 1
然
[BZOJ4993||4990] [Usaco2017 Feb]Why Did the Cow Cross the Road II（DP + 线段树）传送门f[i][j]表示当前第i个，且最后一个位置连接到j第一维可以省去，能连边的点可以预处理出来，dp可以用线段树优化#include <cstdio>#include <iostream>#include <algorithm>#
[BZOJ3545] [ONTAK2010]Peaks（线段树合并 + 离散化）传送门
由于困难值小于等于x这个很恶心，可以离线处理，将边权，和询问时的x排序。
每到一个询问的时候，将边权小于等于x的都合并起来再询问。
。。
有重复元素的线段树合并的时
[BZOJ1582] [Usaco2009 Hol]Holiday Painting 节日画画（线段树）传送门
线段树区间修改傻题
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 50001
#define root 1, 1, n
#define ls now << 1, l, mid
#define
[BZOJ2733] [HNOI2012]永无乡（并查集 + 线段树合并）传送门
一看到第k大就肯定要想到什么权值线段树，主席树，平衡树之类的
然后就简单了
用并查集判断连通，每个节点建立一颗权值线段树，连通的时候直接合并即可
查询时再二分递归
[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））传送门
蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。
首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径
因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs
[BZOJ4756] [Usaco2017 Jan]Promotion Counting（线段树合并）传送门
此题很有意思，有多种解法
1.用天天爱跑步的方法，进入子树的时候ansquery，出去子树的时候ans+query，query可以用树状数组或线段树来搞
2.按dfs序建立主席树
3.线段树的
[luoguP2672] 推销员（贪心 + 树状数组 + 优先队列）传送门
贪心。。。蒟蒻证明不会。。。
每一次找最大的即可，找出一次最大的，数列会分为左右两边，左边用stl优先队列维护，右边用树状数组维护。。
（线段树超时了。。。。）
代码
[luoguP1816] 忠诚（st表 || 线段树）传送门
其实我就是想练练 st表
本以为学了线段树可以省点事不学 st表 了
但是后缀数组中用 st表 貌似很方便
所以还是学了吧，反正也不难
——代码
1 #include <cstdio>
[BZOJ3196] [Tyvj1730] 二逼平衡树（线段树 套 Splay）传送门
至少BZOJ过了，其他的直接弃。
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修
[luoguP1970] 花匠（DP）传送门
n2过不了惨啊
70分做法
f[i][0] 表示第 i 个作为高的，的最优解
f[i][0] 表示第 i 个作为低的，的最优解
（且第 i 个一定选）
那么
f[i+1][1]=max(f[j][0])+1,i>=j>=1,h[j
[luoguP1440] 求m区间内的最小值（单调队列 || 线段树）传送门
这种水题没必要搞线段树了，单调队列就行啊。
——代码
1 #include <cstdio>
2
3 const int MAXN = 2000001;
4 int n, m, h = 1, t = 1;
5 int a[MAXN], q
[luoguP2146] 软件包管理器（树链剖分）传送门
看着很吓人，其实就是个树链剖分模板。
可支持操作：
1.将节点 x 到 根 的路径上的值都变成 1
2.将以节点 x 为根的子树的值都变成 0
1A爽~
——代码
1 #include
[luoguP2982][USACO10FEB]慢下来Slowing down（dfs序 + 线段树）传送门
这个题显然可以用树链剖分做。
然而线段树也能做。
每个点都对它的子树有贡献，所以先求一边 dfs序，然后直接在 dfs序 中搞 线段树 就行。
——代码
1 #include <
分块来水题luogu P3374 【模板】树状数组 1
在大牛分站交能过，主站卡常。
时间复杂度为 n√n ≈ 3.5 * 108，我都不知道怎么过的。。
——代码
1 #include <cmath>
2 #include <cs
[luoguP3606] [USACO17JAN]Building a Tall Barn建谷仓（贪心 + 线段树）传送门
把线段都读进来然后排序，先按右端点为第一关键字从小到大排序，后按左端点为第二关键字从小到大排序。
注意不能先按左端点后按右端点排序，否则会出现大包小的情况，如下
[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）传送门
树链剖分固然可以搞。
但还有另一种做法，可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。
而给以某一节点 x 为根的子树增
[luoguP1198][JSOI2008] 最大数（线段树 || 单调栈）题目传送门
1.线段树
线段树可以搞。
不过慢的要死1300+ms
1 #include <cstdio>
2 #include <iostream>
3
4 using namespace std;
5
6 int m, n, pos, ql, qr
【模板】树链剖分[ZJOI2008]树的统计
洛谷传送门
第一遍树链剖分，打的很难受。
其中拉闸了，检查真是费劲。
树链剖分是什么？
树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分
树状数组 && 线段树树状数组
支持单点修改
#include <cstdio>
using namespace std;
int n, m;
int a[500001], c[500001];
int lowbit(int x)
int sum(int x)
return ans;
}
vo
