| 记录编号 |
364788 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[TYVJ1730]二逼平衡树 |
最终得分 |
100 |
| 用户昵称 |
 半汪 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
4.282 s |
| 提交时间 |
2017-01-18 07:59:47 |
内存使用 |
118.57 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
const int maxe=10000010;
int n,m,a[maxn];
int son[maxe][2],sumt[maxe],a0[maxn],M,N=1,b[maxn],now,root[maxn],tot;
bool getif=0;
struct DO{
int opt,l,r,k;
}d[50010];
#define L(x) son[x][0]
#define R(x) son[x][1]
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int ask(int rt,int l,int r,int s,int t){
if(s<=l&&r<=t)return sumt[rt];
int mid=(l+r)>>1;
if(t<=mid)return ask(L(rt),l,mid,s,t);
if(s>mid)return ask(R(rt),mid+1,r,s,t);
return ask(L(rt),l,mid,s,t)+ask(R(rt),mid+1,r,s,t);
}
int query(int rt,int l,int r,int s,int t,int ss,int tt){
if(s<=l&&r<=t)return ask(root[rt],1,N,ss,tt);
int mid=(l+r)>>1;
if(t<=mid)return query(lson,s,t,ss,tt);
if(s>mid)return query(rson,s,t,ss,tt);
return query(lson,s,t,ss,tt)+query(rson,s,t,ss,tt);
}
int rank(int l,int r,int k){
if(k==1)return 1;
int ans=query(1,1,n,l,r,1,k-1);
return ans+1;
}
void get_root(int rt,int l,int r,int s,int t){
if(s<=l&&r<=t){
b[++now]=root[rt];return;}
int mid=(l+r)>>1;
if(s<=mid)get_root(lson,s,t);
if(t>mid)get_root(rson,s,t);
}
int get_kth(int l,int r,int k){
now=0;
get_root(1,1,n,l,r);
int ll=1,rr=N,mid;
while(ll!=rr){
mid=(ll+rr)>>1;
int sum=0;
for(int i=1;i<=now;i++)sum+=sumt[L(b[i])];
if(sum>=k){
for(int i=1;i<=now;i++)b[i]=L(b[i]);
rr=mid;
}
else{
k-=sum;
for(int i=1;i<=now;i++)b[i]=R(b[i]);
ll=mid+1;
}
}
return a0[ll];
}
void insert(int &rt,int l,int r,int v,int w){
if(!rt)rt=++tot;
if(l==r){
sumt[rt]+=w;return;}
int mid=(l+r)>>1;
if(v<=mid)insert(L(rt),l,mid,v,w);
if(v>mid)insert(R(rt),mid+1,r,v,w);
sumt[rt]=sumt[L(rt)]+sumt[R(rt)];
}
void Add(int rt,int l,int r,int qv,int v,int w){
insert(root[rt],1,N,v,w);
if(l==r)return;
int mid=(l+r)>>1;
if(qv<=mid)Add(lson,qv,v,w);
else Add(rson,qv,v,w);
}
void change(int pos,int v){
// cout<<a[pos]<<" "<<v<<endl;
Add(1,1,n,pos,a[pos],-1);
Add(1,1,n,pos,v,1);
a[pos]=v;
}
void get_back(int rt,int l,int r,int &ans){
if(l==r){
ans=min(ans,l);return;}
int mid=(l+r)>>1;
if(sumt[L(rt)])get_back(L(rt),l,mid,ans);
else get_back(R(rt),mid+1,r,ans);
}
void Find_back(int rt,int l,int r,int k,int &ans){
if(l==r)return;
int mid=(l+r)>>1;
if(k<=mid){
Find_back(L(rt),l,mid,k,ans);
if(sumt[R(rt)]&&!getif)get_back(R(rt),mid+1,r,ans);
}
else Find_back(R(rt),mid+1,r,k,ans);
}
void find_back(int rt,int l,int r,int s,int t,int k,int &ans,int flag){
if(s<=l&&r<=t){
getif=0;
if(!flag)Find_back(root[rt],1,N,k,ans);
else get_back(root[rt],1,N,ans);
return;
}
int mid=(l+r)>>1;
if(s<=mid)find_back(lson,s,t,k,ans,flag);
if(t>mid)find_back(rson,s,t,k,ans,flag);
}
int query_back(int l,int r,int k){
int ans=0x7f7f7f7f;
if(k<1)find_back(1,1,n,l,r,k,ans,1);
else find_back(1,1,n,l,r,k,ans,0);
return a0[ans];
}
void get_front(int rt,int l,int r,int &ans){
if(l==r){
ans=max(ans,l);return;}
int mid=(l+r)>>1;
if(sumt[R(rt)])get_front(R(rt),mid+1,r,ans);
else get_front(L(rt),l,mid,ans);
}
void Find_front(int rt,int l,int r,int k,int &ans){
if(l==r)return;
int mid=(l+r)>>1;
if(k<=mid)Find_front(L(rt),l,mid,k,ans);
else {
Find_front(R(rt),mid+1,r,k,ans);
if(sumt[L(rt)]&&!getif)get_front(L(rt),l,mid,ans);
}
}
void find_front(int rt,int l,int r,int s,int t,int k,int &ans,int flag){
if(s<=l&&r<=t){
getif=0;
if(!flag)Find_front(root[rt],1,N,k,ans);
else get_front(root[rt],1,N,ans);
return;
}
int mid=(l+r)>>1;
if(s<=mid)find_front(lson,s,t,k,ans,flag);
if(t>mid)find_front(rson,s,t,k,ans,flag);
}
int query_pre(int l,int r,int k){
int ans=-1;
if(k>N)find_front(1,1,n,l,r,k,ans,1);
else find_front(1,1,n,l,r,k,ans,0);
return a0[ans];
}
int main(){
freopen("psh.in","r",stdin);freopen("psh.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),a0[++M]=a[i];
for(int i=1;i<=m;i++){
// read(d[i].opt);
//if(d[i].opt!=3)read(d[i].l),read(d[i].r),read(d[i].k);
// else read(d[i].l),read(d[i].k),a0[++M]=d[i].k;
scanf("%d",&d[i].opt);
if(d[i].opt!=3)scanf("%d%d%d",&d[i].l,&d[i].r,&d[i].k);
else scanf("%d%d",&d[i].l,&d[i].k),a0[++M]=d[i].k;
}
sort(a0+1,a0+M+1);
for(int i=2;i<=M;i++)if(a0[i]!=a0[i-1])a0[++N]=a0[i];
for(int i=1;i<=n;i++)a[i]=lower_bound(a0+1,a0+N+1,a[i])-a0;
// for(int i=1;i<=N;i++)cout<<a[i]<<endl;
for(int i=1;i<=n;i++)Add(1,1,n,i,a[i],1);
for(int i=1;i<=m;i++){
if(d[i].opt==1||d[i].opt==3||d[i].opt==4)d[i].k=lower_bound(a0+1,a0+N+1,d[i].k)-a0;
if(d[i].opt==5){
int k1=lower_bound(a0+1,a0+N+1,d[i].k)-a0;
if(a0[k1]>d[i].k)k1--;
d[i].k=k1;
}
}
for(int i=1;i<=m;i++){
if(d[i].opt==1)printf("%d\n",rank(d[i].l,d[i].r,d[i].k));
if(d[i].opt==2)printf("%d\n",get_kth(d[i].l,d[i].r,d[i].k));
if(d[i].opt==3)change(d[i].l,d[i].k);
if(d[i].opt==4)printf("%d\n",query_pre(d[i].l,d[i].r,d[i].k));
if(d[i].opt==5)printf("%d\n",query_back(d[i].l,d[i].r,d[i].k));
}
return 0;
}
/*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*/