【學(xué)習(xí)筆記】FHQ-Treap
一、前言
在今年 NOIP 前學(xué)習(xí)了 FHQ-Treap（一種平衡樹），現(xiàn)在來(lái)記一記。
二、定義
Treap=tree+heap。具體的說(shuō)，Treap 所維護(hù)的值滿足二叉搜索樹的性質(zhì)，另一個(gè)變量?jī)?yōu)先級(jí)滿足堆的性質(zhì)。優(yōu)先級(jí)一般使一個(gè)隨機(jī)數(shù)，這使得樹的高度保持在 \(O(\log n)\) 水平，二叉搜索樹的性質(zhì)使樹可以維護(hù)有序的集合或序列。因?yàn)?\(O(\log n)\) 的樹高，Treap 的操作時(shí)間復(fù)雜度一般都是 \(O(\log n)\) 的。
FHQ-Treap 又名無(wú)旋 Treap，它通過(guò)旋轉(zhuǎn)和分裂維護(hù)堆的性質(zhì)。
三、基本操作
1.合并
合并函數(shù) merge(int p,int q) 用于合并以 \(p\) 為根的樹和以 \(q\) 為根的樹。需要注意的是，合并函數(shù)傳入的兩個(gè)參數(shù) \(p\) 和 \(q\) 要求滿足二叉搜索樹的性質(zhì)，因此在合并過(guò)程中我們只需維護(hù)堆的性質(zhì)即可。
以小根堆為例（其實(shí)大根小根都無(wú)所謂）：
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian(p)<jian(q)){
rs(p)=merge(rs(p),q);
pushup(p);
return p;
}
else{
ls(q)=merge(p,ls(q));
pushup(q);
return q;
}
}
2.分裂
分為按值分裂和按排名分裂。以按值分裂為例，函數(shù) split(int id,int val,int &p,int &q) 將 \(id\) 為根的樹分成 \(p\) 和 \(q\) 兩棵樹，其中 \(p\) 中的值都小于等于 \(val\)，\(q\) 中的值都大于 \(val\)。
il void split(int id,int val,int &p,int &q){
if(!id){
p=q=0;
return ;
}
if(val(id)<=val){
p=id;
split(rs(id),val,rs(id),q);
}
else{
q=id;
split(ls(id),val,p,ls(id));
}
pushup(id);
}
其他操作就都很簡(jiǎn)單了。
四、例題
1.普通平衡樹
板子題，維護(hù)一個(gè)有序的集合。具體講講每個(gè)操作。
插入
將樹按插入的值 \(val\) 分裂，再新建一個(gè)值為 \(val\) 的點(diǎn)合并進(jìn)去。
刪除
通過(guò)兩次分裂，將所有值為 \(val\) 的點(diǎn)搞到一棵樹中。忽略這棵樹的根節(jié)點(diǎn)進(jìn)行合并即可。
查詢排名
將樹按 \(val-1\) 分裂，左邊的樹的大小再加一就是答案。
查詢第 \(k\) 小
可以按照二叉搜索樹的方式遞歸查詢。
查詢前驅(qū)
按 \(val-1\) 分裂，設(shè)左邊大小為 \(res\)，排名為 \(res\) 的就是前驅(qū)。
查詢后繼
按 \(val\) 分裂，設(shè)左邊大小為 \(res\)，排名為 \(res+1\) 的就是后繼。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n;
struct node{
int ls,rs,val,jian,sz;
node(int ls=0,int rs=0,int val=0,int jian=0,int sz=0)
:ls(ls),rs(rs),val(val),jian(jian),sz(sz){}
};
struct FHQtreap{
#define ls(id) tr[id].ls
#define rs(id) tr[id].rs
#define val(id) tr[id].val
#define jian(id) tr[id].jian
#define sz(id) tr[id].sz
int rt,tot;
node tr[maxn];
il int New(int val){
tot++;
val(tot)=val;
jian(tot)=rand();
sz(tot)=1;
return tot;
}
il void pushup(int id){
sz(id)=sz(ls(id))+sz(rs(id))+1;
}
il void split(int id,int val,int &p,int &q){
if(!id){
p=q=0;
return ;
}
if(val(id)<=val){
p=id;
split(rs(id),val,rs(id),q);
}
else{
q=id;
split(ls(id),val,p,ls(id));
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian(p)<jian(q)){
rs(p)=merge(rs(p),q);
pushup(p);
return p;
}
else{
ls(q)=merge(p,ls(q));
pushup(q);
return q;
}
}
il void insert(int val){
int x,y;
split(rt,val,x,y);
rt=merge(merge(x,New(val)),y);
}
il void erase(int val){
int x,y,z;
split(rt,val,x,y);
split(x,val-1,x,z);
rt=merge(merge(x,merge(ls(z),rs(z))),y);
}
il int rnk(int val){
int x,y;
split(rt,val-1,x,y);
int res=sz(x)+1;
rt=merge(x,y);
return res;
}
il int kth(int id,int k){
if(sz(ls(id))==k-1){
return val(id);
}
if(sz(ls(id))>=k){
return kth(ls(id),k);
}
return kth(rs(id),k-sz(ls(id))-1);
}
il int kth(int val){
return kth(rt,val);
}
il int pre(int val){
int x,y;
split(rt,val-1,x,y);
int res=sz(x);
rt=merge(x,y);
return kth(res);
}
il int nxt(int val){
int x,y;
split(rt,val,x,y);
int res=sz(x);
rt=merge(x,y);
return kth(res+1);
}
#undef ls
#undef rs
#undef val
#undef jian
#undef sz
}fhq;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
srand(time(0));
read(n);
while(n--){
int opt,x;
read(opt)read(x)
switch(opt){
case 1:{
fhq.insert(x);
break;
}
case 2:{
fhq.erase(x);
break;
}
case 3:{
printf("%d\n",fhq.rnk(x));
break;
}
case 4:{
printf("%d\n",fhq.kth(x));
break;
}
case 5:{
printf("%d\n",fhq.pre(x));
break;
}
default:{
printf("%d\n",fhq.nxt(x));
break;
}
}
}
return 0;
}
2.文藝平衡樹
維護(hù)序列?？紤]翻轉(zhuǎn)區(qū)間 \([l,r]\)，就是將 \([l,r]\) 中的每個(gè)節(jié)點(diǎn)的左右兒子都交換。打上懶標(biāo)記即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define ls(id) tr[id].ls
#define rs(id) tr[id].rs
#define val(id) tr[id].val
#define jian(id) tr[id].jian
#define tag(id) tr[id].tag
#define sz(id) tr[id].sz
using namespace std;
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,rt,tot;
struct node{
int ls,rs,val,sz,jian;
bool tag;
}tr[maxn];
il int New(int val){
tot++;
val(tot)=val;
sz(tot)=1;
jian(tot)=rand();
return tot;
}
il void pushup(int id){
sz(id)=sz(ls(id))+sz(rs(id))+1;
}
il void pushdown(int id){
if(tag(id)){
swap(ls(id),rs(id));
tag(ls(id))^=1,tag(rs(id))^=1;
tag(id)=0;
}
}
il void split(int id,int k,int &p,int &q){
if(!id){
p=q=0;
return ;
}
pushdown(id);
if(sz(ls(id))>=k){
q=id;
split(ls(id),k,p,ls(id));
}
else{
p=id;
split(rs(id),k-sz(ls(id))-1,rs(id),q);
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian(p)<jian(q)){
pushdown(p);
rs(p)=merge(rs(p),q);
pushup(p);
return p;
}
pushdown(q);
ls(q)=merge(p,ls(q));
pushup(q);
return q;
}
il void dfs(int id){
if(!id){
return ;
}
pushdown(id);
dfs(ls(id));
printf("%d ",val(id));
dfs(rs(id));
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
srand(time(0));
read(n)read(m);
for(int i=1;i<=n;i++){
rt=merge(rt,New(i));
}
while(m--){
int l,r;
read(l)read(r);
int x,y,z;
split(rt,r,x,y);
split(x,l-1,x,z);
tag(z)^=1;
rt=merge(merge(x,z),y);
}
dfs(rt);
return 0;
}
3.[HNOI2002] 營(yíng)業(yè)額統(tǒng)計(jì)
顯然對(duì)于每一天，答案就是這一天的值和前驅(qū)后繼的差的最小值。直接維護(hù)即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace cplx{bool begin;}
const int maxn=(1<<15)+5;
const int inf=0x3f3f3f3f;
int n,rt,tot,ls[maxn],rs[maxn];
int val[maxn],sz[maxn],jian[maxn];
il int New(int x){
tot++;
val[tot]=x;
sz[tot]=1;
jian[tot]=rand();
return tot;
}
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian[p]<jian[q]){
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
il void split(int id,int x,int &p,int &q){
if(!id){
p=q=0;
return ;
}
if(val[id]<=x){
p=id;
split(rs[id],x,rs[id],q);
}
else{
q=id;
split(ls[id],x,p,ls[id]);
}
pushup(id);
}
il void insert(int x){
int p,q;
split(rt,x,p,q);
rt=merge(merge(p,New(x)),q);
}
il int rnk(int x){
int p,q;
split(rt,x-1,p,q);
int res=sz[p]+1;
rt=merge(p,q);
return res;
}
il int kth(int id,int k){
if(sz[ls[id]]==k-1){
return val[id];
}
if(sz[ls[id]]>=k){
return kth(ls[id],k);
}
return kth(rs[id],k-sz[ls[id]]-1);
}
il int pre(int x){
int p,q;
split(rt,x-1,p,q);
int res=sz[p];
rt=merge(p,q);
return kth(rt,res);
}
il int nxt(int x){
int p,q;
split(rt,x-1,p,q);
int res=kth(q,1);
rt=merge(p,q);
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
insert(-inf),insert(inf);
ll ans=0;
for(int i=1,x;i<=n;i++){
read(x);
if(i==1){
ans+=x;
}
else{
ans+=min(x-pre(x),nxt(x)-x);
}
insert(x);
}
printf("%lld",ans);
return 0;
}
4.[HNOI2004] 寵物收養(yǎng)場(chǎng)
依然是求前驅(qū)后繼。要注意的是，需要記錄當(dāng)前平衡樹內(nèi)維護(hù)的是寵物還是領(lǐng)養(yǎng)者。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace cplx{bool begin;}
const int maxn=8e4+5,mod=1e6;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,rt,tot,ls[maxn],rs[maxn];
int sz[maxn],jian[maxn];
ll zhi[maxn];
il int New(ll val){
zhi[++tot]=val;
jian[tot]=rand();
sz[tot]=1;
return tot;
}
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il void split(int id,ll val,int &p,int &q){
if(!id){
p=q=0;
return ;
}
if(zhi[id]<=val){
p=id;
split(rs[id],val,rs[id],q);
}
else{
q=id;
split(ls[id],val,p,ls[id]);
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian[p]<jian[q]){
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
il void insert(ll val){
int x,y;
split(rt,val,x,y);
rt=merge(merge(x,New(val)),y);
}
il void erase(ll val){
int x,y,z;
split(rt,val,x,y);
split(x,val-1,x,z);
rt=merge(merge(x,merge(ls[z],rs[z])),y);
}
il ll kth(int id,int k){
if(sz[ls[id]]==k-1){
return zhi[id];
}
if(sz[ls[id]]>=k){
return kth(ls[id],k);
}
return kth(rs[id],k-sz[ls[id]]-1);
}
il ll pre(ll val){
int x,y;
split(rt,val,x,y);
ll res=kth(x,sz[x]);
rt=merge(x,y);
return res;
}
il ll nxt(ll val){
int x,y;
split(rt,val-1,x,y);
ll res=kth(y,1);
rt=merge(x,y);
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
srand(time(0));
insert(-inf),insert(inf);
ll ans=0;
read(n);
bool flag=0;
while(n--){
int opt;
ll a;
read(opt)read(a);
if(sz[rt]==2||flag==opt){
insert(a);
flag=opt;
}
else{
ll x=pre(a),y=nxt(a);
(ans+=min(a-x,y-a))%=mod;
erase(a-x<=y-a?x:y);
}
}
printf("%lld",ans);
return 0;
}
5.「NOI 2004」郁悶的出納員
整體修改 + 查詢第 \(k\) 小，打懶標(biāo)記即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,rt,tot,ls[maxn],rs[maxn];
int zhi[maxn],jian[maxn];
int tag[maxn],sz[maxn];
il int New(int val){
zhi[++tot]=val;
jian[tot]=rand();
sz[tot]=1;
return tot;
}
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il void pushdown(int id){
if(tag[id]){
tag[ls[id]]+=tag[id];
tag[rs[id]]+=tag[id];
zhi[ls[id]]+=tag[id];
zhi[rs[id]]+=tag[id];
tag[id]=0;
}
}
il void split(int id,int val,int &p,int &q){
if(!id){
p=q=0;
return ;
}
pushdown(id);
if(zhi[id]<=val){
p=id;
split(rs[id],val,rs[id],q);
}
else{
q=id;
split(ls[id],val,p,ls[id]);
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian[p]<jian[q]){
pushdown(p);
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
pushdown(q);
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
il void insert(int val){
int x,y;
split(rt,val,x,y);
rt=merge(merge(x,New(val)),y);
}
il void erase(int val){
int x,y,z;
split(rt,val,x,y);
split(x,val-1,x,z);
rt=merge(merge(x,merge(ls[z],rs[z])),y);
}
il int kth(int id,int k){
if(sz[ls[id]]==k-1){
return zhi[id];
}
pushdown(id);
if(sz[ls[id]]>=k){
return kth(ls[id],k);
}
return kth(rs[id],k-sz[ls[id]]-1);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
srand(time(0));
read(n)read(m);
int ans=0;
while(n--){
char opt;
int x;
scanf(" %c",&opt);
read(x);
switch(opt){
case 'I':{
if(x>=m){
insert(x);
}
break;
}
case 'A':{
if(sz[rt]){
tag[rt]+=x,zhi[rt]+=x;
}
break;
}
case 'S':{
if(sz[rt]){
tag[rt]-=x,zhi[rt]-=x;
int val=kth(rt,1);
while(val<m){
erase(val),ans++;
if(sz[rt]){
val=kth(rt,1);
}
else{
break;
}
}
}
break;
}
default:{
printf("%d\n",x>sz[rt]?-1:kth(rt,sz[rt]-x+1));
break;
}
}
}
printf("%d",ans);
return 0;
}
6.[JSOI2008]火星人prefix
考慮用平衡樹維護(hù)哈希。那么對(duì)于修改操作，就是一個(gè)區(qū)間加和區(qū)間乘的操作了。詢問(wèn)二分即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define ull unsigned ll
using namespace std;
namespace cplx{bool begin;}
const int maxn=1e5+5;
const ull bas1=13331;
const ll bas2=13327,mod2=2.5e9+1;
int n,m,rt,tot,sz[maxn],ls[maxn],rs[maxn],jian[maxn];
ull pw1[maxn],ha1[maxn],tgj1[maxn],tgc1[maxn];
ll pw2[maxn],ha2[maxn],tgj2[maxn],tgc2[maxn];
char s[maxn],zhi[maxn];
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il void pushdown(int id){
if(tgc1[id]!=1){
if(ls[id]){
tgc1[ls[id]]*=tgc1[id];
tgj1[ls[id]]*=tgc1[id];
ha1[ls[id]]*=tgc1[id];
}
if(rs[id]){
tgc1[rs[id]]*=tgc1[id];
tgj1[rs[id]]*=tgc1[id];
ha1[rs[id]]*=tgc1[id];
}
tgc1[id]=1;
}
if(tgc2[id]!=1){
if(ls[id]){
(tgc2[ls[id]]*=tgc2[id])%=mod2;
(tgj2[ls[id]]*=tgc2[id])%=mod2;
(ha2[ls[id]]*=tgc2[id])%=mod2;
}
if(rs[id]){
(tgc2[rs[id]]*=tgc2[id])%=mod2;
(tgj2[rs[id]]*=tgc2[id])%=mod2;
(ha2[rs[id]]*=tgc2[id])%=mod2;
}
tgc2[id]=1;
}
if(tgj1[id]){
if(ls[id]){
tgj1[ls[id]]+=tgj1[id];
ha1[ls[id]]+=tgj1[id];
}
if(rs[id]){
tgj1[rs[id]]+=tgj1[id];
ha1[rs[id]]+=tgj1[id];
}
tgj1[id]=0;
}
if(tgj2[id]){
if(ls[id]){
(tgj2[ls[id]]+=tgj2[id])%=mod2;
(ha2[ls[id]]+=tgj2[id])%=mod2;
}
if(rs[id]){
(tgj2[rs[id]]+=tgj2[id])%=mod2;
(ha2[rs[id]]+=tgj2[id])%=mod2;
}
tgj2[id]=0;
}
}
il void split(int id,int k,int &p,int &q){
if(!id){
p=q=0;
return ;
}
pushdown(id);
if(sz[ls[id]]<k){
p=id;
split(rs[id],k-sz[ls[id]]-1,rs[id],q);
}
else{
q=id;
split(ls[id],k,p,ls[id]);
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian[p]<jian[q]){
pushdown(p);
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
pushdown(q);
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
il int kth(int id,int k){
if(sz[ls[id]]==k-1){
return id;
}
pushdown(id);
if(sz[ls[id]]<k){
return kth(rs[id],k-sz[ls[id]]-1);
}
return kth(ls[id],k);
}
il void upd(int pos,char val){
int x,y,z;
split(rt,pos-1,x,y);
z=kth(y,1);
tgj1[y]+=pw1[pos-1]*(val-zhi[z]);
ha1[y]+=pw1[pos-1]*(val-zhi[z]);
(tgj2[y]+=(val-zhi[z]+mod2)%mod2*pw2[pos-1])%=mod2;
(ha2[y]+=(val-zhi[z]+mod2)%mod2*pw2[pos-1])%=mod2;
zhi[z]=val;
rt=merge(x,y);
}
il void insert(int pos,char val){
zhi[++tot]=val;
sz[tot]=1;
jian[tot]=rand();
tgc1[tot]=tgc2[tot]=1;
int x,y,z;
split(rt,pos,x,y);
z=kth(x,pos);
ha1[tot]=ha1[z]+pw1[pos]*val;
ha2[tot]=(ha2[z]+pw2[pos]*val)%mod2;
if(y){
tgc1[y]*=bas1;
(tgc2[y]*=bas2)%=mod2;
tgj1[y]=(tgj1[y]-ha1[z])*bas1+ha1[tot];
tgj2[y]=((tgj2[y]-ha2[z]+mod2)%mod2*bas2+ha2[tot])%mod2;
ha1[y]=(ha1[y]-ha1[z])*bas1+ha1[tot];
ha2[y]=((ha2[y]-ha2[z]+mod2)%mod2*bas2+ha2[tot])%mod2;
}
rt=merge(merge(x,tot),y);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
srand(time(0));
pw1[0]=pw2[0]=1;
for(int i=1;i<=1e5;i++){
pw1[i]=pw1[i-1]*bas1;
pw2[i]=pw2[i-1]*bas2%mod2;
}
scanf(" %s",s+1);
n=strlen(s+1);
rt=tot=1;
sz[rt]=1,jian[rt]=rand();
tgc1[rt]=tgc2[rt]=1;
for(int i=1;i<=n;i++){
insert(i,s[i]);
}
read(m);
while(m--){
char opt;
scanf(" %c",&opt);
switch(opt){
case 'Q':{
int x,y,p,q;
read(x)read(y);
if(x>y){
swap(x,y);
}
p=kth(rt,x);
q=kth(rt,y);
ull hx1=ha1[p],hy1=ha1[q];
ll hx2=ha2[p],hy2=ha2[q];
int l=0,r=sz[rt]-y;
while(l<r){
int mid=(l+r+1)>>1;
p=kth(rt,x+mid);
q=kth(rt,y+mid);
if((ha1[p]-hx1)*pw1[y-x]==ha1[q]-hy1&&(ha2[p]-hx2+mod2)%mod2*pw2[y-x]%mod2==(ha2[q]-hy2+mod2)%mod2){
l=mid;
}
else{
r=mid-1;
}
}
printf("%d\n",l);
break;
}
case 'R':{
int x;
char val;
read(x);
scanf(" %c",&val);
upd(x+1,val);
break;
}
default:{
int x;
char val;
read(x);
scanf(" %c",&val);
insert(x+1,val);
break;
}
}
}
return 0;
}
7.[Tjoi2013]最長(zhǎng)上升子序列
考慮 DP，設(shè) \(dp_i\) 表示以 \(i\) 結(jié)尾的最長(zhǎng)上升子序列長(zhǎng)度。有方程：
\[dp_i=\max_{j<i\land a_j<a_i} dp_j
\]
因?yàn)槭菑男〉酱蟛迦耄覀兙椭挥镁S護(hù) \(j<i\) 的限制就行了。用平衡樹維護(hù)序列即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,rt,tot,sz[maxn],zhi[maxn],mx[maxn],jian[maxn],ls[maxn],rs[maxn];
il void pushup(int id){
mx[id]=max({zhi[id],mx[ls[id]],mx[rs[id]]});
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il void split(int id,int k,int &p,int &q){
if(!id){
p=q=0;
return ;
}
if(sz[ls[id]]<k){
p=id;
split(rs[id],k-sz[ls[id]]-1,rs[id],q);
}
else{
q=id;
split(ls[id],k,p,ls[id]);
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian[p]<jian[q]){
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
srand(time(0));
for(int i=1,p,x,y;i<=n;i++){
read(p);
split(rt,p,x,y);
sz[++tot]=1,jian[tot]=rand();
mx[tot]=zhi[tot]=mx[x]+1;
rt=merge(merge(x,tot),y);
printf("%d\n",mx[rt]);
}
return 0;
}
8.二逼平衡樹
線段樹套平衡樹。
在每個(gè)線段樹的節(jié)點(diǎn)上維護(hù)一個(gè)平衡樹，維護(hù)這個(gè)區(qū)間中的值。逐一分析每個(gè)操作。
查詢排名
考慮排名的本質(zhì)，就是比 \(val\) 小的值的數(shù)量加一。在線段樹上將區(qū)間拆分成 \(O(\log n)\) 個(gè)，再在每個(gè)區(qū)間中查詢累加答案即可。
查詢第 \(k\) 小
這不好直接查，二分即可。
單點(diǎn)修改
在線段樹上每個(gè)相關(guān)的節(jié)點(diǎn)修改即可。
查詢前驅(qū)
前驅(qū)就是比 \(val\) 小的值中最大的值。在每個(gè)區(qū)間內(nèi)查詢并取 \(\max\) 即可。
查詢后繼
類似前驅(qū)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e4+5,inf=0x3f3f3f3f;
int n,m,a[maxn],rt[maxn<<2];
namespace fhq{
int tot,zhi[maxn*20],sz[maxn*20];
int ls[maxn*20],rs[maxn*20],jian[maxn*20];
int ljt[maxn*20],top;
il int New(int val){
int p=top?ljt[top--]:++tot;
zhi[p]=val;
jian[p]=rand();
sz[p]=1;
ls[p]=rs[p]=0;
return p;
}
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il void split(int id,int val,int &p,int &q){
if(!id){
p=q=0;
return ;
}
if(zhi[id]<=val){
p=id;
split(rs[id],val,rs[id],q);
}
else{
q=id;
split(ls[id],val,p,ls[id]);
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian[p]<jian[q]){
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
il int rnk(int &id,int val){
int x,y;
split(id,val-1,x,y);
int res=sz[x]+1;
id=merge(x,y);
return res;
}
il void insert(int &id,int val){
int x,y;
split(id,val,x,y);
id=merge(merge(x,New(val)),y);
}
il void del(int &id,int val){
int x,y,z;
split(id,val,x,y);
split(x,val-1,x,z);
ljt[++top]=z;
id=merge(merge(x,merge(ls[z],rs[z])),y);
}
il int kth(int id,int k){
if(sz[ls[id]]==k-1){
return zhi[id];
}
if(sz[ls[id]]>=k){
return kth(ls[id],k);
}
return kth(rs[id],k-sz[ls[id]]-1);
}
il int qanq(int &id,int val){
int x,y;
split(id,val-1,x,y);
int res=sz[x]?kth(x,sz[x]):-inf;
id=merge(x,y);
return res;
}
il int houj(int &id,int val){
int x,y;
split(id,val,x,y);
int res=sz[y]?kth(y,1):inf;
id=merge(x,y);
return res;
}
}
il void build(int id,int l,int r){
for(int i=l;i<=r;i++){
fhq::insert(rt[id],a[i]);
}
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il int qrnk(int id,int L,int R,int l,int r,int val){
if(L>=l&&R<=r){
return fhq::rnk(rt[id],val);
}
int mid=(L+R)>>1,res=0;
if(l<=mid){
res+=qrnk(lid,L,mid,l,r,val)-1;
}
if(r>mid){
res+=qrnk(rid,mid+1,R,l,r,val)-1;
}
return res+1;
}
il void upd(int id,int l,int r,int pos,int val){
fhq::del(rt[id],a[pos]);
fhq::insert(rt[id],val);
if(l==r){
return ;
}
int mid=(l+r)>>1;
if(pos<=mid){
upd(lid,l,mid,pos,val);
}
else{
upd(rid,mid+1,r,pos,val);
}
}
il int qqanq(int id,int L,int R,int l,int r,int val){
if(L>=l&&R<=r){
return fhq::qanq(rt[id],val);
}
int mid=(L+R)>>1,res=-inf;
if(l<=mid){
res=max(res,qqanq(lid,L,mid,l,r,val));
}
if(r>mid){
res=max(res,qqanq(rid,mid+1,R,l,r,val));
}
return res;
}
il int qhouj(int id,int L,int R,int l,int r,int val){
if(L>=l&&R<=r){
return fhq::houj(rt[id],val);
}
int mid=(L+R)>>1,res=inf;
if(l<=mid){
res=min(res,qhouj(lid,L,mid,l,r,val));
}
if(r>mid){
res=min(res,qhouj(rid,mid+1,R,l,r,val));
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
srand(time(0));
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i]);
}
build(1,1,n);
while(m--){
int opt;
read(opt);
switch(opt){
case 1:{
int l,r,val;
read(l)read(r)read(val);
printf("%d\n",qrnk(1,1,n,l,r,val));
break;
}
case 2:{
int l,r,k;
read(l)read(r)read(k);
int L=-inf,R=inf;
while(L<R){
int mid=(L+R+1)>>1;
if(qrnk(1,1,n,l,r,mid)<=k){
L=mid;
}
else{
R=mid-1;
}
}
printf("%d\n",L);
break;
}
case 3:{
int pos,val;
read(pos)read(val);
upd(1,1,n,pos,val);
a[pos]=val;
break;
}
case 4:{
int l,r,val;
read(l)read(r)read(val);
printf("%d\n",qqanq(1,1,n,l,r,val));
break;
}
default:{
int l,r,val;
read(l)read(r)read(val);
printf("%d\n",qhouj(1,1,n,l,r,val));
break;
}
}
}
return 0;
}
}
int main(){return asbt::main();}
9.星系探索
考慮給樹建一個(gè)歐拉序，對(duì)于點(diǎn) \(u\)，在進(jìn)入 \(u\) 的子樹時(shí)將 \(u\) 加入序列，記位置為 \(dfn_u\)；出 \(u\) 的子樹是再將 \(u\) 加入序列，記位置為 \(low_u\)。
如果在 \(dfn_u\) 記錄 \(u\) 的權(quán)值，在 \(low_u\) 記錄 \(u\) 的權(quán)值的負(fù)值，那么對(duì)于節(jié)點(diǎn) \(u\)，歐拉序上 \([1,dfn_u]\) 的和就是根到 \(u\) 的權(quán)值之和。
子樹加是簡(jiǎn)單的，考慮子樹移動(dòng)。對(duì)應(yīng)到區(qū)間上，其實(shí)就是區(qū)間平移。那么看起來(lái)似乎就很簡(jiǎn)單了。問(wèn)題在于，平移后每個(gè)節(jié)點(diǎn)的排名可能會(huì)改變，要再按排名分裂會(huì)出問(wèn)題?？紤]對(duì)每個(gè)節(jié)點(diǎn)，再記錄它的父親節(jié)點(diǎn) \(fa\)。那么一個(gè)節(jié)點(diǎn)當(dāng)前的排名就可以跳 \(fa\) 來(lái)求了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define int ll
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,m,dfn[maxn],low[maxn];
int rt,tot,ls[maxn],rs[maxn];
int fa[maxn],zhi[maxn],sum[maxn];
int sz[maxn],jian[maxn],a[maxn];
int col[maxn],tcl[maxn],tag[maxn];
vector<int> e[maxn];
il int New(int x,int y){
jian[++tot]=rand();
sum[tot]=zhi[tot]=x;
tcl[tot]=col[tot]=y;
sz[tot]=1,fa[tot]=0;
return tot;
}
il void pushup(int id){
sum[id]=sum[ls[id]]+sum[rs[id]]+zhi[id];
tcl[id]=tcl[ls[id]]+tcl[rs[id]]+col[id];
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il void pushdown(int id){
if(tag[id]){
tag[ls[id]]+=tag[id];
tag[rs[id]]+=tag[id];
zhi[ls[id]]+=col[ls[id]]*tag[id];
zhi[rs[id]]+=col[rs[id]]*tag[id];
sum[ls[id]]+=tag[id]*tcl[ls[id]];
sum[rs[id]]+=tag[id]*tcl[rs[id]];
tag[id]=0;
}
}
il void split(int id,int k,int &p,int &q){
if(!id){
p=q=0;
return ;
}
pushdown(id);
if(sz[ls[id]]<k){
p=id;
split(rs[id],k-sz[ls[id]]-1,rs[id],q);
fa[rs[id]]=id;
}
else{
q=id;
split(ls[id],k,p,ls[id]);
fa[ls[id]]=id;
}
pushup(id);
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jian[p]<jian[q]){
pushdown(p);
rs[p]=merge(rs[p],q);
fa[rs[p]]=p;
pushup(p);
return p;
}
pushdown(q);
ls[q]=merge(p,ls[q]);
fa[ls[q]]=q;
pushup(q);
return q;
}
il void dfs(int u,int fth){
rt=merge(rt,dfn[u]=New(a[u],1));
fa[rt]=0;
for(int v:e[u]){
dfs(v,u);
}
rt=merge(rt,low[u]=New(-a[u],-1));
fa[rt]=0;
}
il int rnk(int id){
int res=sz[ls[id]]+1;
while(fa[id]){
if(id==rs[fa[id]]){
res+=sz[ls[fa[id]]]+1;
}
id=fa[id];
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
read(n);
for(int i=2,x;i<=n;i++){
read(x);
e[x].pb(i);
}
for(int i=1;i<=n;i++){
read(a[i]);
}
dfs(1,0);
read(m);
while(m--){
char opt;
scanf(" %c",&opt);
switch(opt){
case 'Q':{
int u,x,y;
read(u);
split(rt,rnk(dfn[u]),x,y);
fa[x]=fa[y]=0;
printf("%lld\n",sum[x]);
rt=merge(x,y);
fa[rt]=0;
break;
}
case 'C':{
int u,v;
read(u)read(v);
int l=rnk(dfn[u]),r=rnk(low[u]);
int tv=rnk(dfn[v]);
int x,y,z;
split(rt,r,x,y);
fa[x]=fa[y]=0;
split(x,l-1,x,z);
fa[x]=fa[z]=0;
if(tv<l){
int w;
split(x,tv,x,w);
fa[x]=fa[w]=0;
rt=merge(merge(x,z),merge(w,y));
fa[rt]=0;
}
else{
int w;
split(y,tv-r,w,y);
rt=merge(merge(x,w),merge(z,y));
fa[rt]=0;
}
break;
}
default:{
int u,val;
read(u)read(val);
int l=rnk(dfn[u]),r=rnk(low[u]);
int x,y,z;
split(rt,r,x,y);
split(x,l-1,x,z);
tag[z]+=val,zhi[z]+=col[z]*val;
sum[z]+=val*tcl[z];
rt=merge(merge(x,z),y);
break;
}
}
}
return 0;
}
}
signed main(){return asbt::main();}
浙公網(wǎng)安備 33010602011771號(hào)