[luoguP3960] 列队（动态开点线段树）传送门有splay的做法，有树状数组的做法。。。最好理解的还是线段树的做法。一开始我是这样想的，如果移动某一个人，只有当前行和最后一列会受到影响，感觉就像是个线段树，树状数组
[BZOJ4989] [Usaco2017 Feb]Why Did the Cow Cross the Road（树状数组）传送门发现就是逆序对可以树状数组求出对于旋转操作，把一个序列最后面一个数移到开头，假设另一个序列的这个数在位置x，那么对答案的贡献 (n x) + (x 1)#include <cstdio>#in
[BZOJ4994] [Usaco2017 Feb]Why Did the Cow Cross the Road III（树状数组）传送门1.每个数的左右位置预处理出来，按照左端点排序，因为左端点是从小到大的，我们只需要知道每条线段包含了多少个前面线段的右端点即可，可以用树状数组2.如果 ai < bj < bi， 也
[BZOJ3378] [Usaco2004 Open]MooFest 狂欢节（树状数组）传送门
开2个树状数组
一个存的是下标，一个存的是数量
细节。。。看标称吧，懒得说了，好气啊
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 2000
[luoguP3608] [USACO17JAN]Balanced Photo平衡的照片（树状数组 + 离散化）传送门
树状数组裸题
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100001
using namespace std;
int n, m, ans;
int
[luoguP2672] 推销员（贪心 + 树状数组 + 优先队列）传送门
贪心。。。蒟蒻证明不会。。。
每一次找最大的即可，找出一次最大的，数列会分为左右两边，左边用stl优先队列维护，右边用树状数组维护。。
（线段树超时了。。。。）
代码
[BZOJ3932] [CQOI2015]任务查询系统（主席树 || 树状数组 套 主席树 + 差分 + 离散化）传送门
看到这个题有个很暴力的想法，
可以每一个时间点都建一颗主席树，主席树上叶子节点 i 表示优先级为 i 的任务有多少个。
当 x 到 y 有个优先级为 k 的任务时，循环 x 到
[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
[luoguP3402] 最长公共子序列（DP + 离散化 + 树状数组）传送门
比P1439排列LCS问题，难那么一点点，只不过有的元素不是两个串都有，还有数据范围变大，树状数组得打离散化。
不过如果用栈+二分的话还是一样的。
——代码
1 #includ
[luoguP1972] [SDOI2009]HH的项链（莫队 || 树状数组 || 主席树）传送门
莫队基础题，适合我这种初学者。
莫队是离线算法，通常不带修改，时间复杂度为 O(n√n)
我们要先保证通过 [ l , r ] 求得 [ l , r + 1 ] , [ l , r 1 ] , [ l 1 , r ]
[luoguP2617] Dynamic Ranking（树状数组 套 主席树 + 离散化）传送门
BZOJ上是权限题，洛谷赞啊。
求区间 K 大数很简单。
但是如果修改某个数的话，那么就得把这个数及后面所建的主席树都更新一遍 nlogn，显然不行。
所以可以在外面套一个
[luoguP2184] 贪婪大陆（树状数组）传送门
用两个树状数组，cr 维护 1....x 中 r 的数量
cl 维护 1....x 中 l 的数量
求答案的时候只需要求 y 前面 被作为左端点 的个数 x 前面 被作为右端
分块来水题luogu P3374 【模板】树状数组 1
在大牛分站交能过，主站卡常。
时间复杂度为 n√n ≈ 3.5 * 108，我都不知道怎么过的。。
——代码
1 #include <cmath>
2 #include <cs
【转】关于LIS和一类可以用树状数组优化的DP 预备知识原文链接cnblogs/liurunda/p/6193690
预备知识
DP（Dynamic Programming)：一种以无后效性的状态转移为基础的算法，我们可以将其不严谨地先理解为递推。例如斐波那契
[luoguP1439] 排列LCS问题（DP + 树状数组）传送门
无重复元素的LCS问题
n2 做法不说了。
nlogn 做法 ——
因为LCS问题求的是公共子序列，顺序不影响答案，影响答案的只是两个串的元素是否相同，所以可以交换元素位置。
[BZOJ1264][AHOI2006]基因匹配Match（DP + 树状数组）传送门
有点类似LCS，可以把 a[i] 在 b 串中的位置用一个链式前向星串起来，由于链式前向星是从后往前遍历，所以可以直接搞。
状态转移方程 f[i] = max(f[j]) + 1 ( 1 <= j < i
[Vijos1512] SuperBrother打鼹鼠 （二维树状数组）传送门
直接搞就行。
注意下表re从零开始，而树状数组搞不了0，所以统一增加一个偏移量1.
（话说数据随机是什么鬼？）
1 # include <iostream>
2 # include <cstdio>
3 # incl
第k小整数（树状数组）洛谷传送门
入门难度。。
没错，但是我并不是要暴力做。
而是用树状数组来做。
先离散化，然后随便搞一搞就可以了。（晕。比暴力还慢）
如果要查找某一区间的的话可以把区间取出重
求逆序对（树状数组）洛谷传送门
虽然可以用归并排序求，但我实在记不住归并排序的代码。
还是树状数组和蔼点。
先离散化，树状数组就可以开小点，不过耗的时间多点。
——代码
1 #include <cstdi
树状数组 && 线段树树状数组
支持单点修改
#include <cstdio>
using namespace std;
int n, m;
int a[500001], c[500001];
int lowbit(int x)
int sum(int x)
return ans;
}
vo
