前置知识（提高）
基础方法
-
前缀和
-
差分
- 区间加同一个数，查询单点
- 区间加等差数列，查询单点
- 区间加同一个数，查询区间和
-
离散化
-
离线
-
二分
-
倍增
-
双指针
-
标记永久化
-
反转时间：插入变删除，删除变插入
数据结构
- 线段树
线段树（一种分治树,取序列中点进行分治，深度约\(logn\)）
相关问题：
- 线段树上二分（单侧二分，双侧二分）
把当前 k 与左儿子比较
- 动态开点线段树
不建树，修改操作用到的点再创建，查询操作用到了，直接计算出来
适用于无法离散化的情况
空间 \(O(nlogw)\)
- 树状数组
树状数组（BIT，自底而上把线段树的右儿子删除）。一个节点\(t[i]\)管辖\(a[i-lowbit(i)+1,..i]\)
相当于一半的线段树，更局限，但是更短更快。
- ST表
RMQ问题，\(O(nlogn)\)初始化，\(O(1)\)查询。
- 单调队列
单调队列（常结合双指针使用，而不一定要二分）。
- 单调栈
单调栈（给一个序列\(a\)，对每个下标\(i\)，求出\(a_i\)之后第一个大于\(a_i\)的元素的下标，即以\(a_i\)为最大值的极大区间。这个用单调栈可以\(O(n)\)求出。
- 并查集
并查集（DSU），路径压缩后时间\(O(logn)\)，尽管按秩合并也是这个复杂度，但是常数大。另有带权并查集，可维护点权差的传递，可以利用取模后的权值差来分类。同时并查集可以扩域，维护复杂的信息。
其他
LCA：
- O(n)~O(nlogn) : 树剖
- O(nlogn)~O(1) : 括号序->RMQ
DFS序：方便地维护子树信息
平衡树相关
名次树（Treap）
- 插入\(x\)
- 删除\(x\)
- 查询小于\(x\)的数的个数
- 查询第\(k\)小的数
\(1\le m, x\le 2\times 10^5\)
二叉搜索树（BST）
中序遍历排列关键字得到的序列单调不降的一种树。
平衡树（平衡二叉搜索树）
是深度\(O(logn)\)的二叉搜索树（并不严格\(logn\)，但是近似or期望\(logn\)）
Splay、Treap etc都是平衡树
Treap Code
namespace Treap {
struct Node {
int ls, rs;
int v, k, c, s;
}t[MAXN];
int cnt, rt;
void upd(int x) {t[x].s = t[t[x].ls].s + t[t[x].rs].s + t[x].c;}
void lturn(int& x) {int s = t[x].rs; t[x].rs = t[s].ls; upd(x); t[s].ls = x; upd(s); x = s;}
void rturn(int& x) {int s = t[x].ls; t[x].ls = t[s].rs; upd(x); t[s].rs = x; upd(s); x = s;}
void ins(int v, int& x) {
if(!x) t[x = ++cnt] = (Node){0, 0, v, rand(), 1, 1};
else if(t[x].v == v) t[x].c++, upd(x);
else if(t[x].v > v)
ins(v, t[x].ls), t[t[x].ls].k < t[x].k ? rturn(x) : upd(x);
else
ins(v, t[x].rs), t[t[x].rs].k < t[x].k ? lturn(x) : upd(x);
}
void del(int v, int& x) {
if(t[x].v > v) del(v, t[x].ls), upd(x);
else if(t[x].v < v) del(v, t[x].rs), upd(x);
else if(t[x].c > 1) --t[x].c, upd(x);
else if(!t[x].ls) x = t[x].rs;
else if(!t[x].rs) x = t[x].ls;
else if(t[t[x].ls].k < t[t[x].rs].k)
rturn(x), del(v, t[x].rs), upd(x);
else
lturn(x), del(v, t[x].ls), upd(x);
}
int rk(int v, int x) {
if(t[x].v == v) return t[t[x].ls].s + 1;
else if(t[x].v > v) return rk(v, t[x].ls);
else return rk(v, t[x].rs) + t[t[x].ls].s + t[x].c;
}
int kth(int k, int x) {
if(k <= t[t[x].ls].s) return kth(k, t[x].ls);
else if(k <= t[t[x].ls].s + t[x].c) return t[x].v;
else return kth(k - t[t[x].ls].s - t[x].c, t[x].rs);
}
int pre(int v, int x) {
int now = x, ans;
while(now) {
if(t[now].v < v) ans = now, now = t[now].rs;
else now = t[now].ls;
}
return t[ans].v;
}
int nxt(int v, int x) {
int now = x, ans;
while(now) {
if(t[now].v > v) ans = now, now = t[now].ls;
else now = t[now].rs;
}
return t[ans].v;
}
}
using namespace Treap;
/*
注意事项：这个Treap可以适用于空树
*/
维护序列(Splay,FHQTreap)
- 在指定位置插入一个数
- 删除指定位置的数
- 区间染色
- 翻转区间
- 求区间和
- 求最大子段和
Splay
均摊\(O(nlogn)\)，某次操作的复杂度可能达到\(O(n)\)
常数大
建议：找一个lct的板子学。
Splay Code
const int MAXN = 5e5 + 5;
const int INF = 0x3f3f3f3f;
namespace Splay {
#define ls ch[0]
#define rs ch[1]
#define L e[x].ls
#define R e[x].rs
struct Node {
int fa, ch[2];
int v, s, sum, lv, rv, mv;
int tag, rev;
}e[MAXN];
int cnt, rt;
queue que;
int getid() {
int ret;
if(!que.empty()) ret = que.front(), que.pop();
else ret = ++cnt;
return ret;
}
void upd(int x) {
e[x].sum = e[L].sum + e[R].sum + e[x].v;
e[x].s = e[L].s + e[R].s + 1;
e[x].lv = max(e[L].lv, e[L].sum + e[x].v + e[R].lv);
e[x].rv = max(e[R].rv, e[R].sum + e[x].v + e[L].rv);
e[x].mv = max(max(e[L].mv, e[R].mv), e[L].rv + e[x].v + e[R].lv);
}
void psdmdy(int x, int c) {
e[x].v = c; e[x].sum = c * e[x].s;
e[x].mv = max(e[x].v, e[x].sum);
e[x].lv = e[x].rv = max(0, e[x].sum);
e[x].tag = c;
}
void psdrev(int x) {
e[x].rev ^= 1;
swap(e[x].lv, e[x].rv);
swap(L, R);
}
void psd(int x) {
if(e[x].tag != INF) {
if(L) psdmdy(L, e[x].tag);
if(R) psdmdy(R, e[x].tag);
e[x].tag = INF; e[x].rev = 0;
}
if(e[x].rev) {
if(L) psdrev(L);
if(R) psdrev(R);
e[x].rev = 0;
}
}
void init() {
int x;
e[0] = (Node){0, {0, 0}, 0, 0, 0, 0, 0, -INF, INF, 0};
e[rt = getid()] = (Node){0, {0, 0}, -INF, 1, -INF, 0, 0, -INF, INF, 0};
e[x = getid()] = (Node){rt, {0, 0}, -INF, 1, -INF, 0, 0, -INF, INF, 0};
e[rt].rs = x; upd(rt);
}
int idy(int x) {return x == e[e[x].fa].rs;}
void link(int x, int f, int m) {e[x].fa = f; e[f].ch[m] = x;}
void rtt(int x) {
int y = e[x].fa, z = e[y].fa, ix = idy(x), iy = idy(y), s = e[x].ch[ix^1];
link(s, y, ix); link(y, x, ix^1); link(x, z, iy);
upd(y), upd(x);
}
void splay(int x, int to) {
while(e[x].fa != to) {
int y = e[x].fa;
if(e[y].fa != to) rtt(idy(x) == idy(y) ? y : x);
rtt(x);
}
if(!to) rt = x;
}
int kth(int k) {
k++;
int x = rt;
while(1) {
psd(x);
if(k <= e[L].s) x = L;
else if(k <= e[L].s + 1) return x;
else k -= e[L].s + 1, x = R;
}
}
int build(int l, int r, int a[], int f) {
if(l > r) return 0;
int m = (l + r) >> 1;
int x = getid();
e[x] = (Node){f, {0, 0}, a[m], 1, a[m], max(a[m], 0), max(a[m], 0), a[m], INF, 0};
e[x].ls = build(l, m-1, a, x);
e[x].rs = build(m+1, r, a, x);
upd(x);
return x;
}
void ins(int pos, int a[], int n) {
int lp = kth(pos), rp = kth(pos+1);
splay(lp, 0); splay(rp, lp);
int x = build(1, n, a, rp);
e[rp].ls = x;
upd(rp), upd(lp);
}
void dty(int x) {
if(!x) return;
dty(L); dty(R); que.push(x);
}
void del(int pos, int tot) {//[pos, pos+tot-1]
int lp = kth(pos-1), rp = kth(pos+tot);
splay(lp, 0); splay(rp, lp);
dty(e[rp].ls); e[rp].ls = 0;
upd(rp), upd(lp);
}
void mdy(int pos, int tot, int c) {
int lp = kth(pos-1), rp = kth(pos+tot);
splay(lp, 0); splay(rp, lp);
psdmdy(e[rp].ls, c);
upd(rp), upd(lp);
}
void rev(int pos, int tot) {
int lp = kth(pos-1), rp = kth(pos+tot);
splay(lp, 0); splay(rp, lp);
psdrev(e[rp].ls);
upd(rp), upd(lp);
}
int sum(int pos, int tot) {
int lp = kth(pos-1), rp = kth(pos+tot);
splay(lp, 0); splay(rp, lp);
return e[e[rp].ls].sum;
}
int mxsum() {
psd(rt);
return e[rt].mv;
}
/*void print(int x) {
if(!x) return;
psd(x);
print(L);
printf("%d ", e[x].v);
print(R);
}*/
#undef ls
#undef rs
#undef L
#undef R
}
using namespace Splay;
int n, m;
int a[MAXN];
int main() {
n = read(), m = read();
init();
for(int i = 1; i <= n; i++) a[i] = read();
ins(0, a, n);
for(int i = 1; i <= m; i++) {
char s[20];
scanf("%s", s);
if(s[2] == 'S') {//ins
int pos = read(), tot = read();
for(int i = 1; i <= tot; i++) a[i] = read();
ins(pos, a, tot);
} else if(s[2] == 'L') {//del
int pos = read(), tot = read();
del(pos, tot);
} else if(s[2] == 'K') {//mdy
int pos = read(), tot = read(), c = read();
mdy(pos, tot, c);
} else if(s[2] == 'V') {//rev
int pos = read(), tot = read();
rev(pos, tot);
} else if(s[2] == 'T') {//sum
int pos = read(), tot = read();
printf("%d\n", sum(pos, tot));
} else {//mxsum
printf("%d\n", mxsum());
}
}
return 0;
}
无旋Treap(FHQTreap，可持久化Treap，函数式Treap)
分裂、合并
常数大
也可以用来维护序列
<待补>
平衡树总结
通常情况下:
常数：Treap<Splay<FHQTreap
Treap常用于维护有序表
Splay维护有序表效率低，不方便；常用于LCT和维护序列
FHQTreap也可以维护序列，便于实现可持久化，但效率较低
高维问题
原理
维度的组成
对位置有限制，就有位置轴
对权值有限制，就有权值轴
对顺序有要求，就有时间轴
前两者没有本质区别。
时间轴变换
把某一轴变为时间轴。方便降维，解决更方便。
降维方法（2种）
-
离散扫描：将所有询问和数据集合一起按时间排序
-
在线：可持久化
可以查询历史版本的数据结构。
可以修改的是完全可持久化，否则就是部分可持久化
path copying：新开一遍点，但是没有改动的点保留
fat node:(了解即可)
常用于保持动态插入元素的求解过程，如果可以完全可持久化，则可以保存树形的插入过程
二维数点
-
裸题
-
查询一个区间中不小于v的数的个数（位置轴，权值轴）
-
P1972：每次操作询问区间中不同数个数：记录前驱，查询区间(1D)，前驱（2D)
三维数点（三维偏序）
分治树维护
维护某一维的基本方法
以下算法时间复杂度都是\(O(nlog^2n)\)
隐式的分治树（必须离线）
cdq分治
通过分治维护时间轴。询问分成两半，算前面一半对后面一半的贡献。（查询时间前缀）
整体二分
用分治维护需要二分的维度，在分治树上二分
- 静态区间第k小
分治树的组合
树状数组套平衡树
效率一般
空间\(O(nlogn)\)
树状数组套线段树
空间\(O(nlog^2n)\)，各个线段树可以同时二分
效率一般
- 二逼平衡树
线段树套树
支持不可减外层信息
分治套树状数组
离线，空间O(n),效率高，可以在隐式分治树二分
分治套线段树
离线，空间O(n),效率较高，支持较复杂的操作
note：内层如果是权值平衡树，请不要用splay!!!
KDT
维护k维空间矩形信息，\(O(n^{1-1/k})\)，空间O(n)，支持高维标记，但不能剪枝时常数巨大
根号方法
莫队
P1494
给一个序列a，每次操作给出区间[l,r]，求有多少个子区间满足左右端点的数相同
设块大小为l，维护的左端点的移动不超过\(ml+2n\)
右端点的移动不超过\(2n\times ceil(n/l)\),因此取
\(l=ceil(n/\sqrt m)\)得最优复杂度\(O(n\sqrt m)\)
- 曼哈顿最小生成树问题（很难求，不实用）
回滚莫队
有时候无法简单删除，可以只从左端点开始维护区间，移动右端点并在右端点插入相应元素。移动到右端点时，将左端点未插入，得到答案后再撤销左端点的插入。
可以不必删除，但至少要支持两端插入。
分块，根号平衡
\(O(\sqrt n)-O(1)\)或\(O(1)-O(\sqrt n)\)实现：
- 序列单点修改，查询区间和
way1：单点修改：块前缀和，块内前缀和
直接查询
way2：直接修改这个点的值，块的和
查询时加一下
- 序列区间加，查询单点
way1：块打标记，散块暴力维护
自己+块的标记
way2：差分
- 集合插入，查询k小
way1：？
way2：维护树的出现次数，权值分块
暴力查块（先块外，再块里）
P4396