cancan123456 @ 2022-02-12 22:22:57
#include <cstdio>
using namespace std;
const int N = 100005;
int v[N], ch[N][2], fa[N];
int rev[N];
int root, tot;
void LeftRotate(int x) {
int y = ch[x][1], z = fa[x];
ch[x][1] = ch[y][0];
if (ch[x][1] != 0) {
fa[ch[x][1]] = x;
}
fa[y] = z;
if (z != 0) {
if (ch[z][0] == x) {
ch[z][0] = y;
} else {
ch[z][1] = y;
}
}
fa[x] = y;
ch[y][0] = x;
}
void RightRotate(int x) {
int y = ch[x][0], z = fa[x];
ch[x][0] = ch[y][1];
if (ch[y][1] != 0) {
fa[ch[y][1]] = x;
}
fa[y] = z;
if (z != 0) {
if (ch[z][0] == x) {
ch[z][0] = y;
} else {
ch[z][1] = y;
}
}
fa[x] = y;
ch[y][1] = x;
}
void Rotate(int x) {
if (ch[fa[x]][0] == x) {
RightRotate(fa[x]);
} else {
LeftRotate(fa[x]);
}
}
void Splay(int x, int goal_father = 0) {
while (fa[x] != goal_father) {
int y = fa[x];
int z = fa[y];
if (z != goal_father) {
if ((ch[y][0] == x && ch[z][0] == y) || (ch[y][1] == x && ch[z][1] == y)) {
Rotate(y);
} else {
Rotate(x);
}
}
Rotate(x);
}
if (goal_father == 0) {
root = x;
}
}
int Find(int x) {
int p = root;
while (true) {
if (v[p] == x) {
return p;
} else if (x < v[p]) {
p = ch[p][0];
} else {
p = ch[p][1];
}
}
}
void Insert(int x) {
if (root == 0) {
tot++;
v[tot] = x;
root = tot;
} else {
int cur = root, f = 0;
while (true) {
if (v[cur] == x) {
break;
}
f = cur;
if (x < v[cur]) {
if (ch[cur][0] == 0) {
tot++;
v[tot] = x;
fa[tot] = f;
ch[f][0] = tot;
cur = tot;
break;
} else {
cur = ch[cur][0];
}
} else {
if (ch[cur][1] == 0) {
tot++;
v[tot] = x;
fa[tot] = f;
ch[f][1] = tot;
cur = tot;
break;
} else {
cur = ch[cur][1];
}
}
}
Splay(cur);
}
}
int build(int l, int r, int f) {
if (l > r) {
return 0;
}
int p = ++tot;
int mid = (l + r) / 2;
fa[p] = f;
v[p] = mid;
ch[p][0] = build(l, mid - 1, p);
ch[p][1] = build(mid + 1, r, p);
return p;
}
void swap(int & a, int & b) {
a ^= b ^= a ^= b;
}
int n;
void print(int p = root) {
if (rev[p] == 1) {
rev[p] ^= 1;
swap(ch[p][0], ch[p][1]);
rev[ch[p][0]] ^= 1;
rev[ch[p][1]] ^= 1;
}
if (ch[p][0] != 0) {
print(ch[p][0]);
}
if (p != 0 && v[p] != 0 && v[p] != n + 1) {
printf("%d ", v[p]);
}
if (ch[p][1] != 0) {
print(ch[p][1]);
}
}
int main() {
int m;
scanf("%d %d", &n, &m);
root = build(0, n + 1, 0);
for (int l, r, i = 1; i <= m; i++) {
scanf("%d %d", &l, &r);
Splay(Find(l - 1), 0);
Splay(Find(r + 1), root);
rev[ch[ch[root][1]][0]] ^= 1;
}
print();
return 0;
}
样例过了,WA 成 0 分。