题目链接:https://www.acwing.com/problem/content/2439/
解题思路:
翻转,加懒惰标记
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
mt19937 rng(time(0));
struct Node {
int ls, rs, key, pri, sz;
bool flag;
Node() {}
Node(int _key) { ls = rs = 0; key = _key; pri = rng(); sz = 1; flag = false; }
} tr[maxn];
int rt, idx;
void push_up(int u) {
int ls = tr[u].ls, rs = tr[u].rs;
tr[u].sz = tr[ls].sz + tr[rs].sz + 1;
}
void push_down(int u) {
if (tr[u].flag) {
int ls = tr[u].ls, rs = tr[u].rs;
if (ls) {
tr[ls].flag ^= 1;
swap(tr[ls].ls, tr[ls].rs);
}
if (rs) {
tr[rs].flag ^= 1;
swap(tr[rs].ls, tr[rs].rs);
}
tr[u].flag = false;
}
}
void split(int u, int rk, int &L, int &R) {
if (!u) {
L = R = 0;
return;
}
push_down(u);
int ls = tr[u].ls;
if (tr[ls].sz + 1 <= rk) {
L = u;
split(tr[u].rs, rk - tr[ls].sz - 1, tr[u].rs, R);
}
else {
R = u;
split(tr[u].ls, rk, L, tr[u].ls);
}
push_up(u);
}
int merge(int L, int R) {
if (!L || !R) return L + R;
push_down(L);
push_down(R);
if (tr[L].pri > tr[R].pri) {
tr[L].rs = merge(tr[L].rs, R);
push_up(L);
return L;
}
else {
tr[R].ls = merge(L, tr[R].ls);
push_up(R);
return R;
}
}
int build(int l, int r) {
if (l > r) return 0;
int u = ++idx;
int mid = (l + r) / 2;
tr[u] = Node(mid);
tr[u].ls = build(l, mid-1);
tr[u].rs = build(mid+1, r);
push_up(u);
return u;
}
void output(int u) {
if (!u) return;
push_down(u);
output(tr[u].ls);
printf("%d ", tr[u].key);
output(tr[u].rs);
}
int n, m;
void rev(int l, int r) {
int L, p, R;
split(rt, l-1, L, R);
split(R, r-l+1, p, R);
assert(p);
swap(tr[p].ls, tr[p].rs);
tr[p].flag ^= 1;
R = merge(p, R);
rt = merge(L, R);
}
int main() {
scanf("%d%d", &n, &m);
rt = build(1, n);
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
rev(l, r);
}
output(rt);
return 0;
}