![[HNOI2008]玩具装箱 题解 & DP斜率优化原理与实现](https://ksmeow.moe/wp-content/uploads/2018/03/180306b-720x400.jpg "180306b")
[HNOI2008]玩具装箱 题解 & DP斜率优化原理与实现
题目地址：ė …
月度归档： 2018 年 3 月
![[CF314E]Sereja and Squares 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180306a-625x400.png "180306a")
![[CQOI2009]叶子的染色 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180305c.png "180305c")
[CQOI2009]叶子的染色 题解
题目地址：洛谷：【P3155】[CQOI2009]叶子的染色 – 洛谷、BZOJ：Problem 1304. — [CQOI2009]叶子的染色
题目描述
给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。 对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。
输入输出格式
输入格式：
第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。以下m-1行每行两个整数a，b（1<=a < b <= m），表示结点a和b 有边相连。
输出格式：
仅一个数，即着色结点数的最小值。
输入输出样例
输入样例#1：
5 3 0 1 0 1 4 2 5 4 5 3 5
输出样例#1：
2
说明
M<=10000
N<=5021
题解
树形DP的模型。令dp[u][col]表示以u为根的子树，希望的最后一个节点为col的情况子树中最少染色数。转移方程如下。
dp[u][col] = \sum \min\{dp[v][col], dp[v][!col] + 1\}
其中v是u的儿子。
这个转移的含义是，如果儿子的要求与自己的要求一样，那么这个转移过程中不需要再染色。如果要求不一样，则把儿子染上色，再考虑根的事情。初始把每个叶子节点的c[u]颜色设为0，非c[u]颜色设为无穷大，转移上来即可。
如果我们枚举每个点是根的可能性，那么这个DP是O(n^2)的，数据范围承受不了。但是我们思考两个相邻点一个为根或另一个为根的情况，相邻点绝对不可能同色，那么情况只剩下一个染一个不染或者异色，两者为根并不会改变答案。可以假设我们已经得到了最优解，然后尝试把根的一个儿子拎上来这样理解。那么就证明了任意非叶子为根答案一样，任意指定一个非叶子节点为根即可。复杂度优化为O(n)。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <algorithm>
#include <vector>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
// variables
const int MAXN = 10005, INF = 1e9;
std::vector<int> gra[MAXN];
int m, n, c[MAXN], dp[MAXN][2], ut, vt;
// dfs
inline void dfs(int fa, int u) {
if(u <= n) {
dp[u][c[u]] = 0;
dp[u][c[u] ^ 1] = INF;
return;
}
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa) continue;
dfs(u, v);
dp[u][0] += std::min(dp[v][0], dp[v][1] + 1);
dp[u][1] += std::min(dp[v][1], dp[v][0] + 1);
}
}
int main() {
m = readint();
n = readint();
for(int i = 1; i <= n; i++) {
c[i] = readint();
}
for(int i = 1; i < m; i++) {
ut = readint();
vt = readint();
gra[ut].push_back(vt);
gra[vt].push_back(ut);
}
dfs(0, m);
printf("%d", std::min(dp[m][0], dp[m][1]) + 1);
return 0;
}
![[中山OI2011]小W的问题 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180305b-595x400.png "180305b")
![[ZJOI2012]网络 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180305a-534x400.png "180305a")
![[HNOI2011]括号修复 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180303b.png "180303b")
[HNOI2011]括号修复 题解
题目地址：洛谷：【P3215】[HNOI2011]括号修复 – 洛谷、BZOJ：Problem 2329. — [HNOI2011]括号修复
题目描述
一个合法的括号序列是这样定义的：
- 空串是合法的。
- 如果字符串 S 是合法的，则(S)也是合法的。
- 如果字符串 A 和 B 是合法的，则 AB 也是合法的。
现在给你一个长度为 N 的由‘(‘和‘)’组成的字符串，位置标号从 1 到 N。对这个字符串有下列四种操作：
- Replace a b c：将[a,b]之间的所有括号改成 c。例如：假设原来的字符串为：))())())(，那么执行操作 Replace 2 7 ( 后原来的字符串变为：)(((((()(。
- Swap a b：将[a,b]之间的字符串翻转。例如：假设原来的字符串为：))())())(，那么执行操作 Swap 3 5 后原来的字符串变为：))))(())(。
- Invert a b：将[a,b]之间的‘(’变成‘)’,‘)’变成‘(’。例如：假设原来的字符串为：))())())(，那么执行操作 Invert 4 8 后原来的字符串变为：))((()(((。
- Query a b：询问[a,b]之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的‘(’变成‘)’或‘)’变成‘(’。注意执行操作 Query 并不改变当前的括号序列。例如：假设原来的字符串为：))())())(，那么执行操作 Query 3 6 的结果为 2，因为要将位置 5 的‘)’变成‘(’并将位置 6 的‘(’变成‘)’。
输入输出格式
输入格式：
从文件input.txt中读入数据，输入文件的第一行是用空格隔开的两个正整数N和M，分别表示字符串的长度和将执行的操作个数。第二行是长度为N的初始字符串S。接下来的M行是将依次执行的M个操作，其中操作名与操作数之间以及相邻操作数之间均用空格隔开。
输出格式：
输出文件 output.txt 包含 T 行，其中 T 是输入的将执行的 M 个操作中 Query 操作出现的次数。Query 操作的每次出现依次对应输出文件中的一行，该行只有一个非负整数，表示执行对应 Query 操作的结果，即：所指字符串至少要改变多少位才能变成合法的括号序列。输入数据保证问题有解。
输入输出样例
输入样例#1：
4 5 (((( Replace 1 2 ) Query 1 2 Swap 2 3 Invert 3 4 Query 1 4
输出样例#1：
1 2
说明
样例解释：
输入中有2个Query操作，所以输出有2行。执行第一个Query操作时的括号序列为))((，因改变第1位可使[1,2]之间的字符串变成合法的括号序列，故输出的第一行为1。执行第二个Query操作时的括号序列为)((),因要改变第1位和第2位才能使[1,4]之间的字符串变成合法的括号序列，故输出的第二行为2。
数据范围：
30%的数据满足N,M≤3000。100%的数据满足N,M≤100000。
题解
从操作4入手，问题转化
首先我们考虑一个问题，给一个串，怎么知道它最少改变多少位才能合法。我们发现，去除配对成功的括号后，剩余不能配对的串一定长这样：))))(((。假如这里面有a个)，b个(，答案应该是\lceil \frac{a}{2} \rceil + \lceil \frac{b}{2} \rceil。对于括号序列，我们可以用1代替(，用-1代替)，这样求个和就会自动消除那些已经匹配的括号。而a就是最小前缀和，b就是最大后缀和。
我们可以用splay维护区间和，区间最大前缀和，区间最大后缀和。有了这些信息，最小前缀和可以通过和-最大后缀和求得。
标记和标记的apply
翻转标记和替换标记很常规，可以参考[NOI2005]维护数列 题解 | KSkun’s Blog。
至于invert标记，这个会比较麻烦。它会使总和变为相反数，最大前缀和变为最小前缀和，最大后缀和变为最小后缀和。但是我们可以用总和-最小前缀求得最大后缀，以此类推，这个标记就也不是问题了。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <algorithm>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
inline bool isop(char c) {
return c == 'R' || c == 'S' || c == 'I' || c == 'Q';
}
inline char readop() {
char c;
while(!isop(c = fgc()));
return c;
}
inline bool isbracket(char c) {
return c == '(' || c == ')';
}
inline char readbracket() {
char c;
while(!isbracket(c = fgc()));
return c;
}
// variables
const int MAXN = 100005, INF = 1e9;
int n, m, at, bt, ct, a[MAXN];
char op;
// splay
struct Node {
int val, sum, mxl, mxr, siz;
bool rev, rep, inv;
int ch[2], fa;
} tr[MAXN];
int tot = 0, sta[MAXN], stop = 0, rt = 0;
inline void update(int p) {
int lch = tr[p].ch[0], rch = tr[p].ch[1];
tr[p].siz = tr[lch].siz + tr[rch].siz + 1;
tr[p].sum = tr[lch].sum + tr[rch].sum + tr[p].val;
tr[p].mxl = std::max(tr[lch].mxl, tr[lch].sum + tr[p].val + tr[rch].mxl);
tr[p].mxr = std::max(tr[rch].mxr, tr[rch].sum + tr[p].val + tr[lch].mxr);
}
inline void pushdown(int p) {
int lch = tr[p].ch[0], rch = tr[p].ch[1];
if(tr[p].rep) {
tr[p].rep = tr[p].rev = tr[p].inv = false;
if(lch) {
tr[lch].rep = true;
tr[lch].rev = tr[lch].inv = false;
tr[lch].val = tr[p].val;
tr[lch].sum = tr[p].val * tr[lch].siz;
tr[lch].mxl = tr[lch].mxr = std::max(0, tr[lch].sum);
}
if(rch) {
tr[rch].rep = true;
tr[rch].rev = tr[rch].inv = false;
tr[rch].val = tr[p].val;
tr[rch].sum = tr[p].val * tr[rch].siz;
tr[rch].mxl = tr[rch].mxr = std::max(0, tr[rch].sum);
}
}
if(tr[p].rev) {
tr[p].rev = false;
if(lch) {
std::swap(tr[lch].mxl, tr[lch].mxr);
std::swap(tr[lch].ch[0], tr[lch].ch[1]);
tr[lch].rev = !tr[lch].rev;
}
if(rch) {
std::swap(tr[rch].mxl, tr[rch].mxr);
std::swap(tr[rch].ch[0], tr[rch].ch[1]);
tr[rch].rev = !tr[rch].rev;
}
}
if(tr[p].inv) {
tr[p].inv = false;
if(lch) {
int omxl = tr[lch].mxl;
tr[lch].inv = !tr[lch].inv;
tr[lch].mxl = std::max(0, -(tr[lch].sum - tr[lch].mxr));
tr[lch].mxr = std::max(0, -(tr[lch].sum - omxl));
tr[lch].sum = -tr[lch].sum;
tr[lch].val = -tr[lch].val;
}
if(rch) {
int omxl = tr[rch].mxl;
tr[rch].inv = !tr[rch].inv;
tr[rch].mxl = std::max(0, -(tr[rch].sum - tr[rch].mxr));
tr[rch].mxr = std::max(0, -(tr[rch].sum - omxl));
tr[rch].sum = -tr[rch].sum;
tr[rch].val = -tr[rch].val;
}
}
}
inline int newnode() {
int p;
if(stop > 0) {
p = sta[--stop];
} else {
p = ++tot;
}
memset(tr + p, 0, sizeof(Node));
return p;
}
inline void delnode(int a) {
sta[stop++] = a;
}
inline bool isleft(int p) {
return tr[tr[p].fa].ch[0] == p;
}
inline void rotate(int p) { // p is child
bool type = !isleft(p);
int fa = tr[p].fa, ffa = tr[fa].fa;
tr[fa].ch[type] = tr[p].ch[!type];
tr[p].ch[!type] = fa;
tr[tr[fa].ch[type]].fa = fa;
if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[p].fa = tr[fa].fa;
tr[fa].fa = p;
update(fa);
update(p);
}
inline void splay(int p, int tar) {
for(int fa; (fa = tr[p].fa) != tar; rotate(p)) {
if(tr[tr[p].fa].fa != tar) {
rotate(isleft(fa) == isleft(p) ? fa : p);
}
}
if(!tar) rt = p;
}
inline int find(int p, int rk) {
pushdown(p);
int lch = tr[p].ch[0], rch = tr[p].ch[1];
if(tr[lch].siz + 1 == rk) return p;
else if(tr[lch].siz >= rk) return find(lch, rk);
else return find(rch, rk - tr[lch].siz - 1);
}
inline int build(int fa, int l, int r) {
if(l > r) return 0;
int p = newnode();
if(l == r) {
tr[p].siz = 1;
tr[p].val = tr[p].sum = a[l];
tr[p].mxl = tr[p].mxr = std::max(0, a[l]);
tr[p].fa = fa;
return p;
}
int mid = (l + r) >> 1;
tr[p].ch[0] = build(p, l, mid - 1);
tr[p].ch[1] = build(p, mid + 1, r);
tr[p].fa = fa;
tr[p].val = a[mid];
update(p);
return p;
}
inline void replace(int x, int len, int val) {
int a = find(rt, x), b = find(rt, x + len + 1);
splay(a, 0);
splay(b, a);
int p = tr[b].ch[0];
tr[p].val = val;
tr[p].rep = true;
tr[p].sum = val * tr[p].siz;
tr[p].mxl = tr[p].mxr = std::max(0, tr[p].sum);
update(b);
update(a);
}
inline void reverse(int x, int len) {
int a = find(rt, x), b = find(rt, x + len + 1);
splay(a, 0);
splay(b, a);
int p = tr[b].ch[0];
if(!tr[p].rep) {
tr[p].rev = !tr[p].rev;
std::swap(tr[p].mxl, tr[p].mxr);
std::swap(tr[p].ch[0], tr[p].ch[1]);
update(b);
update(a);
}
}
inline void invert(int x, int len) {
int a = find(rt, x), b = find(rt, x + len + 1);
splay(a, 0);
splay(b, a);
int p = tr[b].ch[0];
int omxl = tr[p].mxl;
tr[p].inv = !tr[p].inv;
tr[p].mxl = std::max(0, -(tr[p].sum - tr[p].mxr));
tr[p].mxr = std::max(0, -(tr[p].sum - omxl));
tr[p].sum = -tr[p].sum;
tr[p].val = -tr[p].val;
}
inline int query(int x, int len) {
int a = find(rt, x), b = find(rt, x + len + 1);
splay(a, 0);
splay(b, a);
int p = tr[b].ch[0];
return (tr[p].mxr - tr[p].sum + 1) / 2 + (tr[p].mxr + 1) / 2;
}
int main() {
n = readint();
m = readint();
for(int i = 1; i <= n; i++) {
a[i + 1] = readbracket() == '(' ? 1 : -1;
}
rt = build(0, 1, n + 2);
n += 2;
while(m--) {
op = readop();
at = readint();
bt = readint();
if(op == 'R') {
ct = readbracket() == '(' ? 1 : -1;
replace(at, bt - at + 1, ct);
}
if(op == 'S') {
reverse(at, bt - at + 1);
}
if(op == 'I') {
invert(at, bt - at + 1);
}
if(op == 'Q') {
printf("%d\n", query(at, bt - at + 1));
}
}
return 0;
}
![[NOI2005]维护数列 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180303a-378x400.png "180303a")
![[JSOI2008]火星人 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180302a-524x400.png "180302a")
Splay原理与实现
注：本文部分图片来自互联网，其相关权利归原作者所有，感谢原作者的分享。
概述
Splay（伸展树）是异于Treap的另一种平衡树，由Tarjan等发明。其滋磁的操作更为通用，因此被OIer广为使用。这里介绍Splay的原理与实现。
原理与实现
旋转
旋转操作与Treap相同，可以在Treap原理与实现 | KSkun’s Blog查看示例。这里将左右旋换为了一种自适应的写法。
下面是旋转的实现。
inline void rotate(int p) { // p is child
bool type = !isleft(p);
int fa = tr[p].fa, ffa = tr[fa].fa;
tr[fa].ch[type] = tr[p].ch[!type];
tr[p].ch[!type] = fa;
tr[tr[fa].ch[type]].fa = fa;
if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[p].fa = tr[fa].fa;
tr[fa].fa = p;
calsiz(fa);
calsiz(p);
}
伸展
Splay（伸展）操作是Splay的核心功能，下面介绍Splay操作的原理。
我们需要讨论以下三种情况：
1. zig/zag式
zig/zag式，即为仅有两个节点，例如：
这种情况使用单旋，将儿子变为根。
2.zig-zag式
zig-zag式即儿子-父亲，父亲-祖先的左右儿子关系不相同，如下图。
这种情况使用双旋，先转儿子，再转父亲。例如：
原树：
旋转后：
3.zig-zig式
zig-zag式即儿子-父亲，父亲-祖先的左右儿子关系相同，如下图。
这种情况使用双旋，对儿子进行两次旋转。例如：
转完以后还是一个链啊？为什么会减小复杂度呢？
试想，既然原树不平衡，说明左侧子树较大，我们把一部分放在右侧，这样就会更平衡。
Splay操作的实现如下。
inline void splay(int p, int tar) {
for(int fa; (fa = tr[p].fa) != tar; rotate(p)) {
if(tr[tr[p].fa].fa != tar) {
rotate(isleft(fa) == isleft(p) ? fa : p);
}
}
if(!tar) rt = p;
}
splay(p, tar)的功能是将p旋转至tar的儿子。
插入/删除
与Treap的操作并无两样，就是需要在插入/删除后splay一下。详情见实现。
inline void insert(int val) {
if(!rt) {
rt = newnode();
tr[rt].val = val;
tr[rt].siz = tr[rt].cnt = 1;
return;
}
int p = rt, fa = 0;
for(;;) {
if(val == tr[p].val) {
tr[p].cnt++;
calsiz(p);
calsiz(fa);
splay(p);
return;
}
fa = p;
p = tr[p].ch[tr[p].val < val];
if(!p) {
p = newnode();
tr[p].val = val;
tr[p].siz = tr[p].cnt = 1;
tr[p].fa = fa;
tr[fa].ch[tr[fa].val < val] = p;
calsiz(fa);
splay(p);
return;
}
}
}
inline void delet(int val) {
queryrk(val);
if(tr[rt].cnt > 1) {
tr[rt].cnt--;
calsiz(rt);
return;
}
if(!tr[rt].ch[0]) {
delnode(rt);
rt = tr[rt].ch[1];
tr[rt].fa = 0;
return;
}
if(!tr[rt].ch[1]) {
delnode(rt);
rt = tr[rt].ch[0];
tr[rt].fa = 0;
return;
}
int ort = rt, lmx = querypre();
splay(lmx);
tr[rt].ch[1] = tr[ort].ch[1];
tr[tr[rt].ch[1]].fa = rt;
delnode(ort);
calsiz(rt);
}
其他
其他和Treap区别不大，可以看代码。
区间翻转
将整个数列按照顺序建一棵splay，权值代表数列的第几个数。区间翻转实质上可以通过交换左右儿子实现。而且通过打标记的形式可以做到lazy标记的效果。
在打标记之前，我们首先要把需要翻转的序列放进一个子树中。先splay l-1节点到根，再splay r+1节点到l-1节点儿子处。这样，根的右儿子的左儿子所在子树就是大于l-1小于r+1，即[l, r]区间。在这个子树的根打标记即可。但是要用到l-1和r+1，我们考虑加数列两端加-INF和INF两项，避免l-1和r+1越界。
Splay的中序遍历就是当前数列。
代码
常规操作
这份代码可以通过洛谷【P3369】【模板】普通平衡树（Treap/SBT） – 洛谷或BZOJProblem 3224. — Tyvj 1728 普通平衡树题目。
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
// variable
const int MAXN = 100005, INF = 1e9;
int n, op, x;
// splay
struct Node {
int ch[2], val, siz, cnt, fa;
} tr[MAXN];
int tot = 0, sta[MAXN], stop = 0, rt = 0, anst;
inline void calsiz(int p) {
tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + tr[p].cnt;
}
inline int newnode() {
int p;
if(stop > 0) {
p = sta[--stop];
} else {
p = ++tot;
}
memset(tr + p, 0, sizeof(Node));
return p;
}
inline void delnode(int a) {
sta[stop++] = a;
}
inline bool isleft(int p) {
return tr[tr[p].fa].ch[0] == p;
}
inline void rotate(int p) { // p is child
bool type = !isleft(p);
int fa = tr[p].fa, ffa = tr[fa].fa;
tr[fa].ch[type] = tr[p].ch[!type];
tr[p].ch[!type] = fa;
tr[tr[fa].ch[type]].fa = fa;
if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[p].fa = tr[fa].fa;
tr[fa].fa = p;
calsiz(fa);
calsiz(p);
if(!tr[p].fa) rt = p;
}
inline void splay(int p) {
while(tr[p].fa) {
if(!tr[tr[p].fa].fa) {
rotate(p);
} else {
if(isleft(p) == isleft(tr[p].fa)) {
rotate(tr[p].fa);
rotate(p);
} else {
rotate(p);
rotate(p);
}
}
}
}
inline void insert(int val) {
if(!rt) {
rt = newnode();
tr[rt].val = val;
tr[rt].siz = tr[rt].cnt = 1;
return;
}
int p = rt, fa = 0;
for(;;) {
if(val == tr[p].val) {
tr[p].cnt++;
calsiz(p);
calsiz(fa);
splay(p);
return;
}
fa = p;
p = tr[p].ch[tr[p].val < val];
if(!p) {
p = newnode();
tr[p].val = val;
tr[p].siz = tr[p].cnt = 1;
tr[p].fa = fa;
tr[fa].ch[tr[fa].val < val] = p;
calsiz(fa);
splay(p);
return;
}
}
}
inline int queryrk(int val) {
int p = rt, ans = 0;
for(;;) {
if(val < tr[p].val) {
p = tr[p].ch[0];
} else {
ans += tr[tr[p].ch[0]].siz;
if(val == tr[p].val) {
splay(p);
return ans + 1;
}
ans += tr[p].cnt;
p = tr[p].ch[1];
}
}
}
inline int queryn(int rk) {
int p = rt;
for(;;) {
if(tr[p].ch[0] && rk <= tr[tr[p].ch[0]].siz) {
p = tr[p].ch[0];
} else {
if(rk <= tr[tr[p].ch[0]].siz + tr[p].cnt) {
return tr[p].val;
}
rk -= tr[tr[p].ch[0]].siz + tr[p].cnt;
p = tr[p].ch[1];
}
}
}
inline int querypre() {
int p = tr[rt].ch[0];
while(tr[p].ch[1]) p = tr[p].ch[1];
return p;
}
inline int querynxt() {
int p = tr[rt].ch[1];
while(tr[p].ch[0]) p = tr[p].ch[0];
return p;
}
inline void delet(int val) {
queryrk(val);
if(tr[rt].cnt > 1) {
tr[rt].cnt--;
calsiz(rt);
return;
}
if(!tr[rt].ch[0]) {
delnode(rt);
rt = tr[rt].ch[1];
tr[rt].fa = 0;
return;
}
if(!tr[rt].ch[1]) {
delnode(rt);
rt = tr[rt].ch[0];
tr[rt].fa = 0;
return;
}
int ort = rt, lmx = querypre();
splay(lmx);
tr[rt].ch[1] = tr[ort].ch[1];
tr[tr[rt].ch[1]].fa = rt;
delnode(ort);
calsiz(rt);
}
int main() {
n = readint();
while(n--) {
op = readint();
x = readint();
switch(op) {
case 1:
insert(x);
break;
case 2:
delet(x);
break;
case 3:
printf("%d\n", queryrk(x));
break;
case 4:
printf("%d\n", queryn(x));
break;
case 5:
insert(x);
printf("%d\n", tr[querypre()].val);
delet(x);
break;
case 6:
insert(x);
printf("%d\n", tr[querynxt()].val);
delet(x);
break;
}
}
return 0;
}
区间翻转
这份代码可以通过洛谷【P3391】【模板】文艺平衡树（Splay） – 洛谷或BZOJProblem 3223. — Tyvj 1729 文艺平衡树题目。
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
// variable
const int MAXN = 100005, INF = 1e9;
int n, m, ll, rr, data[MAXN];
// splay
struct Node {
int ch[2], val, siz, cnt, fa;
bool tag;
} tr[MAXN];
int tot = 0, sta[MAXN], stop = 0, rt = 0;
inline void calsiz(int p) {
tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + tr[p].cnt;
}
inline int newnode() {
int p;
if(stop > 0) {
p = sta[--stop];
} else {
p = ++tot;
}
memset(tr + p, 0, sizeof(Node));
return p;
}
inline void delnode(int a) {
sta[stop++] = a;
}
inline bool isleft(int p) {
return tr[tr[p].fa].ch[0] == p;
}
inline void rotate(int p) { // p is child
bool type = !isleft(p);
int fa = tr[p].fa, ffa = tr[fa].fa;
tr[fa].ch[type] = tr[p].ch[!type];
tr[p].ch[!type] = fa;
tr[tr[fa].ch[type]].fa = fa;
if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[p].fa = tr[fa].fa;
tr[fa].fa = p;
calsiz(fa);
calsiz(p);
}
inline void splay(int p, int tar) {
for(int fa; (fa = tr[p].fa) != tar; rotate(p)) {
if(tr[tr[p].fa].fa != tar) {
rotate(isleft(fa) == isleft(p) ? fa : p);
}
}
if(!tar) rt = p;
}
inline void pushdown(int p) {
if(tr[p].tag) {
if(tr[p].ch[0]) tr[tr[p].ch[0]].tag = !tr[tr[p].ch[0]].tag;
if(tr[p].ch[1]) tr[tr[p].ch[1]].tag = !tr[tr[p].ch[1]].tag;
std::swap(tr[p].ch[0], tr[p].ch[1]);
tr[p].tag = false;
}
}
inline int queryn(int rk) {
int p = rt;
for(;;) {
pushdown(p);
if(tr[p].ch[0] && rk <= tr[tr[p].ch[0]].siz) {
p = tr[p].ch[0];
} else {
if(rk <= tr[tr[p].ch[0]].siz + tr[p].cnt) {
return p;
}
rk -= tr[tr[p].ch[0]].siz + tr[p].cnt;
p = tr[p].ch[1];
}
}
}
inline int build(int fa, int l, int r) {
if(l > r) return 0;
int mid = (l + r) >> 1, p = newnode();
tr[p].val = data[mid];
tr[p].fa = fa;
tr[p].ch[0] = build(p, l, mid - 1);
tr[p].ch[1] = build(p, mid + 1, r);
tr[p].cnt = 1;
calsiz(p);
return p;
}
inline void reverse(int l, int r) {
int x = queryn(l), y = queryn(r + 2);
splay(x, 0);
splay(y, x);
tr[tr[tr[rt].ch[1]].ch[0]].tag = !tr[tr[tr[rt].ch[1]].ch[0]].tag;
}
inline void dfs(int p) {
pushdown(p);
if(tr[p].ch[0]) dfs(tr[p].ch[0]);
if(tr[p].val != -INF && tr[p].val != INF) {
printf("%d ", tr[p].val);
}
if(tr[p].ch[1]) dfs(tr[p].ch[1]);
}
int main() {
n = readint();
m = readint();
for(int i = 2; i <= n + 1; i++) {
data[i] = i - 1;
}
data[1] = -INF;
data[n + 2] = INF;
rt = build(0, 1, n + 2);
while(m--) {
ll = readint();
rr = readint();
reverse(ll, rr);
}
dfs(rt);
return 0;
}
参考资料
- P3391 【模板】文艺平衡树（Splay） 题解
- bzoj3223: Tyvj 1729 文艺平衡树 平衡树上的区间翻转标记 – CSDN博客
- 史上第二详尽的平衡树（Splay）详解 – CSDN博客
- 纸上谈兵: 伸展树 (splay tree) – Vamei – 博客园
- Splay学习笔记 – CSDN博客
- splay复习小记 – CSDN博客
- Splay入门解析【保证让你看不懂（滑稽）】 – CSDN博客
文中图片也来源于参考资料。
