BZOJ3196 二逼平衡树
题解
比较经典的一道树套树题目了吧，然而先做了带插入区间第(K)小值之后，这题就比较简单了。外层用线段树，里面套一棵平衡树，这里用了(Splay)。不过需要注意的是，查询排名为(K)的数的时候需要二分，然后到树套树中进行查询排名。这样总的复杂度为(O(nlog^2n))。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('
');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=4e6+500;
const int inf=2147483647;
#define ls(o) o<<1
#define rs(o) o<<1|1
int rt[maxn],a[maxn];
int tot,n,m,mx;
/*==================Define Area================*/
namespace SplayTree {
int ch[maxn][2],sz[maxn],v[maxn],fa[maxn],cnt[maxn];
void Init(int x) {
ch[x][0]=fa[x]=ch[x][1]=sz[x]=cnt[x]=v[x]=0;
}
int Get(int x) {
return ch[fa[x]][1]==x;
}
void Update(int x) {
if(!x) return ;
sz[x]=cnt[x];
if(ch[x][0]) sz[x]+=sz[ch[x][0]];
if(ch[x][1]) sz[x]+=sz[ch[x][1]];
}
void Rotate(int x) {
int y=fa[x],z=fa[y],c=Get(x),cc=Get(y);
ch[y][c]=ch[x][c^1],fa[ch[x][c^1]]=y;
ch[x][c^1]=y;fa[y]=x;
fa[x]=z;
if(z) ch[z][cc]=x;
Update(y);
Update(x);
}
void Splay(int x) {
for(int f;f=fa[x];Rotate(x)) {
if(fa[f]) {
Rotate(Get(x)==Get(f)?f:x);
}
}
}
inline void Insert(int idx,int x){
int now=rt[idx],f=0;
if (!rt[idx]){
rt[idx]=++tot;
fa[tot]=ch[tot][0]=ch[tot][1]=0;
sz[tot]=cnt[tot]=1; v[tot]=x;
return;
}
while (1){
if (x==v[now]){
cnt[now]++;
Update(f);
Splay(now);
rt[idx]=now;
return;
}
f=now;
now=ch[now][v[now]<x];
if (!now){
++tot;
fa[tot]=f;ch[tot][0]=ch[tot][1]=0;
sz[tot]=cnt[tot]=1;v[tot]=x;
ch[f][v[f]<x]=tot;
Update(f);
Splay(tot);
rt[idx]=tot;
return;
}
}
}
void find(int idx,int x) {
int now=rt[idx];
while(1) {
if(v[now]==x) {
Splay(now);
rt[idx]=now;
return ;
}
now=ch[now][v[now]<x];
}
}
int Pre(int idx) {
int now=rt[idx];
now=ch[now][0];
while(ch[now][1]) now=ch[now][1];
return now;
}
int Nxt(int idx) {
int now=rt[idx];
now=ch[now][1];
while(ch[now][0]) now=ch[now][0];
return now;
}
void Del(int i){
int now=rt[i];
if (cnt[now]>1){
cnt[now]--;
Update(now);
return;
}
if (!ch[now][0]&&!ch[now][1]){
Init(rt[i]);
rt[i]=0;
return;
}
if (!ch[now][0]){
int oldroot=now;
rt[i]=ch[oldroot][1];
fa[rt[i]]=0;
Init(oldroot);
return;
}
if (!ch[now][1]){
int oldroot=now;
rt[i]=ch[oldroot][0];
fa[rt[i]]=0;
Init(oldroot);
return;
}
int leftbig=Pre(i),oldroot=rt[i];
Splay(leftbig); rt[i]=leftbig;
ch[rt[i]][1]=ch[oldroot][1];
fa[ch[oldroot][1]]=rt[i];
Init(oldroot);
Update(rt[i]);
return;
}
int GetRank(int idx,int x) {
int now=rt[idx],ans=0;
while(1) {
if(!now) return ans;
if(v[now]==x) return ans+(ch[now][0]?sz[ch[now][0]]:0);
if(v[now]<x) ans+=(ch[now][0]?sz[ch[now][0]]:0)+cnt[now];
now=ch[now][v[now]<x];
}
}
int GetPre(int idx,int x) {
int now=rt[idx],ans=-inf;
while(now) {
if(v[now]<x) {
ans=max(ans,v[now]);
now=ch[now][1];
}
else now=ch[now][0];
}
return ans;
}
int GetNxt(int idx,int x) {
int now=rt[idx],ans=inf;
while(now) {
if(v[now]>x) {
ans=min(ans,v[now]);
now=ch[now][0];
}
else now=ch[now][1];
}
return ans;
}
}
namespace SegmengTree {
void insert(int o,int l,int r,int x,int v) {
int mid=(l+r)>>1;
SplayTree::Insert(o,v);
if(l==r) return ;
if(x<=mid) insert(ls(o),l,mid,x,v);
else insert(rs(o),mid+1,r,x,v);
return ;
}
int getrank(int o,int l,int r,int ql,int qr,int x) {
int ans=0;
if(l>=ql&&r<=qr) {
return SplayTree::GetRank(o,x);
}
int mid=(l+r)>>1;
if(mid>=ql) ans+=getrank(ls(o),l,mid,ql,qr,x);
if(mid<qr) ans+=getrank(rs(o),mid+1,r,ql,qr,x);
return ans;
}
void Modify(int o,int l,int r,int pos,int k) {
int mid=(l+r)>>1;
SplayTree::find(o,a[pos]);SplayTree::Del(o);SplayTree::Insert(o,k);
if(l==r) return ;
if(pos<=mid) Modify(ls(o),l,mid,pos,k);
else Modify(rs(o),mid+1,r,pos,k);
return ;
}
int getpre(int o,int l,int r,int ql,int qr,int k) {
if(ql<=l&&r<=qr) {
return SplayTree::GetPre(o,k);
}
int ans=-inf;
int mid=(l+r)>>1;
if(mid>=ql) ans=max(ans,getpre(ls(o),l,mid,ql,qr,k));
if(mid<qr) ans=max(ans,getpre(rs(o),mid+1,r,ql,qr,k));
return ans;
}
int getnxt(int o,int l,int r,int ql,int qr,int k) {
if(ql<=l&&r<=qr) {
return SplayTree::GetNxt(o,k);
}
int ans=inf;
int mid=(l+r)>>1;
if(mid>=ql) ans=min(ans,getnxt(ls(o),l,mid,ql,qr,k));
if(mid<qr) ans=min(ans,getnxt(rs(o),mid+1,r,ql,qr,k));
return ans;
}
}
int main() {
read(n);read(m);
for(int i=1;i<=n;i++) {
read(a[i]);mx=max(mx,a[i]);
SegmengTree::insert(1,1,n,i,a[i]);
}
while(m--) {
int opt,l,r,pos,k;
read(opt);
if(opt==1) {
read(l);read(r);read(k);
int res=SegmengTree::getrank(1,1,n,l,r,k);
printf("%d
",res+1);
}
if(opt==2) {
read(l);read(r);read(k);
int L=0,R=mx,ret;
while(L<=R) {
int mid=(L+R)>>1;
int res=SegmengTree::getrank(1,1,n,l,r,mid);
if(res<k) {
L=mid+1;
ret=mid;
}
else R=mid-1;
}
printf("%d
",ret);
}
if(opt==3) {
read(pos);read(k);
SegmengTree::Modify(1,1,n,pos,k);
mx=max(mx,k);
a[pos]=k;
}
if(opt==4) {
read(l);read(r);read(k);
int res=SegmengTree::getpre(1,1,n,l,r,k);
printf("%d
",res);
}
if(opt==5) {
read(l);read(r);read(k);
int res=SegmengTree::getnxt(1,1,n,l,r,k);
printf("%d
",res);
}
}
return 0;
}