注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

jytnb1的博客

日影斑驳,朽日浮尘;韶光荏苒,逡巡不前。

 
 
 

日志

 
 
关于我

有志者,事竟成,苦心人,天不负。

网易考拉推荐

【bzoj】3196: Tyvj 1730 二逼平衡树  

2015-10-20 19:57:43|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
哎,我真的是二逼。。。一开始还把区间线段树套在外面,于是复杂度不对了。刚刚学会了线段树动态开结点,我就想到了这题(我曾经用线段树套Splay,结果严重超时【bzoj】3196: Tyvj 1730 二逼平衡树 - jytnb1 - jytnb1的博客)。然而Rxd还是说:“这题不是很傻,我初二就A掉了。”差距啊!!!【bzoj】3196: Tyvj 1730 二逼平衡树 - jytnb1 - jytnb1的博客
题目链接:BZOJ3196

3196: Tyvj 1730 二逼平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1457  Solved: 626
Description
您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)
Input
第一行两个数 n,m 表示长度为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的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继
Output
对于操作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.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数
=============================================================
这题确实很傻,权值线段树套区间线段树(权值线段树一定要套在外面),再动态开结点即可。然而我并不会Treap,更别说线段树套Treap了。
=============================================================

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50500,M=10001000;
int i,j,k,n,m,ch,nls,nn,T_sz,f;
int rt[N<<3],a[N],Ls[N<<1];
struct num {int o,l,r,k;} Nm[N];
struct tree {int ls,rs,sm;} T[M];
void R(int &x)
{
f=x=0;ch=getchar();
while (ch<'0' || '9'<ch) {if (ch=='-') f=1;ch=getchar();}
while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
if (f) x=-x;
}
int find(int x)
{
int l=1,r=nls,mid;
while (l<r)
{
mid=(l+r-1)>>1;
if (Ls[mid]<x) l=mid+1;
else r=mid;
}
return l;
}
void T_change(int L,int R,int x,int ad,int &k)
{
if (!k) k=++T_sz;
T[k].sm+=ad;
if (L<R)
{
int mid=(L+R)>>1;
if (x<=mid) T_change(L,mid,x,ad,T[k].ls);
else T_change(mid+1,R,x,ad,T[k].rs);
}
}
void Tr_change(int L,int R,int x,int ad,int k)
{
T_change(1,n,x,ad,rt[k]);
if (L<R)
{
int mid=(L+R)>>1;
if (a[x]<=mid) Tr_change(L,mid,x,ad,k<<1);
else Tr_change(mid+1,R,x,ad,k<<1|1);
}
}
int T_sum(int L,int R,int l,int r,int k)
{
if (!k) return 0;
if (L==l && R==r) return T[k].sm;
int mid=(L+R)>>1;
if (r<=mid) return T_sum(L,mid,l,r,T[k].ls);
if (l>mid) return T_sum(mid+1,R,l,r,T[k].rs);
return T_sum(L,mid,l,mid,T[k].ls)+T_sum(mid+1,R,mid+1,r,T[k].rs);
}
int Tr_rank(int L,int R,int l,int r,int tl,int tr,int k)
{
if (L==l && R==r) return T_sum(1,n,tl,tr,rt[k]);
int mid=(L+R)>>1;
if (r<=mid) return Tr_rank(L,mid,l,r,tl,tr,k<<1);
if (l>mid) return Tr_rank(mid+1,R,l,r,tl,tr,k<<1|1);
return Tr_rank(L,mid,l,mid,tl,tr,k<<1)+Tr_rank(mid+1,R,mid+1,r,tl,tr,k<<1|1);
}
int Tr_num(int L,int R,int x,int tl,int tr,int k)
{
if (L==R) return L;
int mid=(L+R)>>1;
int t=T_sum(1,n,tl,tr,rt[k<<1]);
if (x<=t) return Tr_num(L,mid,x,tl,tr,k<<1);
return Tr_num(mid+1,R,x-t,tl,tr,k<<1|1);
}
int main()
{
R(n);R(m);
for (i=1;i<=n;i++)
{
R(a[i]);
Ls[++nn]=a[i];
}
for (i=1;i<=m;i++)
{
R(Nm[i].o);
if (Nm[i].o==3)
{
R(Nm[i].l),R(Nm[i].k);
Ls[++nn]=Nm[i].k;
}
else R(Nm[i].l),R(Nm[i].r),R(Nm[i].k);
}
sort(Ls+1,Ls+nn+1);
for (i=1;i<nn;i++) if (Ls[i]!=Ls[i+1]) Ls[++nls]=Ls[i];
Ls[++nls]=Ls[nn];
for (i=1;i<=n;i++)
{
a[i]=find(a[i]);
Tr_change(1,nls,i,1,1);
}
for (i=1;i<=m;i++)
{
if (Nm[i].o==1)
{
ch=find(Nm[i].k);
if (ch==1) puts("1");
else printf("%d\n",Tr_rank(1,nls,1,ch-1,Nm[i].l,Nm[i].r,1)+1);
}
if (Nm[i].o==2) printf("%d\n",Ls[Tr_num(1,nls,Nm[i].k,Nm[i].l,Nm[i].r,1)]);
if (Nm[i].o==3)
{
Tr_change(1,nls,Nm[i].l,-1,1);
a[Nm[i].l]=find(Nm[i].k);
Tr_change(1,nls,Nm[i].l,1,1);
}
if (Nm[i].o==4)
{
if (Nm[i].k>Ls[nls]) ch=nls;
else ch=find(Nm[i].k)-1;
ch=Tr_rank(1,nls,1,ch,Nm[i].l,Nm[i].r,1);
printf("%d\n",Ls[Tr_num(1,nls,ch,Nm[i].l,Nm[i].r,1)]);
}
if (Nm[i].o==5)
{
if (Nm[i].k<Ls[1]) printf("%d\n",Ls[Tr_num(1,nls,1,Nm[i].l,Nm[i].r,1)]);
else
{
ch=find(Nm[i].k);
if (Ls[ch]!=Nm[i].k) ch--;
ch=Tr_rank(1,nls,1,ch,Nm[i].l,Nm[i].r,1);
printf("%d\n",Ls[Tr_num(1,nls,ch+1,Nm[i].l,Nm[i].r,1)]);
}
}
}
}


  评论这张
 
阅读(32)| 评论(12)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017