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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【恶心题】【数据结构】二逼平衡树  

2014-04-28 20:21:02|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@二逼平衡树 on tyvj
题目就是带单点修改的区间第k大
目前有四种解法
①线段树套平衡树 O(nlogn^3)
②树状数组套主席树 O(nlogn^2)
③线段树套线段树 O(nlogn^3) [详细看这里]
④分块+平衡树 O( n*log(sqrt(n))*sqrt(n) ) 
我用的是第二种做法
做法①③因为询问要二分答案,所以比较慢
BZ上大概4000+~6000+ms,
做法②大概在3000+ms
 但是空间消耗会比较可怕……需要小心

我写这个纠结了好长时间……因为是第一次写树套树……
一开始求k的前后趋的时候都是要先插入k然后再查k的rank和个数,最后再求kth……而且各种错误
最后没有办法请教了Claris神犇,原来只要写一个求和函数sum然后结合Kth就能很简单地求出前后趋了……(具体见程序)
一开始犯了写傻逼错误,l和r写反啊什么的……
最后读入优化写挂了蛋疼了好长时间- -、
无数次RE后终于A了!
比较奇妙的是用时居然和题目一样
托了Claris神犇的福进了第二页
【恶心题】【数据结构】二逼平衡树 - 时光机 - 时光机TimeMachine

/*
FenwickTree+Functioned Segtree

*/
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100000+10;
const int F = 10800010+1;
struct ASK{
int l,r,k,t;
}ask[N/2];
int n,m,use[N],data[N],Pdata[N];
int tree[F],lson[F],rson[F],T[N],Tn;
int Build(int l=1,int r=Pdata[0]){
int mid=(l+r)/2,re=++Tn;
if(l<r){
lson[re]=Build(l,mid);
rson[re]=Build(mid+1,r);
}return re;
}
int set(int ro,int x,int val){
int newr=++Tn,re,l=1,r=Pdata[0];re=newr;
tree[newr]=tree[ro]+val;
while(l<r){
int mid=(l+r)/2;
if(x<=mid){
r=mid;
rson[newr]=rson[ro];lson[newr]=++Tn;
ro=lson[ro];newr=lson[newr];
}else{
l=mid+1;
lson[newr]=lson[ro];rson[newr]=++Tn;
ro=rson[ro];newr=rson[newr];
}
tree[newr]=tree[ro]+val;
}return re;
}
void insert(int r,int x,int val){for(;r<=n;r+=r&-r) T[r]=set(T[r],x,val);}
int kth(int lr,int rr,int k){
int l=1,r=Pdata[0],a;
for(a=lr-1;a;a-=a&-a) use[a]=T[a];
for(a=rr ;a;a-=a&-a) use[a]=T[a];
while(l<r){
int mid=(l+r)/2,tmp=0;
for(a=rr;a;a-=a&-a) tmp+=tree[lson[use[a]]];
for(a=lr-1;a;a-=a&-a) tmp-=tree[lson[use[a]]];
if(k<=tmp){
r=mid;
for(a=rr;a;a-=a&-a) use[a]=lson[use[a]];
for(a=lr-1;a;a-=a&-a) use[a]=lson[use[a]];

}else{
k-=tmp;l=mid+1;
for(a=rr;a;a-=a&-a) use[a]=rson[use[a]];
for(a=lr-1;a;a-=a&-a) use[a]=rson[use[a]];
}
}return Pdata[l];
}
int Ask(int ro,int l,int r,int la,int ra){
if(la<=l&&r<=ra) return tree[ro];
int re=0,mid=(l+r)/2;
if(la<=mid)re+=Ask(lson[ro],l,mid,la,ra);
if(mid+1<=ra)re+=Ask(rson[ro],mid+1,r,la,ra);
return re;
}
int sum(int x,int l,int r){
int re=0;
for(;x;x-=x&-x) re+=Ask(T[x],1,Pdata[0],l,r);
return re;
}
int Rank(int l,int r,int x){return sum(r,1,x-1)-sum(l-1,1,x-1)+1;}
int pre(int l,int r,int x){return kth(l,r,sum(r,1,x-1)-sum(l-1,1,x-1));}
int suc(int l,int r,int x){
int a,b;
a=sum(r,1,x);
b=sum(l-1,1,x);
return kth(l,r,a-b+1);
}
void Build_Hash(){
sort(Pdata+1,Pdata+1+Pdata[0]);
Pdata[0]=unique(Pdata+1,Pdata+1+Pdata[0])-Pdata-1;
}
int find(int x){
int l=1,r=Pdata[0];
while(l<r){
int mid=(l+r)/2;
if(x==Pdata[mid]) return mid;
else if(x<Pdata[mid]) r=mid;
else l=mid+1;
}return l;
}
int scan(){
char c=' ';int fh=1,re=0;
while(c==' '||c=='\n'||c=='\r')c=getchar(); //要加'\r'
if(c=='+'){fh=1;c=getchar();}
if(c=='-'){fh=-1;c=getchar();} //-1写成1
while('0'<=c&&c<='9'){
re=re*10+c-'0';
c=getchar();
}
return re*fh;
}
int main(){
int i,j,a,b;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
n=scan();m=scan();
for(i=1;i<=n;i++)
data[i]=Pdata[i]=scan();
for(i=1,Pdata[0]=n;i<=m;i++){
a=ask[i].t=scan();
ask[i].l=scan();
if(a!=3) ask[i].r=scan();
ask[i].k=scan();
if(a!=2) Pdata[++Pdata[0]]=ask[i].k;
}
Build_Hash();
T[0]=Build(1,n);
int fuck=0,tmp;
for(i=1;i<=n;i++) T[i]=T[0];
for(i=1;i<=n;i++) insert(i,find(data[i]),1);
for(i=1;i<=m;i++) if(ask[i].t!=2)ask[i].k=find(ask[i].k);
for(i=1;i<=m;i++){
if(ask[i].t!=3&&fuck) printf("\n");
if(ask[i].t!=3) fuck++;
if(ask[i].t==1) printf("%d",tmp=Rank(ask[i].l,ask[i].r,ask[i].k));
if(ask[i].t==2) printf("%d",tmp=kth(ask[i].l,ask[i].r,ask[i].k));
if(ask[i].t==3){
insert(ask[i].l,find(data[ask[i].l]),-1);
insert(ask[i].l,ask[i].k,1);
data[ask[i].l] = Pdata[ask[i].k];
}if(ask[i].t==4) printf("%d",tmp=pre(ask[i].l,ask[i].r,ask[i].k));
if(ask[i].t==5) printf("%d",tmp=suc(ask[i].l,ask[i].r,ask[i].k));

}
return 0;
}

  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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