内容提要
有关数据结构的例题
求逆序对数
统计每个数前面有多少比他大的数
开数组表示这个数之前0~9这些数出现了几次
动态将某个点加一，动态求前缀和
用树状数组
如果数太大了怎么办？
离散化
步骤：先把原数组排序，然后unique去重，之后按原数组lower_bound查找
Stars
由于我们是按照y的升序处理这个星星的，所以在处理的时候只需要处理x<=当前给定的x的个数就好了，用前缀和搞一搞，也是树状数组
二维偏序
一维排序
一维树状数组
Queries
直接开m个树状数组，每个树状数组中都是0/1的，每个位置a[i]表示a[i]这个数%m是否=0，是就是1，不是就是0
第i个树状数组的第j个下标表示a[i]%m是否=i
查询的时候只需要在第mod个数组查询[l,r]的前缀和就可以了
加减的操作就在原来的基础上搞一搞就行了
营业额统计
- set做法
- 线段树
我们维护0~9每个数当前的次数，某一个数前面的最大值和后面的最小值再与这个数做差，最小的就是波动值
维护一个线段树，每次求一个区间的最大值，一个区间的最小值
权值线段树，他的下标不是数组的下标，而是权值的下标
维护序列
维护两个标记
Sasha and array
考虑矩阵乘法
F为矩阵
实际上就是求[l,r]的ΣF[ai]然后乘[1 1]矩阵
区间加法其实就是对矩阵进行区间乘法
于是就变成了区间乘法，区间求和
花神游历各国
每次开根号单点修改去开，longlong范围内最多开6次就会全变成1或0
直到某个区间全部变成1或0就把他打上标记
中位数之和
每插入一个数，他的中位数之和都会发生改变
S[s1,s2,s3,s4,s0]分别表示集合中%5余1,2,3,4,0的数的和
建一棵权值线段树，以a[i]为下标，每一个节点表示在原先的大小在[l,r]中的数在长度为5的数组中长什么样子，以及大小在[l,r]中出现了多少数
大小为k的在合并时需要向后滚动k个再相加
修改：只需要单点修改
先将要处理的数字离散化。
按数字的顺序为下标建立一颗线段树。
线段树的每个节点维护如下几个值：
这一段闭区间中有几个数字
a[0..4]表示下标模5余某的数值之和
单点修改，区间查询即可完成操作。
Rmq problem
Mex表示[l,r]没有出现的最小非负整数
常在博弈论中求sg函数
离线做
扫一遍可以得到以1为左端点的mex值
每次将l右移1，更新r的值
当拿走一个数时，如果这个数只有一个，那么所有大于他的mex都会变成这个数
区间修改取min
对于所有的r，单点查询，标记下放
单次询问log(n)
只有查询没有修改
等差子序列
实质上是求是否存在三元组(i,j,k)，满足i<j<k且Ak-Aj=Aj-Ai
如果一个数出现过，就让对应位置变成1，否则为0
枚举等差中项，我们看看是否对称，如果对称就意味着都在这个数之前或者之后出现，也就是说不可能以这个数作为等差中项
- 单点修改
- 比较两段区间是否相同（等于比较两个字符串是否相同）
每个节点表示这个节点的hash值，单点修改，比较hash值