Semorius @ 2021-11-19 11:46:48
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100005;
int n, m, tot, root;
int ch[SIZE][2], size[SIZE], val[SIZE], rnd[SIZE];
bool tag[SIZE];
int X, Y, Z;
inline int rd(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1)+(x<<3)+(ch^48);
ch = getchar();
}
return x*f;
}
void pushup(int p){
size[p] = size[ch[p][0]] + size[ch[p][1]] + 1;
}
void pushdown(int p){
if(tag[p]){
swap(ch[p][0], ch[p][1]);
if(ch[p][0]) tag[ch[p][0]] ^= 1;
if(ch[p][1]) tag[ch[p][1]] ^= 1;
tag[p] = 0;
}
}
int New(int x){
ch[++tot][0] = ch[tot][1] = 0;
size[tot] = 1; val[tot] = x;
rnd[tot] = rand();
return tot;
}
void split(int now, int k, int &x, int &y){
if(!now) x = y = 0;
else{
pushdown(now);
if(val[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y);
else y = now, split(ch[now][0], k, x, ch[now][0]);
pushup(now);
}
}
int merge(int A, int B){
if(!A || !B) return A + B;
if(rnd[A] < rnd[B]){
pushdown(A);
ch[A][1] = merge(ch[A][1], B);
pushup(A);
return A;
}
else{
pushdown(B);
ch[B][0] = merge(A, ch[B][0]);
pushup(B);
return B;
}
}
void change(int l, int r){
split(root, r, X, Y);
split(X, l-1, Z, X);
tag[X] ^= 1;
root = merge(merge(Z, X), Y);
}
void Print(int p){
if(!p) return;
if(tag[p]) pushdown(p);
Print(ch[p][0]);
printf("%d ", val[p]);
Print(ch[p][1]);
}
int main(){
srand(time(0));
n = rd(), m = rd();
for(int i = 1; i <= n; i++){
root = merge(root, New(i));
}
for(int i = 1; i <= m; i++){
int l = rd(), r = rd();
change(l, r);
}
Print(root);
return 0;
}
/*
5 10
1 3
2 4
1 5
2 3
3 5
1 2
2 3
3 4
1 3
1 5
*/
by jerry3128 @ 2021-11-19 11:50:43
是有pushdown的时候才交换的一种实现方式,没有问题。
不常见,原因是容易炸,容易出锅。
by Semorius @ 2021-11-19 11:52:55
所以要怎么改呢
by wwlw @ 2021-11-19 11:56:34
@shiyihangxs 你尝试 change 的时候就把儿子换了,pushdown 的时候直接 change 儿子
by w23c3c3 @ 2021-11-19 12:06:34
change 的时候应该按 rank split 吧。
by Semorius @ 2021-11-19 12:07:12
@wwlw 好像不是pushdown的问题,换成排名分裂就过了
by wwlw @ 2021-11-19 12:08:27
按权值 split 有什么问题吗 /jk
by Semorius @ 2021-11-19 12:08:33
所以什么时候用权值,什么时候用排名
by Semorius @ 2021-11-19 12:09:07
感觉也没啥问题
by wwlw @ 2021-11-19 12:13:16
草,肯定不能按权值 split,权值都变了