我写的是线段树套splay，网上很多人写的都是套treap，然而本蒟蒻并不会treap
奉上sth神犇的模板：
//bzoj3196 二逼平衡树，支持修改某个点的值，查询区间第k小值，查询区间某个值排名，查询区间某个值值前驱、后继。查询第k小值是log^3(n)的，其他都是log^2(n)的
#include <cstdio>
using namespace std;
const int maxn=,inf=;
int a[maxn],f[maxn],sum[maxn],num[maxn],n,m,c[],root[],left,right,tot,son[maxn][];
int mmin(int x,int y)
{
if (x<y) return x;
return y;
}
int mmax(int x,int y)
{
if (x>y) return x;
return y;
}
void rotate(int x,int w)
{
int y=f[x];
if (f[y]) if (y==son[f[y]][]) son[f[y]][]=x; else son[f[y]][]=x;
f[x]=f[y];
if (son[x][w]) f[son[x][w]]=y;
son[y][-w]=son[x][w];
f[y]=x;
son[x][w]=y;
sum[y]=sum[son[y][]]+sum[son[y][]]+num[y];
}
void splay(int r,int x,int w)
{
int y;
while (f[x]!=w)
{
y=f[x];
if (f[y]==w) if (x==son[y][]) rotate(x,); else rotate(x,);
else if (y==son[f[y]][]) if (x==son[y][]) {rotate(y,); rotate(x,); } else {rotate(x,); rotate(x,);}
else if (x==son[y][]) {rotate(x,); rotate(x,);} else {rotate(y,); rotate(x,);}
}
sum[x]=sum[son[x][]]+sum[son[x][]]+num[x];
if (w==) root[r]=x;
}
void insert(int r,int value)
{
int x=root[r];
if (x==)
{
a[++tot]=value;
num[tot]=sum[tot]=;
root[r]=tot;
return;
}
while (a[x]!=value)
if (a[x]>value) {if (son[x][]) x=son[x][]; else break;}
else {if (son[x][]) x=son[x][]; else break;}
if (a[x]==value) {num[x]++; splay(r,x,); return;}
a[++tot]=value;
f[tot]=x;
num[tot]=sum[tot]=;
if (value<a[x]) son[x][]=tot; else son[x][]=tot;
splay(r,tot,);
}
void del(int r,int value)
{
int x=root[r];
while (a[x]!=value)
if (a[x]>value) {if (son[x][]) x=son[x][]; else break;}
else {if (son[x][]) x=son[x][]; else break;}
splay(r,x,);
if (num[x]>) {num[x]--; return;}
if (!son[x][]) {root[r]=son[x][]; f[son[x][]]=; return;}
if (!son[x][]) {root[r]=son[x][]; f[son[x][]]=; return;}
int y=son[x][];
while (son[y][]) y=son[y][];
splay(r,y,x);
son[y][]=son[x][];
f[y]=;//一定记得f[y]=0
f[son[y][]]=y;
sum[y]=sum[son[y][]]+sum[son[y][]]+num[y];
root[r]=y;
}
void build(int now,int l,int r)
{
//printf("now=%d l=%d r=%d\n",now,l,r);
int i;
for (i=l;i<=r;i++) insert(now,c[i]);//对每个线段树区间都建立一棵平衡树
//print(now);
if (l==r) return;
int mid=(l+r)>>;
i=now<<;
build(i,l,mid);
build(i+,mid+,r);
}
int find(int r,int value)
{
int x=root[r];
while (a[x]!=value)
if (a[x]>value) {if (son[x][]) x=son[x][]; else break;}
else {if (son[x][]) x=son[x][]; else break;}
splay(r,x,);
return x;
}
int rank(int r,int k)
{
int x=find(r,k);
if (a[x]>=k) return (sum[son[x][]]);
return (sum[son[x][]]+num[x]);
}
int getrank(int now,int l,int r,int k)
{
if (l>=left&&r<=right) return (rank(now,k));
int mid=(l+r)>>,w=now<<,ret=;
if (left<=mid) ret=getrank(w,l,mid,k);
if (right>mid) ret+=getrank(w+,mid+,r,k);
return ret;
}
void change(int now,int l,int r,int pos,int value)
{
del(now,c[pos]);
insert(now,value);
if (l==r) return;
int mid=(l+r)>>,w=now<<;
if (pos<=mid) change(w,l,mid,pos,value); else change(w+,mid+,r,pos,value);
}
int ppre(int r,int value)
{
int x=root[r];
while (a[x]!=value)
if (a[x]>value) {if (son[x][]) x=son[x][]; else break;}
else {if (son[x][]) x=son[x][]; else break;}
if (a[x]==value)
{
splay(r,x,);
if (!son[x][]) return ;
x=son[x][];
while (son[x][]) x=son[x][];
return x;
}
while (f[x]&&a[x]>value) x=f[x];
if (a[x]<value) return x;
return ;
}
int ssucc(int r,int value)
{
int x=root[r];
while (a[x]!=value)
if (a[x]>value) {if (son[x][]) x=son[x][]; else break;}
else {if (son[x][]) x=son[x][]; else break;}
if (a[x]==value)
{
splay(r,x,);
if (!son[x][]) return ;
x=son[x][];
while (son[x][]) x=son[x][];
return x;
}
while (f[x]&&a[x]<value) x=f[x];
if (a[x]>value) return x;
return ;
}
int pre(int now,int l,int r,int value)
{
if (l>=left&&r<=right)
{
int x=ppre(now,value);
if (a[x]<value) return a[x];
x=find(now,);
return -;
}
int mid=(l+r)>>,w=now<<,ret=-;
if (left<=mid) ret=mmax(ret,pre(w,l,mid,value));
if (right>mid) ret=mmax(ret,pre(w+,mid+,r,value));
return ret;
}
int succ(int now,int l,int r,int value)
{
if (l>=left&&r<=right)
{
int x=ssucc(now,value);
if (a[x]>value) return (a[x]);
return inf;
}
int mid=(l+r)>>,w=now<<,ret=inf;
if (left<=mid) ret=mmin(ret,succ(w,l,mid,value));
if (right>mid) ret=mmin(ret,succ(w+,mid+,r,value));
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int i,kind,x,y,z,min,max,ans,mid;
for (i=;i<=n;i++) scanf("%d",&c[i]);
tot=;
a[]=-,a[]=;
build(,,n);
for (i=;i<=m;i++)
{
scanf("%d%d%d",&kind,&x,&y);
if (kind!=) scanf("%d",&z);
if (kind==)
{
left=x,right=y;
printf("%d\n",getrank(,,n,z)+);
continue;
}
if (kind==)
{
left=x,right=y;
min=,max=;
while (min<=max)
{
mid=(min+max)>>;
if (getrank(,,n,mid)<z) {ans=mid; min=mid+;} else max=mid-;
}
printf("%d\n",ans);
continue;
}
if (kind==)
{
change(,,n,x,y);
c[x]=y;
continue;
}
if (kind==)
{
left=x,right=y;
printf("%d\n",pre(,,n,z));
continue;
}
left=x,right=y;
printf("%d\n",succ(,,n,z));
}
return ;
}
然后是我的AC code:
/*调了好久，一部分原因是做这道题时学长讲新课，没时间调这道题。今天终于调出来了，然后把三篇平衡树的博客一起写出来了。这个题的题解在上面sth神犇的模板里有，主要是那个二分k值是本题的特色。我这道题一直WA的原因是快速读入没有判断负号(╯‵□′)╯︵┻━┻*/
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline const int max(const int &a,const int &b){return a>b?a:b;}
inline const int min(const int &a,const int &b){return a<b?a:b;}
struct node{
node();
node *fa,*ch[];
int sum,d;
short pl(){return this==fa->ch[];}
void count(){sum=ch[]->sum+ch[]->sum+;}
}*null;
node::node(){fa=ch[]=ch[]=null;sum=;}
int data[],N,M;
node *ROOT[<<];
int getint(){char c;int fh=;while(!isdigit(c=getchar()))if (c=='-')fh=-;int a=c-'';while(isdigit(c=getchar()))a=a*+c-'';return a*fh;}
namespace Splay{
void Builda(){
null=new node;
*null=node();
}
void rotate(node *k,int rt){
node *r=k->fa;
if (k==null||r==null) return;
int x=k->pl()^;
r->ch[x^]=k->ch[x];
r->ch[x^]->fa=r;
if (r->fa==null) ROOT[rt]=k;
else r->fa->ch[r->pl()]=k;
k->fa=r->fa; r->fa=k;
k->ch[x]=r;
r->count(); k->count();
}
void splay(int rt,node *r,node *tar=null){
for (;r->fa!=tar;rotate(r,rt))
if (r->fa->fa!=tar)rotate(r->pl()==r->fa->pl()?r->fa:r,rt);
}
void insert(int rt,int x){
node *r=ROOT[rt];
if (ROOT[rt]==null){
ROOT[rt]=new node;
*ROOT[rt]=node();
ROOT[rt]->d=x;
ROOT[rt]->count();
return;
}
while (){
int c;
if (x<r->d) c=;
else c=;
if (r->ch[c]==null){
r->ch[c]=new node;
*r->ch[c]=node();
r->ch[c]->fa=r;
r->ch[c]->d=x;
splay(rt,r->ch[c]);
return;
}else r=r->ch[c];
}
}
void build(int rt,int l,int r){
ROOT[rt]=null;
for(int i=l;i<=r;++i) insert(rt,data[i]);
}
node *kth(int rt,int x){
node *r=ROOT[rt];
while (r!=null){
if (x<r->d) r=r->ch[];
else if (x>r->d) r=r->ch[];
else return r;
}return r;
}
node *rightdown(node *r){
while (r->ch[]!=null){
r=r->ch[];
}return r;
}
void deletee(int rt,int x){
node *r=kth(rt,x);
splay(rt,r);
if ((r->ch[]==null)&&(r->ch[]==null)){
ROOT[rt]=null;
delete r;
}else if (r->ch[]==null){
r->ch[]->fa=null;
ROOT[rt]=r->ch[];
delete r;
}else if (r->ch[]==null){
r->ch[]->fa=null;
ROOT[rt]=r->ch[];
delete r;
}else{
splay(rt,rightdown(r->ch[]),ROOT[rt]);
r->ch[]->ch[]=r->ch[];
r->ch[]->fa=r->ch[];
r->ch[]->fa=null;
r->ch[]->count();
ROOT[rt]=r->ch[];
delete r;
}
}
int predd(node *r,int x){
if (r==null) return -;
if (x<=r->d) return predd(r->ch[],x);
else return max(r->d,predd(r->ch[],x));
}
int pross(node *r,int x){
if (r==null) return 1E8+;
if (x>=r->d) return pross(r->ch[],x);
else return min(r->d,pross(r->ch[],x));
}
node *get1(node *r,int x){
if (r==null) return null;
if (x<r->d) return get1(r->ch[],x);
if (x>r->d) return get1(r->ch[],x);
node *rr=get1(r->ch[],x);
if (rr!=null) return rr; else return r;
}
int quee1(int rt,int x){
node *r=get1(ROOT[rt],x);
if (r!=null){
splay(rt,r);
return r->ch[]->sum;
}else{
insert(rt,x);
int anss=ROOT[rt]->ch[]->sum;
deletee(rt,x);
return anss;
}
}
int quee2(int rt,int x){
node *r=get1(ROOT[rt],x);
if (r!=null){
splay(rt,r);
return r->ch[]->sum;
}else{
insert(rt,x);
int anss=ROOT[rt]->ch[]->sum;
deletee(rt,x);
return anss;
}
}
}
void buildtree(int l,int r,int rt){
Splay::build(rt,l,r);
if (l==r) {Splay::build(rt,l,r);return;}
int mid=(l+r)>>;
buildtree(l,mid,rt<<);
buildtree(mid+,r,rt<<|);
}
int que1(int L,int R,int k,int l,int r,int rt){
if ((L<=l)&&(r<=R)) return Splay::quee1(rt,k);
int mid=(l+r)>>,s=;
if (L<=mid) s+=que1(L,R,k,l,mid,rt<<);
if (R>mid) s+=que1(L,R,k,mid+,r,rt<<|);
return s;
}
int que2(int L,int R,int k,int l,int r,int rt){
if ((L<=l)&&(r<=R)) return Splay::quee2(rt,k);
int mid=(l+r)>>,s=;
if (L<=mid) s+=que2(L,R,k,l,mid,rt<<);
if (R>mid) s+=que2(L,R,k,mid+,r,rt<<|);
return s;
}
void que3(int pos,int k,int l,int r,int rt){
if ((l<=pos)&&(pos<=r)){
Splay::deletee(rt,data[pos]);
Splay::insert(rt,k);
}if (l==r) return; int mid=(l+r)>>;
if (pos<=mid) que3(pos,k,l,mid,rt<<);
if (pos>mid) que3(pos,k,mid+,r,rt<<|);
}
int que4(int L,int R,int k,int l,int r,int rt){
if ((L<=l)&&(r<=R)) return Splay::predd(ROOT[rt],k);
int mid=(l+r)>>,s=-;
if (L<=mid) s=que4(L,R,k,l,mid,rt<<);
if (R>mid) s=max(s,que4(L,R,k,mid+,r,rt<<|));
return s;
}
int que5(int L,int R,int k,int l,int r,int rt){
if ((L<=l)&&(r<=R)) return Splay::pross(ROOT[rt],k);
int mid=(l+r)>>,s=1E8+;
if (L<=mid) s=que5(L,R,k,l,mid,rt<<);
if (R>mid) s=min(s,que5(L,R,k,mid+,r,rt<<|));
return s;
}
int main(){
Splay::Builda();
N=getint();M=getint();
for(int i=;i<=N;++i)data[i]=getint();
buildtree(,N,);
while (M){M--;
int x=getint();
switch (x){
int l,r,k,pos,ans,left,right,mid;
case :
l=getint(),r=getint(),k=getint();
printf("%d\n",que1(l,r,k,,N,)+);
break;
case :
l=getint(),r=getint(),k=getint(),left=,right=1E8;
while (left<=right){
mid=(left+right)>>;
if (que2(l,r,mid,,N,)+<=k) ans=mid,left=mid+;
else right=mid-;
}printf("%d\n",ans);
break;
case :
pos=getint(),k=getint();
que3(pos,k,,N,);
data[pos]=k;
break;
case :
l=getint(),r=getint(),k=getint();
printf("%d\n",que4(l,r,k,,N,));
break;
case :
l=getint(),r=getint(),k=getint();
printf("%d\n",que5(l,r,k,,N,));
break;
}
}
return ;
}
这样就可以了