FHQ Treap
普通平衡树
struct treap
{
int l, r, siz, dat, val;
} tr[N];
int idx, rt;
int get_new(int val)
{
tr[++ idx].val = val;
tr[idx].dat = rand();
tr[idx].siz = 1;
return idx;
}
void pushup(int u)
{
tr[u].siz = tr[tr[u].l].siz + tr[tr[u].r].siz + 1;
}
void split(int u, int v, int &x, int &y)
{
if(!u) x = y = 0;
else
{
if(tr[u].val <= v) x = u, split(tr[x].r, v, tr[x].r, y);
else y = u, split(tr[y].l, v, x, tr[y].l);
pushup(u);
}
}
int merge(int x, int y)
{
if(!x || !y) return x + y;
if(tr[x].dat < tr[y].dat)
{
tr[x].r = merge(tr[x].r, y);
pushup(x);
return x;
}
else
{
tr[y].l = merge(x, tr[y].l);
pushup(y);
return y;
}
}
void insert(int val)
{
int x, y, z;
split(rt, val, x, y);
z = get_new(val);
rt = merge(merge(x, z), y);
}
void remove(int val)
{
int x, y, z;
split(rt, val, x, z);
split(x, val - 1, x, y);
y = merge(tr[y].l, tr[y].r);
rt = merge(merge(x, y), z);
}
int get_rk_by_val(int val)
{
int x, y, res;
split(rt, val - 1, x, y);
res = tr[x].siz + 1;
rt = merge(x, y);
return res;
}
int get_val_by_rk(int u, int rk)
{
if(rk <= tr[tr[u].l].siz) return get_val_by_rk(tr[u].l, rk);
else if(rk == tr[tr[u].l].siz + 1) return tr[u].val;
return get_val_by_rk(tr[u].r, rk - tr[tr[u].l].siz - 1);
}
int get_pre(int val)
{
int x, y, res;
split(rt, val - 1, x, y);
res = get_val_by_rk(x, tr[x].siz);
rt = merge(x, y);
return res;
}
int get_nxt(int val)
{
int x, y, res;
split(rt, val, x, y);
res = get_val_by_rk(y, 1);
rt = merge(x, y);
return res;
}
Splay
普通平衡树
int n,idx,root;
struct Splay
{
int s[2],v,p,size;
int cnt;
void init(int _v,int _p)
{
v=_v,p=_p;
size=cnt=1;
}
}tr[N];
void push_up(int x)
{
tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}
void rotate(int x)
{
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
push_up(y),push_up(x);
}
void splay(int x,int k)
{
while(tr[x].p!=k)
{
int y=tr[x].p,z=tr[y].p;
if(z!=k)
if((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root=x;
}
void find(int v)
{
int x=root;
while(tr[x].s[v>tr[x].v]&&v!=tr[x].v)
x=tr[x].s[v>tr[x].v];
splay(x,0);
}
int get_prev(int v)
{
find(v);
int x=root;
if(tr[x].v<v) return x;
x=tr[x].s[0];
while(tr[x].s[1])
x=tr[x].s[1];
return x;
}
int get_next(int v)
{
find(v);
int x=root;
if(tr[x].v>v) return x;
x=tr[x].s[1];
while(tr[x].s[0])
x=tr[x].s[0];
return x;
}
void del(int v)
{
int prev=get_prev(v),next=get_next(v);
splay(prev,0),splay(next,prev);
int son=tr[next].s[0];
if(tr[son].cnt>1)
tr[son].cnt--,splay(son,0);
else
tr[next].s[0]=0,splay(next,0);
}
int get_kth(int k)
{
int u=root;
while(u)
{
if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
else if(tr[tr[u].s[0]].size+tr[u].cnt>=k)
{
splay(u,0);
return tr[u].v;
}
else k-=tr[tr[u].s[0]].size+tr[u].cnt,u=tr[u].s[1];
}
return -1;
}
void insert(int v)
{
int u=root,p=0;
while(u)
{
if(tr[u].v==v)
{
splay(u,0);
tr[u].cnt++;
return;
}
p=u;
u=tr[u].s[v>tr[u].v];
}
u=++idx;
if(p) tr[p].s[v>tr[p].v]=u;
tr[u].init(v,p);
splay(u,0);
}
文艺平衡树
int root,idx;
struct Splay
{
int s[20],size,flag,v,p;
void init(int _v,int _p)
{
v=_v,p=_p;
size=1;
}
} tr[N];
void push_up(int x)
{
tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}
void push_down(int x)
{
if(!tr[x].flag)
return;
swap(tr[x].s[0],tr[x].s[1]);
tr[tr[x].s[0]].flag^=1;
tr[tr[x].s[1]].flag^=1;
tr[x].flag=0;
}
void rotate(int x)
{
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
push_up(y);
push_up(x);
}
void splay(int x,int k)
{
while(tr[x].p!=k)
{
int y=tr[x].p,z=tr[y].p;
if(z!=k)
if(tr[y].s[1]==x != tr[z].s[1]==y) rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root=x;
}
void insert(int v)
{
int u=root,p=0;
while(u)
{
p=u;
u=tr[u].s[v>tr[u].v];
}
u=++idx;
if(p) tr[p].s[v>tr[p].v]=u;
tr[u].init(v,p);
splay(u,0);
}
int get_kth(int k)
{
int u=root;
while(true)
{
push_down(u);
if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
else if(tr[tr[u].s[0]].size+1==k) return u;
else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
}
return -1;
}
void output(int u)
{
push_down(u);
if(tr[u].s[0])
output(tr[u].s[0]);
if(tr[u].v>=1&&tr[u].v<=n) printf("%d ", tr[u].v);
if(tr[u].s[1])
output(tr[u].s[1]);
}
Treap
struct treap
{
int l, r;
int val, dat;
int cnt, siz;
} tr[N];
int idx, rt;
int get_new(int val)
{
tr[++ idx].val = val;
tr[idx].dat = rand();
tr[idx].siz = tr[idx].cnt = 1;
return idx;
}
void pushup(int x)
{
tr[x].siz = tr[tr[x].l].siz + tr[tr[x].r].siz + tr[x].cnt;
}
void zig(int &x)
{
int y = tr[x].l;
tr[x].l = tr[y].r, tr[y].r = x, x = y;
pushup(tr[x].r), pushup(x);
}
void zag(int &x)
{
int y = tr[x].r;
tr[x].r = tr[y].l, tr[y].l = x, x = y;
pushup(tr[x].l), pushup(x);
}
void insert(int &x, int val)
{
if(x == 0)
{
x = get_new(val);
return;
}
if(val == tr[x].val)
{
tr[x].cnt ++, pushup(x);
return;
}
if(val < tr[x].val)
{
insert(tr[x].l, val);
if(tr[tr[x].l].dat > tr[x].dat) zig(x);
}
else if(val > tr[x].val)
{
insert(tr[x].r, val);
if(tr[tr[x].r].dat > tr[x].dat) zag(x);
}
pushup(x);
}
void remove(int &x, int val)
{
if(x == 0) return;
if(tr[x].val == val)
{
if(tr[x].cnt > 1)
{
tr[x].cnt --;
pushup(x);
return;
}
if(tr[x].l || tr[x].r)
{
if(tr[x].r == 0 || tr[tr[x].l].dat > tr[tr[x].r].dat)
zig(x), remove(tr[x].r, val);
else
zag(x), remove(tr[x].l, val);
pushup(x);
}
else x = 0;
return;
}
if(val < tr[x].val) remove(tr[x].l, val);
else remove(tr[x].r, val);
pushup(x);
}
int get_rk_by_val(int x, int val)
{
if(x == 0) return 0;
if(val == tr[x].val) return tr[tr[x].l].siz + 1;
if(val < tr[x].val) return get_rk_by_val(tr[x].l, val);
return tr[tr[x].l].siz + tr[x].cnt + get_rk_by_val(tr[x].r, val);
}
int get_val_by_rk(int x, int rk)
{
if(x == 0) return INF;
if(tr[tr[x].l].siz >= rk) return get_val_by_rk(tr[x].l, rk);
if(tr[tr[x].l].siz + tr[x].cnt >= rk) return tr[x].val;
return get_val_by_rk(tr[x].r, rk - tr[tr[x].l].siz - tr[x].cnt);
}
int get_pre(int x, int val)
{
if(x == 0) return -INF;
if(val <= tr[x].val) return get_pre(tr[x].l, val);
return max(tr[x].val, get_pre(tr[x].r, val));
}
int get_nxt(int x, int val)
{
if(x == 0) return INF;
if(val >= tr[x].val) return get_nxt(tr[x].r, val);
return min(tr[x].val, get_nxt(tr[x].l, val));
}
树状数组
struct BIT
{
int c[N], mx;
#define lbt(x) x & -x
void Add(int x, int v)
{
for(;x <= mx;x += lbt(x)) c[x] += v;
}
int Ask(int x)
{
int res = 0;
for(;x;x -= lbt(x)) res += c[x];
return res;
}
} bit;
线段树
struct segment_tree
{
int l, r, val, tag;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define val(x) tr[x].val
#define tag(x) tr[x].tag
}tr[N << 2];
void pushup(int x)
{
val(x) = val(x << 1) + val(x << 1 | 1);
}
void pushdown(int x)
{
if(!tag(x)) return;
tag(x << 1) += tag(x);
val(x << 1) += (r(x << 1) - l(x << 1) + 1) * tag(x);
tag(x << 1 | 1) += tag(x);
val(x << 1 | 1) += (r(x << 1 | 1) - l(x << 1 | 1) + 1) * tag(x);
tag(x) = 0;
}
void build(int l, int r, int x)
{
l(x) = l, r(x) = r;
if(l == r)
{
val(x) = a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, x << 1);
build(mid + 1, r, x << 1 | 1);
pushup(x);
}
void update(int l, int r, int x, ll v)
{
if(l <= l(x) && r(x) <= r)
{
val(x) += (r(x) - l(x) + 1) * v;
tag(x) += v;
return;
}
pushdown(x);
int mid = l(x) + r(x) >> 1;
if(l <= mid) update(l, r, x << 1, v);
if(r > mid) update(l, r, x << 1 | 1, v);
pushup(x);
}
int query(int l, int r, int x)
{
if(l <= l(x) && r(x) <= r) return val(x);
pushdown(x);
int mid = l(x) + r(x) >> 1, res = 0;
if(l <= mid) res += query(l, r, x << 1);
if(r > mid) res += query(l, r, x << 1 | 1);
return res;
}
树链剖分
void dfs1(int u, int fath) //处理fa,dep,siz,son
{
fa[u] = fath;
dep[u] = dep[fath] + 1;
siz[u] = 1;
for(auto v:e[u])
{
if(v == fath) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[son[u]])
son[u] = v;
}
}
void dfs2(int u, int fst)
{
id[u] = ++ idx;
a[idx] = w[u];值
top[u] = fst;
if(!son[u]) return;
dfs2(son[u], fst);
for(auto v:e[u])
{
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
快速幂
int Pow(int a, int b)
{
int res = 1;
for(;b;a *= a, b >>= 1) if(b & 1) res *= a;
return res;
}
ST表
for(int j = 1;(1 << j) <= n;j ++)
for(int i = 1;i + (1 << j) - 1<= n;i ++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
dijkstra
void duijkstra()
{
for(int i = 1;i <= n;i ++) dist[i] = INF, st[i] = false;
priority_queue<PII, vector<PII>, greater<PII> > q;
dist[s] = 0;
q.push({0, s});
while(q.size())
{
int u = q.top().se;
q.pop();
if(st[u]) continue;
st[u] = true;
for(int i = h[u];i;i = nxt[i])
{
int v = to[i], w = val[i];
if(dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
}
加边
int h[N], nxt[M << 1], to[M << 1], val[M << 1], cnt;
void add(int u, int v, int w)
{
to[++ cnt] = v, val[cnt] = w, nxt[cnt] = h[u], h[u] = cnt;
}
int h[N], nxt[M << 1], to[M << 1], cnt;
void add(int u, int v)
{
to[++ cnt] = v, nxt[cnt] = h[u], h[u] = cnt;
}
LCA
void dfs(int u, int fath)
{
dep[u] = dep[fath] + 1, fa[u][0] = fath;
for(int i = 1;i <= lg[dep[u]];i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = head[u];i;i = nxt[i])
{
int v = to[i];
if(v == fath) continue;
dfs(v, u);
}
}
int lca(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
while(dep[u] > dep[v]) u = fa[u][lg[dep[u] - dep[v]]];
if(u == v) return u;
for(int k = lg[dep[u]];k >= 0;k --)
if(fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k];
return fa[u][0];
}
DSU
int fa[N];
void dsu_clear()
{
for(int i = 1;i <= n;i ++) fa[i] = i;
}
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
fa[find(x)] = find(y);
}
最小生成树
sort(e + 1, e + 1 + m);
ll res = 0;
for(int i = 1;i <= m;i ++)
{
int u = find(e[i].u), v = find(e[i].v);
if(u == v) continue;
res += e[i].w;
merge(u, v);
}
Floyd
for(int i = 1;i <= n;i ++) f[i][i] = 0;
for(int k = 1;k <= n;k ++)
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
矩阵快速幂
struct matrix
{
ll c[105][105];
} A;
ll n, k;
matrix operator *(const matrix &a, const matrix &b)
{
matrix c;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++) c.c[i][j] = 0;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
for(int k = 1;k <= n;k ++)
c.c[i][j] = (c.c[i][j] + a.c[i][k] * b.c[k][j]) % mod;
return c;
}
matrix qpow(matrix a, ll b)
{
matrix res;
for(int i = 1;i <= n;i ++) res.c[i][i] = 1;
for(;b;a = a * a, b >>= 1)if(b & 1) res = res * a;
return res;
}