平衡树

SBT

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
#define dbg(x) cout<<#x<<"="<<x<<'\n'
#define mmt memset
#define sf sizeof
#define nl NULL
int data[200000],s[200000],le[200000],ri[200000];
int tot=0,root=0,n;
void r(int &now)
{
R int tmp=le[now];
le[now]=ri[tmp];
ri[tmp]=now;s[tmp]=s[now];
s[now]=s[le[now]]+s[ri[now]]+1;
now=tmp;
}
void l(int &now)
{
R int tmp=ri[now];
ri[now]=le[tmp];
le[tmp]=now;s[tmp]=s[now];
s[now]=s[ri[now]]+s[le[now]]+1;
now=tmp;
}
void mt(int &now,bool flag)
{
if(!flag)
{
if(s[le[le[now]]]>s[ri[now]])r(now);
else if(s[ri[le[now]]]>s[ri[now]])l(le[now]),r(now);
else return;
}
else
{
if(s[ri[ri[now]]]>s[le[now]])l(now);
else if(s[le[ri[now]]]>s[le[now]])r(ri[now]),l(now);
else return;
}
mt(le[now],0);mt(ri[now],1);
mt(now,0);mt(now,1);
}
void insert(int &now,int x)
{
if(!now)
{
now=++tot;
data[now]=x;s[now]=1;
return;
}
s[now]++;
if(x<data[now])insert(le[now],x);
else insert(ri[now],x);//相同元素插入到右子树中
mt(now,x>=data[now]);
}
int del(int &now,int x)
{
int res;s[now]--;
if((x==data[now])||(x<data[now]&&!le[now])||(x>data[now]&&!ri[now]))
{
res=data[now];
if(!le[now]||!ri[now])now=le[now]+ri[now];
else data[now]=del(le[now],data[now]+1);
return res;
}
if(x<data[now])return del(le[now],x);
else return del(ri[now],x);
}

int getmin()
{
R int now=root;
while(le[now])now=le[now];
return data[now];
}
int getmax()
{
R int now=root;
while(ri[now])now=ri[now];
return data[now];
}
int pred(int &now,int y,int x)
{
if(!now)return y;
if(data[now]<x)return pred(ri[now],data[now],x);
else return pred(le[now],y,x);
}
int succ(int &now,int y,int x)
{
if(!now)return y;
if(data[now]>x)return succ(le[now],data[now],x);
else return succ(ri[now],y,x);
}
int kth(int &p,int x)
{
if(x==s[le[p]]+1)return data[p];
if(x<=s[le[p]])return kth(le[p],x);
else return kth(ri[p],x-1-s[le[p]]);
}
int rank(int &now,int x)
{
if(!now)return 1;
if(x<=data[now])return rank(le[now],x);
else return rank(ri[now],x)+s[le[now]]+1;
return s[le[now]]+1;
}
int main()
{
scanf("%d",&n);
fo(i,1,n)
{
R int odd,x;
scanf("%d%d",&odd,&x);
if(odd==1)insert(root,x);
else if(odd==2)del(root,x);
else if(odd==3)printf("%d\n",rank(root,x));
else if(odd==4)printf("%d\n",kth(root,x));
else if(odd==5)printf("%d\n",pred(root,0,x));
else printf("%d\n",succ(root,0,x));
}
return 0;
}

替罪羊树

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define R register
#define fo(a,b,c) for(R int a=b;a<=c;++a)
#define maxn 500010
const double alp=0.75;
int n,lc[maxn],rc[maxn],ex[maxn],s[maxn];
int ct[maxn],root,god,v[maxn],st[maxn],tp,q[maxn],t1;
void dfs(int rt)
{
if(!rt)return;
if(lc[rt])dfs(lc[rt]);
if(ex[rt])q[++t1]=rt;
else st[++tp]=rt;
if(rc[rt])dfs(rc[rt]);
}
void build(int &rt,int l,int r)
{
R int mid=(l+r)>>1;
rt=q[mid];
if(l==r)
{
s[rt]=ct[rt]=1;
lc[rt]=rc[rt]=0;
return;
}
if(l<mid)build(lc[rt],l,mid-1);
else lc[rt]=0;
build(rc[rt],mid+1,r);
s[rt]=s[lc[rt]]+s[rc[rt]]+1;
ct[rt]=ct[lc[rt]]+ct[rc[rt]]+1;
}
void rebuild(int &rt)
{
t1=0;
dfs(rt);
if(t1)build(rt,1,t1);
}
void ins(int &rt,int x)
{
if(rt==0)
{
rt=st[tp--];v[rt]=x;
s[rt]=ct[rt]=ex[rt]=1;
lc[rt]=rc[rt]=0;
return;
}
s[rt]++;ct[rt]++;
if(x<=v[rt])ins(lc[rt],x);
else ins(rc[rt],x);
if(1.0*s[rt]*alp>1.0*max(s[lc[rt]],s[rc[rt]]))
{
if(god)
{
if(lc[rt]==god)rebuild(lc[rt]);
else rebuild(rc[rt]);
god=0;
}
}
else god=rt;
}
void del(int &rt,int x)
{
if(ex[rt]&&x==s[lc[rt]]+1){ex[rt]=0;s[rt]--;return;}
s[rt]--;
if(x<=s[lc[rt]]+ex[rt])del(lc[rt],x);
else del(rc[rt],x-(s[lc[rt]]+ex[rt]));
}
int rak(int x)
{
R int now=root,ans=1;
while(now)
if(v[now]>=x)now=lc[now];
else ans+=s[lc[now]]+ex[now],now=rc[now];
return ans;
}
int kth(int x)
{
R int now=root;
while(now)
{
if(ex[now]&&x==s[lc[now]]+1)return v[now];
else if(s[lc[now]]>=x)now=lc[now];
else x-=s[lc[now]]+ex[now],now=rc[now];
}
}
void delval(int val)
{
del(root,rak(val));
if(1.0*s[root]<1.0*alp*ct[root])rebuild(root);
}

int main()
{
scanf("%d",&n);
for(int i=400000;i;--i)st[++tp]=i;
while(n--)
{
R int odd,x;
scanf("%d%d",&odd,&x);
if(odd==1)ins(root,x);
else if(odd==2)delval(x);
else if(odd==3)printf("%d\n",rak(x));
else if(odd==4)printf("%d\n",kth(x));
else if(odd==5)printf("%d\n",kth(rak(x)-1));
else printf("%d\n",kth(rak(x+1)));
}
return 0;
}

Splay

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define R register
#define ll long long
#define il inline
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
#define dbg(x) cout<<#x<<"="<<x<<'\n'
#define mmt(x,y) memset(x,y,sizeof(x))
#define maxn 100010
int n,m,t[maxn],ch[maxn][2],fa[maxn],rt,tot,siz[maxn],l,r,laz[maxn];
int get(int x){return ch[fa[x]][1]==x;}
void pushdown(int x)
{
if(!x||!laz[x])return;
laz[ch[x][0]]^=1;
laz[ch[x][1]]^=1;
swap(ch[x][0],ch[x][1]);
laz[x]=0;
}
void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
void rotate(int x)
{
R int f1=fa[x],f2=fa[f1];
pushdown(f2);pushdown(f1);pushdown(x);
R int pd=get(x);
if(f2)ch[f2][get(f1)]=x;
fa[x]=f2;
ch[f1][pd]=ch[x][pd^1];
fa[ch[f1][pd]]=f1;
ch[x][pd^1]=f1;
fa[f1]=x;pushup(f1);pushup(x);
}
void splay(int x,int k)
{
while(fa[x]!=k)
{
R int f1=fa[x],f2=fa[f1];
if(f2!=k)
{
if((ch[f2][0]==f1)^(ch[f1][0]==x))rotate(x);
else rotate(f1);
}
rotate(x);
}
if(!k)rt=x;
}
void insert(int &x,int sum,int last)
{
if(!x){x=++tot;siz[x]=1;t[x]=sum;fa[x]=last;splay(x,0);return;}
insert(ch[x][sum>t[x]],sum,x);
}
int find(int x,int sum)
{
pushdown(x);
if(siz[ch[x][0]]>=sum)return find(ch[x][0],sum);
else if(sum>siz[ch[x][0]]+1)return find(ch[x][1],sum-1-siz[ch[x][0]]);
else return x;
}
void print(int x)
{
if(!x)return;
pushdown(x);
print(ch[x][0]);
if(t[x]>0&&t[x]<n+1)printf("%d ",t[x]);
print(ch[x][1]);
}
int main()
{
scanf("%d%d",&n,&m);
fo(i,0,n+1)insert(rt,i,0);
while(m--)
{
scanf("%d%d",&l,&r);
l=find(rt,l);r=find(rt,r+2);
splay(l,0);splay(r,l);
laz[ch[r][0]]^=1;
}
print(rt);
return 0;
}
显示 Gitment 评论