文艺平衡树

题目大意:维护一个支持区间翻转的数据结构,在所有操作结束后输出最后的序列

有生之年第一次写平衡树系列

代码十分的丑

压行是个坏习惯嗯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
int n,q,x,y,lazy[1000000],l[1000000],r[1000000],fa[1000000],de[1000000];
int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=1,kk=0;if (c=='-')k=-1,c=getchar();
while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return k*kk;
}void pushdown(int d){
swap(l[d],r[d]);lazy[l[d]]=!lazy[l[d]];lazy[r[d]]=!lazy[r[d]];lazy[d]=lazy[0]=0;
}void zigzag(int d){
if (l[fa[d]]==d){
int k=fa[fa[d]];if (l[k]==fa[d])l[k]=d;else r[k]=d;
fa[fa[d]]=d;l[fa[d]]=r[d];fa[r[d]]=fa[d];r[d]=fa[d];
de[fa[d]]=de[l[fa[d]]]+de[r[fa[d]]]+1;fa[d]=k;de[d]=de[l[d]]+de[r[d]]+1;
}else{
int k=fa[fa[d]];if (l[k]==fa[d])l[k]=d;else r[k]=d;
fa[fa[d]]=d;r[fa[d]]=l[d];fa[l[d]]=fa[d];l[d]=fa[d];
de[fa[d]]=de[l[fa[d]]]+de[r[fa[d]]]+1;fa[d]=k;de[d]=de[l[d]]+de[r[d]]+1;
}
}void splay(int x,int y){
if (lazy[fa[x]])pushdown(fa[x]);if (lazy[x])pushdown(x);
if (fa[fa[x]]!=y&&!(l[fa[fa[x]]]==fa[x]&&l[fa[x]]==x||r[fa[fa[x]]]==fa[x]&&r[fa[x]]==x))zigzag(fa[x]);
if (fa[x]!=y)zigzag(x);
}void putit(int x){
int d=0;de[x]=1;l[x]=r[x]=900000;while (1){
de[d]+=de[x];
if (x<d){if (l[d]==900000){l[d]=x;fa[x]=d;return;}d=l[d];}
else{if (r[d]==900000){r[d]=x;fa[x]=d;return;}d=r[d];}
}
}void upit(int x,int ffa){
while (fa[x]!=ffa)splay(x,ffa);
}void outit(int x){
if (lazy[x])pushdown(x);if (l[x])outit(l[x]);
if (x-1>=1&&x-1<=n)cout<<x-1<<' ';if (r[x])outit(r[x]);
}int findit(int d,int k){
if (lazy[d])pushdown(d);
if (k<=de[l[d]])return findit(l[d],k);k-=de[l[d]];
if (d)k--;if (!k)return d;return findit(r[d],k);
}
signed main(){
n=read();q=read();l[0]=r[0]=900000;
for (int i=0;i<=n+1;i++)putit(i+1),upit(i+1,0);
while (q--){
x=read();y=read();x=findit(0,x);y=findit(0,y+2);
upit(x,0);upit(y,x);lazy[l[r[x]]]=!lazy[l[r[x]]];//outit(0);cout<<endl;
}outit(0);cout<<endl;
}
分享到