http://acm.hust.edu.cn/vjudge/problem/42297

【题目描述】

写一种数据结构,来维护一个有序数列,其中需要提供以下操作:

1.查询k在区间内的排名

2.查询区间内排名为k的值

3.修改某一位值上的数值

4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)

5.查询k在区间内的后继(后继定义为大于x,且最小的数)

【输入格式】

第一行两个数 n,m( n,m <= 50000 )表示长度为n的有序序列和m个操作

第二行有n个数,表示有序序列

下面有m行,opt表示操作标号

若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名

若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数

若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k

若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱(没有前驱输出no)

若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继(没有后继输出no)

【输出格式】

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6

4 2 2 1 9 4 0 1 1

2 1 4 3

3 4 10

2 1 4 3

1 2 5 9

4 3 9 5

5 2 8 5

Sample Output

2

4

3

4

9

HINT:

1、序列中每个数的数据范围:[0,1e8]

2、虽然原题没有,但事实上5操作的k可能为负数

这题我在bzoj上AC,在tvoj上最后两个点TLE(然而并不知道怎么优化)。

昨天中午打了一个中午,晚上调了一个钟,今天早上又调了两个钟。。呵呵。。

我的做法是在开一棵1~n的线段树t,每个节点(管理t[x].l~t[x].r)开一棵treap,把t[x].l~t[x].r的值全部放进去。为了防止找前驱后继的时候有问题,每棵treap上先放-Inf和Inf进去。

1.表示查询k在区间[l,r]的排名:用线段树找到[l,r]所需要用到的线段树上的节点,开一个数组存起来,然后一个个区间查询比k小的数的个数。

2.表示查询区间[l,r]内排名为k的数:mn和mx存下出现过的最小和最大的数是什么。二分一个数x,然后用1的方法看x的排名。

这里注意一个问题:找的是排名<=k的最大的数。

例如:1 2 3 3 3 5,查询3的排名是3,但是如果我们要找排名为4的数,答案依然是3。

3.单点修改:顺着线段树走下去,中途所经过的点,都要在它那棵treap上del原来的数,ins新数

4.找前驱:就在线段树上先找出所有要用到的点,再一个个进去找在这棵treap树上的前驱x,取最大值。

5.找后继:同上。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int N=,TN=*+,Inf=(int)1e9;
struct tr_node{
int son[],n,c,f,d;
}c[*TN];
struct xd_node{
int lc,rc,l,r,root;
}t[**N];
int tl,cl,sl;
int w[*N],s[*N]; void updata(int x)
{
if(!x) return;
int lc=c[x].son[],rc=c[x].son[];
c[x].c=c[x].n+c[lc].c+c[rc].c;
} void add(int d,int f)
{
cl++;
c[cl].f=f;c[cl].d=d;
c[cl].n=c[cl].c=;
c[cl].son[]=c[cl].son[]=;
if(d<c[f].d) c[f].son[]=cl;
else c[f].son[]=cl;
updata(f);//debug
} int find_ip(int d,int id)
{
int x=t[id].root;
while(c[x].d!=d)
{
if(d<c[x].d)
{
if(c[x].son[]) x=c[x].son[];
else break;
}
else
{
if(c[x].son[]) x=c[x].son[];
else break;
}
}
return x;
} void rotate(int x)
{
int y=c[x].f,z=c[y].f,w,r,R;
w=(c[y].son[]==x) ? :; r=c[x].son[w];R=y;
c[R].son[-w]=r;
if(r) c[r].f=R; r=x;R=z;
c[R].son[(c[z].son[]==y) ? :]=r;
c[r].f=R; r=y;R=x;
c[R].son[w]=r;
c[r].f=R; updata(y);
updata(x);
} void splay(int x,int rt,int id)
{
while(c[x].f!=rt)
{
int y=c[x].f,z=c[y].f;
if(z==rt) rotate(x);
else
{
if((c[z].son[]==y) == (c[y].son[]==x)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
if(rt==) t[id].root=x;
} void ins(int d,int id)
{
int root=t[id].root;
if(root==) {add(d,);t[id].root=cl;return;}
int x=find_ip(d,id);
if(c[x].d==d) c[x].n++;
else add(d,x);
updata(x);
splay(x,,id);
} int build_xd_tree(int l,int r)
{
int x=++tl;
t[x].l=l;t[x].r=r;
t[x].lc=t[x].rc=;
t[x].root=;
if(l<r)
{
int mid=(l+r)>>;
t[x].lc=build_xd_tree(l,mid);
t[x].rc=build_xd_tree(mid+,r);
ins(-Inf,x);ins(Inf,x);
for(int i=l;i<=r;i++) ins(w[i],x);
}
else ins(-Inf,x),ins(Inf,x),ins(w[t[x].l],x);//l==r
return x;
} void find_xd_id(int x,int l,int r)
{
if(t[x].l==l && t[x].r==r) {s[++sl]=x;return;}
int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;
if(r<=mid) find_xd_id(lc,l,r);
else if(l>mid) find_xd_id(rc,l,r);
else find_xd_id(lc,l,mid),find_xd_id(rc,mid+,r);
} int find_qq(int d,int id)
{
int x=find_ip(d,id);splay(x,,id);//debug splay(x,0,id)
if(c[x].d>=d && c[x].son[])
{
x=c[x].son[];
while(c[x].son[]) x=c[x].son[];
}
if(c[x].d>=d) x=;
return x;
} int find_hj(int d,int id)
{
int x=find_ip(d,id);splay(x,,id);//debug
if(c[x].d<=d && c[x].son[])
{
x=c[x].son[];
while(c[x].son[]) x=c[x].son[];
}
if(c[x].d<=d) x=;
return x;
} void del(int d,int id)
{
int x=find_ip(d,id);splay(x,,id);
if(c[x].n>=) {c[x].n--;return;}
int x0=find_qq(d,id);
int x1=find_hj(d,id);
splay(x0,,id);
splay(x1,x0,id);
c[x1].son[]=;
updata(x1);
} void change(int x,int p,int d)
{
if(t[x].l==t[x].r)
{
del(w[p],x);ins(d,x);
return;
}
int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;
if(p<=mid) change(lc,p,d);
else change(rc,p,d);
del(w[p],x);ins(d,x);
} int find_rk(int d,int id)//the number of all that <d
{
int root=t[id].root;
int x=find_qq(d,id);
splay(x,,id);
return c[c[x].son[]].c-+c[x].n;
} int opt1(int k,int l,int r)
{
int ans=;
sl=;find_xd_id(,l,r);
for(int j=;j<=sl;j++)
ans+=find_rk(k,s[j]);
return ans+;
} int minn(int x,int y){return x<y ? x:y;}
int maxx(int x,int y){return x>y ? x:y;} int find_rank(int k)
{
int ans=;
for(int i=;i<=sl;i++)
ans+=find_rk(k,s[i]);
return ans+;
} int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
tl=;cl=;
int mn=Inf,mx=-Inf;
for(int i=;i<=n;i++)
{
scanf("%d",&w[i]);
mn=minn(mn,w[i]);
mx=maxx(mx,w[i]);
}
build_xd_tree(,n);
for(int i=;i<=m;i++)
{
int k,l,r,pos,opt;
scanf("%d",&opt);
if(opt!=) scanf("%d%d%d",&l,&r,&k);
else scanf("%d%d",&pos,&k);
if(opt==)
{
int ans=;
sl=;find_xd_id(,l,r);
printf("%d\n",find_rank(k));
}
if(opt==)
{
sl=;find_xd_id(,l,r);
int ll=mn,rr=mx;
while(ll!=rr)
{
int mid=(ll+rr+)>>;
int now=find_rank(mid);
if(now<=k) ll=mid;//注意
else rr=mid-;
}
printf("%d\n",ll);
}
if(opt==)
{
change(,pos,k);
w[pos]=k;
mn=minn(mn,k);
mx=maxx(mx,k);
}
if(opt==)
{
int ans=-Inf;
sl=;find_xd_id(,l,r);
for(int j=;j<=sl;j++) ans=maxx(ans,c[find_qq(k,s[j])].d);
if(ans!=-Inf) printf("%d\n",ans);
else printf("no\n");
}
if(opt==)
{
int ans=Inf;
sl=;find_xd_id(,l,r);
for(int j=;j<=sl;j++) ans=minn(ans,c[find_hj(k,s[j])].d);
if(ans!=Inf) printf("%d\n",ans);
else printf("no\n");
}
}
return ;
}
05-22 23:14
查看更多