.
题意很清楚了吧。。
题解：树套树。我用了个线段树套splay。讲道理可以不用套splay的，但就当练模板了吧。
代码：
#include<bits/stdc++.h>
using namespace std;
struct Splay
{
struct pnt
{
int c,n,sz;
pnt *f,*s[2];
pnt(int x,pnt *f):c(x),f(f),n(1),sz(1)
{
s[0]=s[1]=0;
}
}*root;
Splay()
{
root=0;
}
void print(pnt*x)
{
if(!x)
return;
printf("*%d %d %d ",x->c,x->n,x->sz);
if(x->s[0])
printf("l:%d ",x->s[0]->c);
if(x->s[1])
printf("r:%d ",x->s[1]->c);
puts("");
print(x->s[0]);
print(x->s[1]);
}
void pushup(pnt *x)
{
x->sz=x->n;
if(x->s[0])
x->sz+=x->s[0]->sz;
if(x->s[1])
x->sz+=x->s[1]->sz;
}
void rot(pnt *x)
{
pnt *f=x->f,*ff=f->f,*R,*r;
bool w=(x==f->s[0]);
R=f;r=x->s[w];
R->s[1-w]=r;
if(r)
r->f=R;
R=ff;r=x;
if(R)
R->s[f==ff->s[1]]=r;
r->f=R;
R=x;r=f;
R->s[w]=r;
r->f=R;
pushup(f);
pushup(x);
}
void splay(pnt *x,pnt *rt)
{
while(x->f!=rt)
{
pnt *f=x->f,*ff=f->f;
if(ff==rt)
rot(x);
else if((x==f->s[0])==(f==ff->s[0]))
{
rot(f);
rot(x);
}
else
{
rot(x);
rot(x);
}
}
if(!rt)
root=x;
}
void add(int x,pnt *f)
{
// printf("f:%d\n",f->c);
pnt *p=new pnt(x,f);
if(x<f->c)
f->s[0]=p;
else
f->s[1]=p;
pushup(f);
splay(f,0);
}
pnt* fd_by_val(int x)
{
pnt *now=root;
while(now->c!=x)
{
if(x<now->c)
{
if(now->s[0])
now=now->s[0];
else
return now;
}
else
{
if(now->s[1])
now=now->s[1];
else
return now;
}
}
return now;
}
void ins(int x)
{
if(!root)
{
root=new pnt(x,0);
return;
}
pnt *f=fd_by_val(x);
// printf("%d\n",f->c);
if(f->c==x)
{
f->n++;
pushup(f);
splay(f,0);
}
else
{
add(x,f);
}
}
int getrank(int x)
{
pnt *now=fd_by_val(x);
splay(now,0);
// print(root);
if(now->c>=x)
{
if(now->s[0])
return now->s[0]->sz;
else
return 0;
}
else
{
if(now->s[0])
return now->s[0]->sz+now->n;
else
return now->n;
}
}
int qian(int x)
{
pnt *now=fd_by_val(x);
splay(now,0);/*
puts("");
print(root);
puts("");*/
if(now->c<x)
return now->c;
else
{
if(!now->s[0])
return -1;
now=now->s[0];
while(now->s[1])
now=now->s[1];
return now->c;
}
}
int hou(int x)
{
pnt *now=fd_by_val(x);
splay(now,0);
if(now->c>x)
return now->c;
else
{
if(!now->s[1])
return 2147483647;
now=now->s[1];
while(now->s[0])
now=now->s[0];
return now->c;
}
}
void del(int x)
{
pnt *hh=fd_by_val(x);/*
puts("a");
print(root);
puts("b");
printf("%d\n",hh->c);*/
splay(hh,0);/*
puts("c");
print(root);
puts("d");*/
if(hh->n>1)
{
hh->n--;
hh->sz--;
}
else if(!hh->s[0]&&!hh->s[1])
{
root=0;
delete hh;
}
else if(hh->s[0]&&!hh->s[1])
{
root=hh->s[0];
root->f=0;
delete hh;
}
else if(!hh->s[0]&&hh->s[1])
{
root=hh->s[1];
root->f=0;
delete hh;
}
else
{
pnt *now=hh->s[0];
while(now->s[1])
now=now->s[1];
splay(now,hh);
now->s[1]=hh->s[1];
hh->s[1]->f=now;
now->f=0;
root=now;
pushup(now);
delete hh;
}/*
puts("g");
print(root);
puts("f");*/
}
};
struct tree
{
int l,r;
tree *lc,*rc;
Splay c;
}*rt;
int n,m,a[50010];
tree* bt(int l,int r)
{
tree *i=new tree;
i->l=l;
i->r=r;
i->lc=i->rc=0;
if(l<r)
{
int md=l+r>>1;
i->lc=bt(l,md);
i->rc=bt(md+1,r);
}
return i;
}
void add(tree *i,int x,int p)
{
if(i->l==i->r)
{
i->c.ins(x);
return;
}
i->c.ins(x);
int md=i->l+i->r>>1;
tree *lc=i->lc,*rc=i->rc;
if(p<=md)
add(lc,x,p);
else
add(rc,x,p);
}
void chg(tree *i,int x,int p)
{
if(i->l==i->r)
{
i->c.del(a[p]);
i->c.ins(x);
return;
}
i->c.del(a[p]);
i->c.ins(x);
int md=i->l+i->r>>1;
tree *lc=i->lc,*rc=i->rc;
if(p<=md)
chg(lc,x,p);
else
chg(rc,x,p);
}
int getrank(tree *i,int l,int r,int x)
{
if(i->l==l&&i->r==r)
{/*
int hh=i->c.getrank(x);
printf("%d %d %d %d\n",l,r,x,hh);
return hh;*/
return i->c.getrank(x);
}
int md=i->l+i->r>>1;
tree *lc=i->lc,*rc=i->rc;
if(r<=md)
return getrank(lc,l,r,x);
else if(l>md)
return getrank(rc,l,r,x);
else
return getrank(lc,l,md,x)+getrank(rc,md+1,r,x);
}
int getkth(int l,int r,int k)
{
int ll=0,len=100000001;
while(len)
{
int md=ll+(len>>1);
if(getrank(rt,l,r,md)<k)
{
// printf("getrank(%d,%d,%d)=%d\n",l,r,md,getrank(rt,l,r,md));
ll=md+1;
len=len-(len>>1)-1;
}
else
len>>=1;
}
return ll-1;
}
int getqian(tree *i,int l,int r,int x)
{
if(i->l==l&&i->r==r)
{
// printf("%d %d %d\n",l,r,x);
return i->c.qian(x);
}
int md=i->l+i->r>>1;
tree *lc=i->lc,*rc=i->rc;
if(r<=md)
return getqian(lc,l,r,x);
else if(l>md)
return getqian(rc,l,r,x);
else
return max(getqian(lc,l,md,x),getqian(rc,md+1,r,x));
}
int gethou(tree *i,int l,int r,int x)
{
if(i->l==l&&i->r==r)
{
return i->c.hou(x);
}
int md=i->l+i->r>>1;
tree *lc=i->lc,*rc=i->rc;
if(r<=md)
return gethou(lc,l,r,x);
else if(l>md)
return gethou(rc,l,r,x);
else
return min(gethou(lc,l,md,x),gethou(rc,md+1,r,x));
}
void print(tree *i,int p)
{
if(!i)
return;
printf("%d %d\n",i->l,i->r);
i->c.print(i->c.root);
int md=i->l+i->r>>1;
if(p<=md)
print(i->lc,p);
else
print(i->rc,p);
}
int main()
{
scanf("%d%d",&n,&m);
rt=bt(1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
add(rt,a[i],i);
}/*
rt->c.print(rt->c.root);
puts("");*/
while(m--)
{
int op,l,r,k;
scanf("%d",&op);
switch(op)
{
case 1:
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",getrank(rt,l,r,k)+1);
break;
case 2:
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",getkth(l,r,k));
break;
case 3:
scanf("%d%d",&l,&k);
chg(rt,k,l);
a[l]=k;
break;
case 4:
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",getqian(rt,l,r,k));
break;
case 5:
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",gethou(rt,l,r,k));
break;
}/*
print(rt,l);
puts("");
if(op!=3)
{
print(rt,r);
puts("");
}*/
}
}