平衡树
\(\tt{Treap}\)
&
\(\tt{Splay}\)
壹.单旋
\(\tt{Treap}\)
首先了解
\(\tt{BST}\)
非常好用的东西,但是数据可以把它卡成一条链
\(\dots\)
于是,我们将
\(\tt{Tree}\)
与
\(\tt{heap}\)
(堆) 合并,以保证平衡树
\(\log\)
的深度。
具体地,我们可以使用旋转操作实现
K8He的图
以右旋为例,我们发现,本来的中序遍历顺序为
\(y
,那么对于
\(q\)
右旋,即将左儿子旋上来,由于本来
\(p
,所以显然
\(q\)
要成为
\(p\)
的右儿子。那就剩下
\(x\)
无家可归,我们发现
\(p
,那么
\(q\)
的左儿子再适合不过了。
我们规定
\(0\)
方向为左,
\(1\)
方向为右,即可通过
\(d\)
^
\(1\)
实现方向取反。
一般的,对于一个节点
\(i\)
,如果将其
\(d\)
方向上的儿子
\(s\)
旋上去,那么
\(i\)
要成为
\(s\)
在
\(d\)
^
\(1\)
方向上的儿子,
\(s\)
原来在
\(d\)
^
\(1\)
方向上的儿子要成为
\(i\)
在
\(d\)
方向上的儿子。
void rotate(int &i,int d){
int s=t[i].son[d];
t[i].son[d]=t[s].son[d^1];
t[s].son[d^1]=i;
up(i),i=s,up(i);
return;
}
那么我们什么时候进行旋转呢?还记得我们说过要利用堆的性质,那么我们对每个节点随机一个优先级,将它按照小根堆或大根堆存,若当前不满足堆的性质了,那就旋转。
-
插入操作,从根往下跑,但要注意不满足堆的性质时,考虑旋转。
void insert(int &i,int k){
if(!i){
i=++tot;
t[i].cnt=t[i].siz=1;
t[i].val=k,t[i].rd=rnd();
return;
}
t[i].siz++;
if(t[i].val==k){
++t[i].cnt;return;
}
int d=(t[i].valt[t[i].son[d]].rd) rotate(i,d);
return;
}
-
删除操作,先找节点,如果只有一个儿子,让儿子替换它,否则让儿子旋上来(当然要满足堆性质),然后一直旋,直到剩一个儿子或者成为叶子节点。
void del(int &i,int k){
if(!i) return;
if(t[i].val==k){
if(t[i].cnt>1){
--t[i].cnt,--t[i].siz;
return;
}
int d=(t[ls(i)].rd>t[rs(i)].rd);
if(!ls(i)||!rs(i)) i=ls(i)+rs(i);
else rotate(i,d),del(i,k);
return;
}
t[i].siz--;
int d=t[i].val
int rk(int i,int k){
if(!i) return 1;
if(t[i].val>k) return rk(ls(i),k);
if(t[i].val
int kth(int i,int k){
while(1){
if(k<=t[ls(i)].siz) i=ls(i);
else if(k>t[ls(i)].siz+t[i].cnt)
k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
else return t[i].val;
}
}
-
前驱后继,和普通
\(\tt{BST}\)
一样。
int pre(int i,int k){
if(!i) return -1e8;
if(t[i].val>=k) return pre(ls(i),k);
return max(pre(rs(i),k),t[i].val);
}
int nex(int i,int k){
if(!i) return 1e8;
if(t[i].val<=k) return nex(rs(i),k);
return min(nex(ls(i),k),t[i].val);
}
对于单旋
\(\tt{Treap}\)
,我们只需要理解旋转操作即可,毕竟下面的
\(\tt{Splay}\)
还要用它,请务必看懂旋转操作,其他的,
还是FHQ好打,
差不多看看就行,应用范围不大。
(板子封装在下面题单
普通平衡树
里)
贰.无旋
\(\tt{FHQ\ Treap}\)
由于单旋
\(\tt{Treap}\)
不好打且扩展功能不多,所以我们引入新的
\(\tt{FHQ\_ Treap}\)
,好像是神范浩强发明的,%%%%%%。
网上都说FHQ比单旋好理解,我表示理解了之后确实好理解,但你得先理解(我看了一个多小时才看懂,不过我是fw)
好那么直入正题 ——
\(\tt{FHQ\_ Treap}\)
既然也是
\(\tt{Treap}\)
,那就是一样的,也是靠堆性质,它的不同之处就在于,它无旋,它是靠
分裂+合并
来保证
\(\log\)
的深度。
具体地,分裂方式有两种,一种是按权值分裂,另一种是按照子树大小分裂:
-
按照权值分裂,比如将以
\(i\)
为根的平衡树分成两棵平衡树,根分别是
\(x,y\)
,要求树
\(x\)
的权值都小于等于
\(k\)
,剩下是
\(y\)
,那么分讨:
-
如果
\(val(i)<=k\)
,那么
\(i\)
的整棵左子树一定都小于
\(k\)
,肯定都要划到
\(x\)
里,则令
\(x=i\)
,继续递归划分
\(rs(i)\)
即可。
-
否则,
\(i\)
的整棵右子树一定都大于
\(k\)
,肯定都要划到
\(y\)
里,则令
\(y=i\)
,继续递归划分
\(ls(i)\)
即可。
注意取地址。
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(val(i)>k) y=i,split(ls(i),k,x,ls(i));
if(val(i)<=k) x=i,split(rs(i),k,rs(i),y);
up(i);return;
}
-
按照子树大小分裂,还是将以
\(i\)
为根的平衡树分成两棵平衡树,根分别是
\(x,y\)
,要求是
\(siz(x)=k\)
,还是和上面一样:
-
如果
\(siz(ls(i))+cnt(i)<=k\)
,那么
\(i\)
的整棵左子树和
\(i\)
肯定都要划到
\(x\)
里,则令
\(x=i\)
,继续递归划分
\(rs(i)\)
即可。
-
否则,
\(i\)
的整棵右子树肯定都要划到
\(y\)
里,则令
\(y=i\)
,继续递归划分
\(ls(i)\)
即可。
按子树大小分裂,一般用在平衡树维护序列,后面的
\(\tt{Splay}\)
也是一样。
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(siz(ls(i))+cnt(i)<=k) x=i,split(rs(i),k-(siz(ls(i))+cnt(i)),rs(i),y);
else y=i,split(ls(i),k,x,ls(i));
up(i);
}
-
下一个操作是合并,
\(\tt{FHQ\_ Treap}\)
正是通过它保证的堆性质,设要合并的两棵树的根分别为
\(x,y\)
,设堆性质为大根堆。
-
若
\(rd(x)>rd(y)\)
则把
\(x\)
定为根,然后继续递归合并
\(rs(x)\)
和
\(y\)
-
否则把
\(y\)
定为根,然后继续递归合并
\(x\)
和
\(ls(y)\)
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);return;
}
-
插入
\(k\)
,先分裂出
\(<=k-1\)
,合并时把
\(k\)
合并进去。
void insert(int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
merge(rt,rt1,New(k));merge(rt,rt,rt2);
return;
}
-
删除
\(k\)
,把
\(k\)
分裂出来,然后把
\(k\)
用它的左右子树合并替代,再合并。
void del(int k){
int rt1,rt2,cut;
split(rt,k-1,rt1,rt2);split(rt2,k,cut,rt2);
merge(cut,ls(cut),rs(cut));
merge(rt,rt1,cut);merge(rt,rt,rt2);
return;
}
-
查排名,分裂完
\(\leq k-1\)
的树大小
\(+1\)
int rk(int i,int k){
int rt1,rt2,res;
split(i,k-1,rt1,rt2);
res=siz(rt1)+1;
merge(i,rt1,rt2);
return res;
}
int pre(int &i,int k){
int rt1,rt2,res;
split(i,k-1,rt1,rt2),res=rt1;
while(rs(res)) res=rs(res);
merge(i,rt1,rt2);
return val(res);
}
int nxt(int &i,int k){
int rt1,rt2,res;
split(i,k,rt1,rt2),res=rt2;
while(ls(res)) res=ls(res);
merge(i,rt1,rt2);
return val(res);
}
(板子封装在下面题单
普通平衡树
里)
叁.双旋
\(\tt{Splay}\)
\(\tt{Splay}\)
不同于以上两种
\(\tt{Treap}\)
,它不再依靠随机的优先级保证深度,而是通过不断旋转来达到目的。
类似于单旋,只不过单旋是将某节点的儿子旋上来,而
\(\tt{Splay}\)
是将某节点自身旋上去,单次旋转和
\(\tt{Treap}\)
一样,但是要多记录一个父亲
具体地,旋转
\(x\)
时,令
\(y\)
为
\(x\)
的父亲,
\(z\)
为祖父,设
\(x\)
为
\(y\)
在
\(d\)
方向上的儿子,则单次旋转可分为这几步:
-
\(x\)
替换
\(y\)
成为
\(z\)
的儿子
-
\(x\)
在
\(d\)
^
\(1\)
方向的儿子下放给
\(y\)
当
\(d\)
方向的儿子
-
\(y\)
充当
\(x\)
在
\(d\)
^
\(1\)
方向的儿子
三次修改,三次认爹,
rotate
就写完了
#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1]
void rotate(int x){
int y=fa(x),z=fa(y);
int d=(rs(y)==x);
t[z].son[(rs(z)==y)]=x;fa(x)=z;
ds(y)=bs(x);fa(bs(x))=y;
bs(x)=y;fa(y)=x;
up(y),up(x);
}
然后便是
\(\tt{Splay}\)
的核心操作,
splay
如说
具体地,
splay
操作是将节点
\(x\)
旋转到目标节点
\(s\)
的儿子,若
\(s=0\)
则为旋转到根。那么如果我们一直一直单旋上去的话我们会发现一个严重的问题——虽然
\(x\)
上去了,但是它的最大深度依然没变,也就是说,转了个寂寞。。
那么怎么办,进行双旋,讨论几种情况——(
\(x,y,z\)
意义同上)
-
\(z=s\)
直接将
\(x\)
单旋一次上去
-
\(z\not ={s}\)
此时我们应先转
\(y\)
再转
\(x\)
-
-
\(x,y,z\)
三点不共线,直接旋转两次
\(x\)
-
就这样旋旋旋,就能保证深度OK,每次插入节点后都要进行一次
Splay
void splay(int x,int s){
while(fa(x)!=s){
int y=fa(x),z=fa(y);
if(z!=s)
(ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
rotate(x);
}
if(!s) rt=x;
}
至于这么旋为什么可以让复杂度OK,使用什么
"势能分析法"
,我是fw我不会。
\(\tt{Splay}\)
与
\(\tt{FHQ}\)
一样,也是两种维护方式,一种维护权值,一种维护下标(即序列的中序遍历)。
然后就是
\(\tt{Splay}\)
的一些基本操作:
-
插入,有两种方式,即按权值和子树大小,与
\(\tt{FHQ}\)
类似,注意要记录一下父亲节点
void insert(int k){
int p=rt,f=0;
while(p&&val(p)!=k){
f=p;
p=t[p].son[val(p)
void insert(int &i,int f,int x,int k){
if(!i){
i=++tot;
siz(i)=1;fa(i)=f;val(i)=k;
return;
}
if(x<=siz(ls(i))+1) insert(ls(i),i,x,k);
else insert(rs(i),i,x-siz(ls(i))-1,k);
up(i);
}
-
对于
splay
,我们要先找到某权值对应的节点,直接找然后
splay
void find(int k){
if(!rt) return;
int p=rt;
while(t[p].son[val(p)
void find(int x){
if(!rt) return;
int p=rt;
while(siz(ls(p))+1!=x){
if(x<=siz(ls(p))+1){
p=ls(p);
}
else{
x-=(siz(ls(p))+1);
p=rs(p);
}
}
splay(p,0);
}
-
查第
\(k\)
小,与
\(\tt{Treap}\)
同理,不再赘述
-
查排名,转到根节点后左子树的大小
\(+1\)
即可
-
查前驱后继,以前驱为例,转到根之后左子树里最大值即前驱,后继同理
-
删除比较有意思,我们先找到前驱后继,然后将前驱
splay
到根,将后继
splay
到前驱的右儿子,那么要删除的节点就一定为
\(ls(rs(rt))\)
(如下图)。这也就意味着必须有前驱后继,否则删不了,那么直接插入两个极值哨兵节点即可。
pre
/ \
... nxt
/ \
cut ...
void del(int k){
int prek=pre(k);
int nxtk=nxt(k);
splay(prek,0);splay(nxtk,prek);
int cut=ls(nxtk);
if(cnt(cut)>1)
--cnt(cut),splay(cut,0);
else ls(nxtk)=0;
}
另外,维护序列的
\(\tt{Splay}\)
进行区间操作时,也是将区间转化为子树,和删除操作类似,比如
文艺平衡树
就是这样,不再赘述。
最后注意一定要插哨兵
(板子封装在下面题单
普通平衡树
里)
肆.
\(hs\)
题单
\(T_D\)
普通平衡树
由于是纯板子,所以先挂
\(T_D\)
。
普通Treap
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 100010
int m;
namespace TREAP{
mt19937 rnd(0x7f);
struct Treap{
int son[2],cnt,siz,val,rd;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
}t[N];
int tot,rt;
void up(int i){
t[i].siz=t[ls(i)].siz+t[rs(i)].siz+t[i].cnt;
}
void rotate(int &i,int d){
int s=t[i].son[d];
t[i].son[d]=t[s].son[d^1];
t[s].son[d^1]=i;
up(i),i=s,up(i);
return;
}
void insert(int &i,int k){
if(!i){
i=++tot;
t[i].cnt=t[i].siz=1;
t[i].val=k,t[i].rd=rnd();
return;
}
t[i].siz++;
if(t[i].val==k){
++t[i].cnt;return;
}
int d=(t[i].valt[t[i].son[d]].rd) rotate(i,d);
return;
}
void del(int &i,int k){
if(!i) return;
if(t[i].val==k){
if(t[i].cnt>1){
--t[i].cnt,--t[i].siz;
return;
}
int d=(t[ls(i)].rd>t[rs(i)].rd);
if(!ls(i)||!rs(i)) i=ls(i)+rs(i);
else rotate(i,d),del(i,k);
return;
}
t[i].siz--;
int d=t[i].valk) return rk(ls(i),k);
if(t[i].valt[ls(i)].siz+t[i].cnt)
k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
else return t[i].val;
}
}
int pre(int i,int k){
if(!i) return -1e8;
if(t[i].val>=k) return pre(ls(i),k);
return max(pre(rs(i),k),t[i].val);
}
int nex(int i,int k){
if(!i) return 1e8;
if(t[i].val<=k) return nex(rs(i),k);
return min(nex(ls(i),k),t[i].val);
}
} using namespace TREAP;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
m=read;
int op,x;
while(m-->0){
op=read,x=read;
switch(op){
case 1:
insert(rt,x);break;
case 2:
del(rt,x);break;
case 3:
write(rk(rt,x));pt;break;
case 4:
write(kth(rt,x));pt;break;
case 5:
write(pre(rt,x));pt;break;
case 6:
write(nex(rt,x));pt;break;
}
}
return 0;
}
FHQ_Treap
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N=1e5+10;
namespace FHQ_TREAP{
struct Treap{
int son[2],rd,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define rd(i) t[i].rd
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=cnt(i)+siz(ls(i))+siz(rs(i));
}
int New(int k){
val(++tot)=k;
cnt(tot)=siz(tot)=1;
rd(tot)=rand();
return tot;
}
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(val(i)>k) y=i,split(ls(i),k,x,ls(i));
if(val(i)<=k) x=i,split(rs(i),k,rs(i),y);
up(i);return;
}
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);return;
}
void insert(int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
merge(rt,rt1,New(k));merge(rt,rt,rt2);
return;
}
void del(int k){
int rt1,rt2,cut;
split(rt,k-1,rt1,rt2);split(rt2,k,cut,rt2);
merge(cut,ls(cut),rs(cut));
merge(rt,rt1,cut);merge(rt,rt,rt2);
return;
}
int rk(int i,int k){
int rt1,rt2,res;
split(i,k-1,rt1,rt2);
res=siz(rt1)+1;
merge(i,rt1,rt2);
return res;
}
int kth(int i,int k){
while(1){
if(k<=siz(ls(i))) i=ls(i);
else if(k>siz(ls(i))+cnt(i))
k-=(siz(ls(i))+cnt(i)),i=rs(i);
else return val(i);
}
}
int pre(int &i,int k){
int rt1,rt2,res;
split(i,k-1,rt1,rt2),res=rt1;
while(rs(res)) res=rs(res);
merge(i,rt1,rt2);
return val(res);
}
int nxt(int &i,int k){
int rt1,rt2,res;
split(i,k,rt1,rt2),res=rt2;
while(ls(res)) res=ls(res);
merge(i,rt1,rt2);
return val(res);
}
} using namespace FHQ_TREAP;
int m;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
srand(time(0));
m=read;
int op,x;
while(m-->0){
op=read,x=read;
switch(op){
case 1:
insert(x);
break;
case 2:
del(x);
break;
case 3:
write(rk(rt,x));pt;
break;
case 4:
write(kth(rt,x));pt;
break;
case 5:
write(pre(rt,x));pt;
break;
case 6:
write(nxt(rt,x));pt;
break;
default:break;
}
}
return 0;
}
Splay
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n;
namespace SPLAY{
struct Splay_Tree{
int son[2],fa,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1]
#define fa(i) t[i].fa
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
void rotate(int x){
int y=fa(x),z=fa(y);
int d=(rs(y)==x);
t[z].son[(rs(z)==y)]=x;fa(x)=z;
ds(y)=bs(x);fa(bs(x))=y;
bs(x)=y;fa(y)=x;
up(y),up(x);
}
void splay(int x,int s){
while(fa(x)!=s){
int y=fa(x),z=fa(y);
if(z!=s)
(ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
rotate(x);
}
if(!s) rt=x;
}
void find(int k){
if(!rt) return;
int p=rt;
while(t[p].son[val(p)k) return p;
p=rs(p);while(ls(p)) p=ls(p);
return p;
}
void del(int k){
int prek=pre(k);
int nxtk=nxt(k);
splay(prek,0);splay(nxtk,prek);
int cut=ls(nxtk);
if(cnt(cut)>1)
--cnt(cut),splay(cut,0);
else ls(nxtk)=0;
}
int kth(int k){
int i=rt;
if(siz(i)siz(ls(i))+cnt(i))
k-=(siz(ls(i))+cnt(i)),i=rs(i);
else return val(i);
}
}
} using namespace SPLAY;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
insert(-1e8);insert(1e8);
int op,x;
for(int i=1;i<=n;i++){
op=read,x=read;
switch(op){
case 1:
insert(x);break;
case 2:
del(x);break;
case 3:
find(x);
write(siz(ls(rt))),pt;break;
case 4:
write(kth(x+1)),pt;break;
case 5:
write(val(pre(x))),pt;break;
case 6:
write(val(nxt(x))),pt;break;
default:
break;
}
}
return 0;
}
\(T_A\)
营业额统计
板子,求前驱后继。
普通Treap
#include
using namespace std;
#define inf 1e10
#define int long long
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N=(1<<15)+10;
int n;
int a;
int ans;
namespace TREAP{
mt19937 Rand(0x7f);
int tot,rt;
struct Treap{
int son[2],val,rd;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define val(i) t[i].val
#define rd(i) t[i].rd
}t[N];
void rotate(int &i,int d){
int s=t[i].son[d];
t[i].son[d]=t[s].son[d^1];
t[s].son[d^1]=i;
i=s;
return;
}
void insert(int &i,int k){
if(!i){
i=++tot;
val(i)=k;rd(i)=Rand();
return;
}
if(val(i)==k){
return;
}
int d=(val(i)rd(t[i].son[d])) rotate(i,d);
}
int pre(int i,int k){
if(!i) return -inf;
if(val(i)>k) return pre(ls(i),k);
return max(val(i),pre(rs(i),k));
}
int nxt(int i,int k){
if(!i) return inf;
if(val(i)
FHQ_Treap
#include
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = (1<<15)+10;
namespace FHQ_TREAP{
mt19937 Rand(0x7f);
struct Treap{
int son[2],rd,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define ds(i) t[i].son[d]
#define rd(i) t[i].rd
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=cnt(i)+siz(ls(i))+siz(rs(i));
}
int New(int k){
val(++tot)=k;
cnt(tot)=siz(tot)=1;
rd(tot)=Rand();
return tot;
}
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(val(i)>k) y=i,split(ls(i),k,x,ls(i));
if(val(i)<=k) x=i,split(rs(i),k,rs(i),y);
up(i);
}
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);
}
void insert(int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
merge(rt,rt1,New(k));
merge(rt,rt,rt2);
}
int pre(int k){
int rt1,rt2;
split(rt,k,rt1,rt2);
if(!siz(rt1)) return -1e8;
int res=rt1;
while(rs(res)) res=rs(res);
merge(rt,rt1,rt2);
return val(res);
}
int nxt(int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
if(!siz(rt2)) return 1e8;
int res=rt2;
while(ls(res)) res=ls(res);
merge(rt,rt1,rt2);
return val(res);
}
} using namespace FHQ_TREAP;
int n,a;
int ans;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
a=read;
insert(a);
ans=a;
for(int i=2;i<=n;i++){
a=read;
int prea=pre(a);
int nxta=nxt(a);
ans+=min(a-prea,nxta-a);
insert(a);
}
write(ans);
return 0;
}
Splay
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n;
namespace SPLAY{
struct Splay_Tree{
int son[2],fa,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1]
#define fa(i) t[i].fa
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
void rotate(int x){
int y=fa(x),z=fa(y);
int d=(rs(y)==x);
t[z].son[(rs(z)==y)]=x;fa(x)=z;
ds(y)=bs(x);fa(bs(x))=y;
bs(x)=y;fa(y)=x;
up(y),up(x);
}
void splay(int x,int s){
while(fa(x)!=s){
int y=fa(x),z=fa(y);
if(z!=s)
(ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
rotate(x);
}
if(!s) rt=x;
}
void find(int k){
if(!rt) return;
int p=rt;
while(t[p].son[val(p)=k) return p;
p=rs(p);while(ls(p)) p=ls(p);
return p;
}
} using namespace SPLAY;
int a,ans;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
insert(-1e8);insert(1e8);
a=read;
ans=a;
insert(a);
for(int i=2;i<=n;i++){
a=read;
int prea=val(pre(a)),nxta=val(nxt(a));
ans+=min(a-prea,nxta-a);
insert(a);
}
write(ans);
return 0;
}
\(T_B\)
宠物收养所
发现某时刻的平衡树里只会全是人或者全是狗,查前驱后继即可,查完即删。
普通Treap
#include
using namespace std;
#define int long long
#define inf 1e10
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N=8*1e4+10;
const int p=1e6;
int n;
namespace TREAP{
mt19937 Rand(0x7f);
struct Treap{
int son[2],cnt,siz,val,rd;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
#define rd(i) t[i].rd
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
void rotate(int &i,int d){
int s=t[i].son[d];
t[i].son[d]=t[s].son[d^1];
t[s].son[d^1]=i;
up(i),i=s,up(i);
return;
}
void insert(int &i,int k){
if(!i){
i=++tot;
cnt(i)=siz(i)=1;
val(i)=k;rd(i)=Rand();
return;
}
siz(i)++;
if(val(i)==k){
cnt(i)++;return;
}
int d=(val(i)rd(t[i].son[d])) rotate(i,d);
return;
}
void del(int &i,int k){
if(!i) return;
if(val(i)==k){
if(cnt(i)>1){
--cnt(i),--siz(i);
return;
}
int d=(rd(ls(i))>rd(rs(i)));
if(!ls(i)||!rs(i)) i=ls(i)+rs(i);
else rotate(i,d),del(i,k);
return;
}
int d=(val(i)k) return pre(ls(i),k);
return max(val(i),pre(rs(i),k));
}
int nxt(int i,int k){
if(!i) return inf;
if(val(i)
Splay
#include
using namespace std;
#define int long long
#define inf 1e10
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 8*1e4+10;
const int p = 1e6;
int n;
namespace SPLAY{
struct Splay_Tree{
int son[2],fa,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1]
#define fa(i) t[i].fa
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
void rotate(int x){
int y=fa(x),z=fa(y);
int d=(rs(y)==x);
t[z].son[(rs(z)==y)]=x;fa(x)=z;
ds(y)=bs(x);fa(bs(x))=y;
bs(x)=y;fa(y)=x;
up(y),up(x);
}
void splay(int x,int s){
while(fa(x)!=s){
int y=fa(x),z=fa(y);
if(z!=s)
(ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
rotate(x);
}
if(!s) rt=x;
}
void insert(int k){
int p=rt,f=0;
while(p && val(p)!=k){
f=p;
p=t[p].son[val(p)k) return p;
p=rs(p);while(ls(p)) p=ls(p);
return p;
}
void del(int k){
int prek=pre(k,0),nxtk=nxt(k,0);
splay(prek,0);splay(nxtk,prek);
int cut=ls(nxtk);
if(cnt(cut)>1) --cnt(cut),splay(cut,0);
else ls(nxtk)=0;
}
}
using namespace SPLAY;
bool now;
int num[2];
int a,b;
int ans;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
insert(-inf);insert(inf);
n=read;
now=read;b=read;num[now]=1;
insert(b);
for(int i=2;i<=n;i++){
a=read,b=read;
if(!num[a^1]){
++num[a],now=a;
insert(b);
continue;
}
if(a==now){
++num[now];
insert(b);
}
else{
int preb=val(pre(b,1)),nxtb=val(nxt(b,1));
int hwr=(b-preb<=nxtb-b?preb:nxtb);
ans=(ans+abs(hwr-b))%p;
del(hwr);
--num[now];
}
}
write(ans);
return 0;
}
注意
\(Splay\)
求前驱后继时
如果要取等注意特判
,删除时不可取等(取等就寄了)
\(T_C\)
郁闷的出纳员
维护整体懒标记,每次删除低于
\(minn-add\)
线的。
-
用普通
\(\tt{Treap}\)
直接暴力删,不好打。
-
用
\(\tt{FHQ\_ Treap}\)
分裂出低于
\(minn-add\)
的部分,直接不要即可。
服了,
\(\tt{FHQ\_ Treap}\)
跑不过普通
\(\tt{Treap}\)
的暴力。。。
普通Treap
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e6;
int n,minn;
int add;
int ans,sum;
int num;
namespace TREAP{
mt19937 rnd(0x7f);
struct Treap{
int son[2],cnt,siz,val,rd;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define val(i) t[i].val
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
}t[N];
int tot,rt;
void up(int i){
t[i].siz=t[ls(i)].siz+t[rs(i)].siz+t[i].cnt;
}
void rotate(int &i,int d){
int s=t[i].son[d];
t[i].son[d]=t[s].son[d^1];
t[s].son[d^1]=i;
up(i),i=s,up(i);
return;
}
void insert(int &i,int k){
if(!i){
i=++tot;
t[i].cnt=t[i].siz=1;
t[i].val=k,t[i].rd=rnd();
return;
}
t[i].siz++;
if(t[i].val==k){
++t[i].cnt;return;
}
int d=(t[i].valt[t[i].son[d]].rd) rotate(i,d);
return;
}
void del(int &i,int k){
if(!i) return;
if(t[i].val==k){
if(t[i].cnt>1){
--t[i].cnt,--t[i].siz;
return;
}
int d=(t[ls(i)].rd>t[rs(i)].rd);
if(!ls(i)||!rs(i)) i=ls(i)+rs(i);
else rotate(i,d),del(i,k);
return;
}
t[i].siz--;
int d=(t[i].valk) return rk(ls(i),k);
if(t[i].valt[ls(i)].siz+t[i].cnt)
k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
else return t[i].val;
}
}
void dfs(int x){
if(ls(x)) dfs(ls(x));
if(rs(x)) dfs(rs(x));
if(minn-add>val(x)){
int c=cnt(x);
for(int i=1;i<=c;i++)
del(rt,val(x));
}
}
} using namespace TREAP;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read,minn=read;
char op;
int k;
for(int i=1;i<=n;i++){
cin>>op;k=read;
switch (op){
case 'I':
if(k>=minn) insert(rt,k-add),++num;
break;
case 'A':
add+=k;
break;
case 'S':
add-=k;
dfs(rt);
break;
case 'F':
if(siz(rt)
FHQ_Treap
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n,minn,add;
namespace FHQ_TREAP{
mt19937 Rand(0x7f);
struct Treap{
int son[2],rd,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define ds(i) t[i].son[d]
#define rd(i) t[i].rd
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
int New(int k){
val(++tot)=k;
siz(tot)=cnt(tot)=1;
rd(tot)=Rand();
return tot;
}
void spilt(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(val(i)>k) y=i,spilt(ls(i),k,x,ls(i));
if(val(i)<=k) x=i,spilt(rs(i),k,rs(i),y);
up(i);
}
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);
}
void insert(int k){
int rt1,rt2;
spilt(rt,k-1,rt1,rt2);
merge(rt,rt1,New(k));
merge(rt,rt,rt2);
return;
}
void del(int k){
int rt1,rt2;
spilt(rt,k-1,rt1,rt2);
rt=rt2;
}
int kth(int i,int k){
while(1){
if(k<=siz(ls(i))) i=ls(i);
else if(k>siz(ls(i))+cnt(i))
k-=(siz(ls(i))+cnt(i)),i=rs(i);
else return val(i);
}
}
} using namespace FHQ_TREAP;
int sum,ans;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read,minn=read;
char op;
int k;
for(int i=1;i<=n;i++){
cin>>op;k=read;
switch(op){
case 'I':
if(k>=minn)
insert(k-add),++sum;
break;
case 'A':
add+=k;
break;
case 'S':
add-=k;
del(minn-add);
break;
case 'F':
if(siz(rt)
\(T_E\)
文艺平衡树
平衡树不仅具有二叉搜索树的功能,同样可以支持区间操作,即,将序列的下标塞进平衡树,它的中序遍历就是原序列,然后我们想干嘛就干嘛~
对于区间翻转,考虑维护懒标记,下放时交换左右儿子,分别异或。最后中序遍历输出每个节点的值。
对于打懒标记,分裂出
\([l,r]\)
部分,一定要先分出前
\(r\)
个,再分前
\(l-1\)
个,反过来如果先分前
\(l-1\)
个,后面就应该分出
\(r-l+1\)
个,手画一下就知道为什么了。
这里使用
\(\tt{FHQ\_ Treap}\)
时,我们按子树大小进行分裂,因为我们是按照下标建的树,不能按权值分裂。
FHQ_Treap
#include
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n,m;
namespace FHQ_TREAP{
struct Treap{
int son[2],val,cnt,siz,rd,lazy;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define rd(i) t[i].rd
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
#define lazy(i) t[i].lazy
}t[N];
int tot,rt;
int New(int k){
val(++tot)=k;
cnt(tot)=siz(tot)=1;
rd(tot)=rand();
return tot;
}
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
void down(int i){
if(!lazy(i)) return;
swap(ls(i),rs(i));
lazy(ls(i))^=1;
lazy(rs(i))^=1;
lazy(i)=0;
}
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
down(i);
if(siz(ls(i))+cnt(i)<=k) x=i,split(rs(i),k-(siz(ls(i))+cnt(i)),rs(i),y);
else y=i,split(ls(i),k,x,ls(i));
up(i);
}
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) down(x),merge(rs(x),rs(x),y),i=x;
else down(y),merge(ls(y),x,ls(y)),i=y;
up(i);
}
void insert(int k){
int rt1,rt2;
split(rt,k,rt1,rt2);
merge(rt,rt1,New(k));
merge(rt,rt,rt2);
}
void out(int i){
down(i);
if(ls(i)) out(ls(i));
write(val(i));putchar(' ');
if(rs(i)) out(rs(i));
}
} using namespace FHQ_TREAP;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
srand(time(0));
n=read,m=read;
for(int i=1;i<=n;i++) insert(i);
int l,r,rt1,rt2,rt3;
for(int i=1;i<=m;i++){
l=read,r=read;
rt1=rt2=rt3=0;
split(rt,r,rt1,rt3);
split(rt1,l-1,rt1,rt2);
lazy(rt2)^=1;
merge(rt1,rt1,rt2);
merge(rt,rt1,rt3);
// split(rt,l-1,rt1,rt2);
// split(rt2,r-l+1,rt2,rt3);
// lazy(rt2)^=1;
// merge(rt2,rt2,rt3);
// merge(rt,rt1,rt2);
}
out(rt);
return 0;
}
对于
\(\tt{Splay}\)
,其实是差不多的,我们都是将区间转到一棵子树上进行打标记,类似于删除操作,我们将
\(l-1\)
转到根,将
\(r+1\)
转到根的儿子,那么
\(ls(rs(rt))\)
的子树就是区间
\([l,r]\)
,然后和
\(\tt{FHQ}\)
一样。
我的代码比较排斥
\(0\)
,所以我干脆将整体
\(+1\)
,最后答案
\(-1\)
输出。
Splay
#include
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n,m;
namespace SPLAY{
struct Splay_Tree{
int son[2],fa,lazy,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1]
#define fa(i) t[i].fa
#define lazy(i) t[i].lazy
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+1;
}
void down(int i){
if(!lazy(i)) return;
lazy(i)=0;
swap(ls(i),rs(i));
lazy(ls(i))^=1,lazy(rs(i))^=1;
}
void rotate(int x){
int y=fa(x),z=fa(y);
int d=(rs(y)==x);
t[z].son[rs(z)==y]=x;fa(x)=z;
ds(y)=bs(x);fa(bs(x))=y;
bs(x)=y;fa(y)=x;
up(y),up(x);
}
void splay(int x,int s){
while(fa(x)!=s){
down(x);
int y=fa(x),z=fa(y);
if(z!=s)
(ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
rotate(x);
}
if(!s) rt=x;
}
int find(int k){
if(!rt) return 0;
int p=rt;
while(siz(ls(p))+1!=k){
if(k<=siz(ls(p)))
p=ls(p);
else{
k-=(siz(ls(p))+1);
p=rs(p);
}
down(p);
}
return p;
}
void insert(int &i,int f,int x,int k){
if(!i){
i=++tot;
siz(i)=1;fa(i)=f;val(i)=k;
return;
}
if(x<=siz(ls(i))+1) insert(ls(i),i,x,k);
else insert(rs(i),i,x-siz(ls(i))-1,k);
up(i);
}
void out(int i){
down(i);
if(ls(i)) out(ls(i));
if(val(i)>1&&val(i)<=n+1)
write(val(i)-1),putchar(' ');
if(rs(i)) out(rs(i));
}
} using namespace SPLAY;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read,m=read;
insert(rt,0,1,1);
for(int i=1;i<=n;i++){
insert(rt,0,i+1,i+1);
splay(tot,0);
}
insert(rt,0,n+2,n+2);
int l,r;
for(int i=1;i<=m;i++){
l=read+1,r=read+1;
splay(find(l-1),0);
splay(find(r+1),rt);
int p=ls(rs(rt));
lazy(p)^=1;
}
out(rt);
return 0;
}
\(T_F\)
二逼平衡树
线段树套平衡树板子。
-
首先建立普通线段树,对于每个区间建一棵平衡树。
-
对于
\(x\)
区间内排名,转化成查找区间内比它小的树的个数加
\(1\)
,分裂求。
-
对于第
\(k\)
小数,考虑二分,通过操作
\(1\)
检查
-
单点修改直接从根节点跑到叶子,路过的每个节点都要删掉原数,插入新数。注意要修改原序列。
-
前驱后继直接分别查区间内每个小区间,取极值即可。
由于难写难调,只打了 FHQ_Treap
FHQ_Treap
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 5*1e4+10;
const int inf = 2147483647;
int n,a[N],m;
int MIN=inf,MAX=-inf;
namespace FHQ_TREAP{
struct Treap{
int son[2],rd,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define rd(i) t[i].rd
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N<<6];
int tot;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
int New(int k){
val(++tot)=k;
siz(tot)=cnt(tot)=1;
rd(tot)=rand();
return tot;
}
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(val(i)<=k) x=i,split(rs(i),k,rs(i),y);
else y=i,split(ls(i),k,x,ls(i));
up(i);
}
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);
}
void insert(int &rt,int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
merge(rt,rt1,New(k));
merge(rt,rt,rt2);
}
void del(int &rt,int k){
int rt1,rt2,cut;
split(rt,k,rt1,rt2);
split(rt1,k-1,rt1,cut);
merge(cut,ls(cut),rs(cut));
merge(rt1,rt1,cut);
merge(rt,rt1,rt2);
}
int sumless(int rt,int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
int res=siz(rt1);
merge(rt,rt1,rt2);
return res;
}
int pre(int rt,int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
if(!siz(rt1)) return -inf;
int res=rt1;
while(rs(res)) res=rs(res);
merge(rt,rt1,rt2);
return val(res);
}
int nxt(int rt,int k){
int rt1,rt2;
split(rt,k,rt1,rt2);
if(!siz(rt2)) return inf;
int res=rt2;
while(ls(res)) res=ls(res);
merge(rt,rt1,rt2);
return val(res);
}
#undef ls
#undef rs
};
using namespace FHQ_TREAP;
namespace Segment_Tree{
struct SegTree{
int l,r,rt;
#define l(i) tr[i].l
#define r(i) tr[i].r
#define rt(i) tr[i].rt
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
}tr[N<<2];
void build(int i,int l,int r){
l(i)=l,r(i)=r;
for(int k=l;k<=r;k++){
insert(rt(i),a[k]);
}
if(l==r) return;
int mid=(l+r)>>1;
build(ls(i),l,mid);
build(rs(i),mid+1,r);
}
int lessk(int i,int ql,int qr,int k){
int l=l(i),r=r(i);
if(ql<=l&&r<=qr){
return sumless(rt(i),k);
}
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=lessk(ls(i),ql,qr,k);
if(mid>1;
if(q_rk(ql,qr,mid)<=k)
res=mid,st=mid+1;
else ed=mid-1;
}
return res;
}
void modify(int i,int x,int k){
del(rt(i),a[x]);
insert(rt(i),k);
int l=l(i),r=r(i);
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) modify(ls(i),x,k);
else modify(rs(i),x,k);
}
int q_pre(int i,int ql,int qr,int k){
int l=l(i),r=r(i);
if(ql<=l&&r<=qr){
return pre(rt(i),k);
}
int mid=(l+r)>>1,res=-inf;
if(ql<=mid) res=max(res,q_pre(ls(i),ql,qr,k));
if(mid>1,res=inf;
if(ql<=mid) res=min(res,q_nxt(ls(i),ql,qr,k));
if(mid0){
op=read;
switch(op){
case 1:
l=read,r=read,x=read;
write(q_rk(l,r,x)),pt;break;
case 2:
l=read,r=read,x=read;
write(q_kth(l,r,x)),pt;break;
case 3:
l=read,x=read;//不要忘记修改原序列
modify(1,l,x);a[l]=x;break;
case 4:
l=read,r=read,x=read;
write(q_pre(1,l,r,x)),pt;break;
case 5:
l=read,r=read,x=read;
write(q_nxt(1,l,r,x)),pt;break;
default:break;
}
}
return 0;
}
服了,洛谷数据太强大,我的常数也太强大,不得不写离散化。。
FHQ_Treap+离散化
#include
#define getchar() getchar_unlocked()
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 5*1e4+10;
const int inf = 2147483647;
int n,a[N],m;
int MIN=inf,MAX=-inf;
int lsh[N<<1],num,tt;
int op[N];
int l[N],r[N],x[N];
int ans[N],total;
namespace FHQ_TREAP{
struct Treap{
int son[2],rd,cnt,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define rd(i) t[i].rd
#define cnt(i) t[i].cnt
#define siz(i) t[i].siz
#define val(i) t[i].val
}t[N<<6];
int tot;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
}
int New(int k){
val(++tot)=k;
siz(tot)=cnt(tot)=1;
rd(tot)=rand();
return tot;
}
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(val(i)<=k) x=i,split(rs(i),k,rs(i),y);
else y=i,split(ls(i),k,x,ls(i));
up(i);
}
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);
}
void insert(int &rt,int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
merge(rt,rt1,New(k));
merge(rt,rt,rt2);
}
void del(int &rt,int k){
int rt1,rt2,cut;
split(rt,k,rt1,rt2);
split(rt1,k-1,rt1,cut);
merge(cut,ls(cut),rs(cut));
merge(rt1,rt1,cut);
merge(rt,rt1,rt2);
}
int sumless(int rt,int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
int res=siz(rt1);
merge(rt,rt1,rt2);
return res;
}
int pre(int rt,int k){
int rt1,rt2;
split(rt,k-1,rt1,rt2);
if(!siz(rt1)) return -inf;
int res=rt1;
while(rs(res)) res=rs(res);
merge(rt,rt1,rt2);
return val(res);
}
int nxt(int rt,int k){
int rt1,rt2;
split(rt,k,rt1,rt2);
if(!siz(rt2)) return inf;
int res=rt2;
while(ls(res)) res=ls(res);
merge(rt,rt1,rt2);
return val(res);
}
#undef ls
#undef rs
};
using namespace FHQ_TREAP;
namespace Segment_Tree{
struct SegTree{
int l,r,rt;
#define l(i) tr[i].l
#define r(i) tr[i].r
#define rt(i) tr[i].rt
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
}tr[N<<2];
void build(int i,int l,int r){
l(i)=l,r(i)=r;
for(int k=l;k<=r;k++){
insert(rt(i),a[k]);
}
if(l==r) return;
int mid=(l+r)>>1;
build(ls(i),l,mid);
build(rs(i),mid+1,r);
}
int lessk(int i,int ql,int qr,int k){
int l=l(i),r=r(i);
if(ql<=l&&r<=qr){
return sumless(rt(i),k);
}
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=lessk(ls(i),ql,qr,k);
if(mid>1;
if(q_rk(ql,qr,mid)<=k)
res=mid,st=mid+1;
else ed=mid-1;
}
return res;
}
void modify(int i,int x,int k){
del(rt(i),a[x]);
insert(rt(i),k);
int l=l(i),r=r(i);
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) modify(ls(i),x,k);
else modify(rs(i),x,k);
}
int q_pre(int i,int ql,int qr,int k){
int l=l(i),r=r(i);
if(ql<=l&&r<=qr){
return pre(rt(i),k);
}
int mid=(l+r)>>1,res=-inf;
if(ql<=mid) res=max(res,q_pre(ls(i),ql,qr,k));
if(mid>1,res=inf;
if(ql<=mid) res=min(res,q_nxt(ls(i),ql,qr,k));
if(mid
\(T_G\)
JSOI2008火星人prefix
平衡树维护序列,
\(\tt{FHQ}\)
按子树大小分裂,维护
\(hash\)
值,父节点存子树的
\(hash\)
值,最后二分求
\(LCP\)
。注意插入字符后要
++n
。
还是
\(\tt{FHQ}\)
好打,
\(\tt{Splay}\)
以后再说。
FHQ_Treap
#include
using namespace std;
#define ull unsigned long long
#define read read()
#define pt puts("")
#define gc getchar
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
#define N 100010
const ull base = 233;
int n,m;
char s[N];
ull pb[N];
void init(){pb[0]=1ull;for(int i=1;ird(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);
}
void insert(int x,int k){
int rt1,rt2;
split(rt,x,rt1,rt2);
merge(rt,rt1,New(k));
merge(rt,rt,rt2);
}
void replace(int x,int k){
int rt1,rt2,rt3;
split(rt,x,rt1,rt2);
split(rt1,x-1,rt1,rt3);
merge(rt1,rt1,New(k));
merge(rt,rt1,rt2);
}
ull q_hash(int l,int r){
int rt1,rt2,rt3;
split(rt,r,rt2,rt3);
split(rt2,l-1,rt1,rt2);
ull res=hash(rt2);
merge(rt2,rt1,rt2);
merge(rt,rt2,rt3);
return res;
}
} using namespace FHQ_Treap;
int solve(int l,int r){
int st=0,ed=n-r+1;
int res=0;
while(st<=ed){
int mid=(st+ed)>>1;
if(q_hash(l,l+mid-1)==q_hash(r,r+mid-1)){
st=mid+1;res=mid;
}
else ed=mid-1;
}
return res;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
scanf("%s",s+1);
n=strlen(s+1);m=read;
init();
for(int i=1;i<=n;i++){
insert(i-1,s[i]-'a'+1);
}
char op,x;
int l,r;
while(m-->0){
op=gc();while(op!='Q'&&op!='R'&&op!='I')op=gc();
switch(op){
case 'Q':
l=read,r=read;
write(solve(l,r)),pt;
break;
case 'R':
l=read;x=gc();while(x<'a'||x>'z') x=gc();
replace(l,x-'a'+1);
break;
case 'I':
l=read;x=gc();while(x<'a'||x>'z') x=gc();
insert(l,x-'a'+1);++n;
break;
default:break;
}
}
return 0;
}
\(T_H\)
最长上升子序列
逆天性质题~~
本来对于
\(dp_i\)
表示以
\(i\)
位置结尾的最长上升子序列长度,有:
但是对于此题,他是按照
\(1\)
~
\(n\)
的顺序插入,也就是,当前插入的数,一定比原序列里所有数都大,那么
考虑平衡树维护序列,节点存子树里的
\(dp\)
最大值,直接转移即可。
-
对于
\(\tt{FHQ}\)
,分裂出前
\(i\)
个,
\(rt1\)
的
\(dp\)
值
\(\tt{+1}\)
即为所求
-
对于
\(\tt{Splay}\)
,转到根节点,左儿子的
\(dp\)
值
\(\tt{+1}\)
即为所求
FHQ_Treap
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n;
namespace FHQ_Treap{
struct Treap{
int son[2],rd,siz,len,ans;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define rd(i) t[i].rd
#define siz(i) t[i].siz
#define len(i) t[i].len
#define ans(i) t[i].ans
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+1;
ans(i)=max(ans(ls(i)),ans(rs(i)));
ans(i)=max(ans(i),len(i));
}
void split(int i,int k,int &x,int &y){
if(!i){x=y=0;return;}
if(k<=siz(ls(i))) y=i,split(ls(i),k,x,ls(i));
else x=i,split(rs(i),k-(siz(ls(i))+1),rs(i),y);
up(i);
}
void merge(int &i,int x,int y){
if(!x||!y){i=x|y;return;}
if(rd(x)>rd(y)) merge(rs(x),rs(x),y),i=x;
else merge(ls(y),x,ls(y)),i=y;
up(i);
}
int New(int k){
++tot;
siz(tot)=1;
ans(tot)=len(tot)=k;
rd(tot)=rand();
return tot;
}
void insert(int x){
int rt1,rt2;
split(rt,x,rt1,rt2);
merge(rt,rt1,New(ans(rt1)+1));
merge(rt,rt,rt2);
}
} using namespace FHQ_Treap;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
for(int x,i=1;i<=n;i++){
x=read;
insert(x);
write(ans(rt));pt;
}
return 0;
}
Splay
#include
using namespace std;
#define read read()
#define pt puts("")
inline int read{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return f*x;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N = 1e5+10;
int n;
namespace SPLAY{
struct Splay_Tree{
int son[2],fa,ans,siz,val;
#define ls(i) t[i].son[0]
#define rs(i) t[i].son[1]
#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1]
#define fa(i) t[i].fa
#define siz(i) t[i].siz
#define ans(i) t[i].ans
#define val(i) t[i].val
}t[N];
int tot,rt;
void up(int i){
siz(i)=siz(ls(i))+siz(rs(i))+1;
ans(i)=max(ans(ls(i)),ans(rs(i)));
ans(i)=max(ans(i),val(i));
}
void rotate(int x){
int y=fa(x),z=fa(y);
int d=(rs(y)==x);
t[z].son[(rs(z)==y)]=x;fa(x)=z;
ds(y)=bs(x);fa(bs(x))=y;
bs(x)=y;fa(y)=x;
up(y),up(x);
}
void splay(int x,int s){
while(fa(x)!=s){
int y=fa(x),z=fa(y);
if(z!=s)
(ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
rotate(x);
}
if(!s) rt=x;
}
void find(int x){
if(!rt) return;
int p=rt;
while(siz(ls(p))+1!=x){
if(x<=siz(ls(p))+1){
p=ls(p);
}
else{
x-=(siz(ls(p))+1);
p=rs(p);
}
}
splay(p,0);
}
void insert(int &i,int f,int x,int k){
if(!i){
i=++tot;
fa(i)=f;
siz(i)=1;
ans(i)=val(i)=k;
return;
}
if(x<=siz(ls(i))+1) insert(ls(i),i,x,k);
else insert(rs(i),i,x-siz(ls(i))-1,k);
up(i);
}
} using namespace SPLAY;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("lty.in","r",stdin);
freopen("lty.out","w",stdout);
#endif
n=read;
for(int x,k,i=1;i<=n;i++){
x=read;
if(!x) k=1;
else if(x==i-1) k=ans(rt)+1;
else{
find(x+1);
k=ans(ls(rt))+1;
}
insert(rt,0,x+1,k);
splay(tot,0);
write(ans(rt));pt;
}
return 0;
}
\(T_I\)
星系探索
好像是阉割版的
\(\tt{ETT/LCT}\)
(
Wang54321
说的),不会。
伍.闲话
转眼间在奥赛班的短短
\(3\)
个月只剩最后几天,整个下午跑机房,还能有多长时间。。。
\(3\)
个月说长不长说短不短,学到了不少东西,虽然不像别的奥赛对高中文化课有很大帮助,但是:
我们学的东西是他们这辈子都不一定能接触到的。。。
不知道回原班在中考前还能学多长时间
\(\tt{OI}\)
,像小
\(\tt{H}\)
说的
也不知道回原班之后的二三十天,自己还能在这个机位上坐几个小时。这种感觉,或有点像心有余而力不足而被迫退役的感觉吧。当然我也希望,两年后的自己,不会有这种感觉。——
\(\tt{HANGRY\_ Sol}\)
没想到二模完没有立刻【垃圾分类】,那就把
\(\tt{Splay}\)
收尾,不用放假加班了,珍惜机房的每一分钟吧...