| 记录编号 |
396022 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[TYVJ1730]二逼平衡树 |
最终得分 |
100 |
| 用户昵称 |
 Cydiater |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.605 s |
| 提交时间 |
2017-04-17 20:53:03 |
内存使用 |
59.83 MiB |
显示代码纯文本
//OJ 1997
//by Cydiater
//2017.4.17
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;++i)
#define down(i,j,n) for(int i=j;i>=n;--i)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define FILE "psh"
const int MAXN=5e4+5;
const int oo=0x3f3f3f3f;
int N,M,a[MAXN],num[MAXN<<1],top=0,rts[MAXN][2],t0,t1;//0 L 1 R
int root[MAXN<<1];
struct Query{
int op,L,R,k,p;
}qry[MAXN];
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
namespace CMT{
struct tree{
int son[2],siz;
}t[MAXN*100];
int cnt=0;
inline int NewNode(int s0,int s1,int siz){
cnt++;
t[cnt].son[0]=s0;t[cnt].son[1]=s1;t[cnt].siz=siz;
return cnt;
}
void Build(int leftt,int rightt,int &k,int x,int p){
k=NewNode(t[x].son[0],t[x].son[1],t[x].siz+1);
if(leftt==rightt)return;
int mid=(leftt+rightt)>>1;
if(p<=mid) Build(leftt,mid,t[k].son[0],t[x].son[0],p);
if(p>=mid+1) Build(mid+1,rightt,t[k].son[1],t[x].son[1],p);
}
int Qrank(int leftt,int rightt,int num){
int siz=0;
up(i,1,t0)siz-=t[t[rts[i][0]].son[0]].siz;
up(i,1,t1)siz+=t[t[rts[i][1]].son[0]].siz;
if(leftt==rightt)return 1;
int mid=(leftt+rightt)>>1;
if(num<=mid){
up(i,1,t0)rts[i][0]=t[rts[i][0]].son[0];
up(i,1,t1)rts[i][1]=t[rts[i][1]].son[0];
return Qrank(leftt,mid,num);
}
if(num>=mid+1){
up(i,1,t0)rts[i][0]=t[rts[i][0]].son[1];
up(i,1,t1)rts[i][1]=t[rts[i][1]].son[1];
return siz+Qrank(mid+1,rightt,num);
}
}
int Qnum(int leftt,int rightt,int rnk){
int siz=0;
up(i,1,t0)siz-=t[t[rts[i][0]].son[0]].siz;
up(i,1,t1)siz+=t[t[rts[i][1]].son[0]].siz;
if(leftt==rightt)return leftt;
int mid=(leftt+rightt)>>1;
if(rnk<=siz){
up(i,1,t0)rts[i][0]=t[rts[i][0]].son[0];
up(i,1,t1)rts[i][1]=t[rts[i][1]].son[0];
return Qnum(leftt,mid,rnk);
}else{
up(i,1,t0)rts[i][0]=t[rts[i][0]].son[1];
up(i,1,t1)rts[i][1]=t[rts[i][1]].son[1];
return Qnum(mid+1,rightt,rnk-siz);
}
}
int Qcnt(int leftt,int rightt,int pos){
if(leftt==rightt){
int siz=0;
up(i,1,t0)siz-=t[rts[i][0]].siz;
up(i,1,t1)siz+=t[rts[i][1]].siz;
return siz;
}
int mid=(leftt+rightt)>>1;
if(pos<=mid){
up(i,1,t0)rts[i][0]=t[rts[i][0]].son[0];
up(i,1,t1)rts[i][1]=t[rts[i][1]].son[0];
return Qcnt(leftt,mid,pos);
}else{
up(i,1,t0)rts[i][0]=t[rts[i][0]].son[1];
up(i,1,t1)rts[i][1]=t[rts[i][1]].son[1];
return Qcnt(mid+1,rightt,pos);
}
}
void Modify(int leftt,int rightt,int &k,int pos,int val){
k=NewNode(t[k].son[0],t[k].son[1],t[k].siz+val);
if(leftt==rightt)return;
int mid=(leftt+rightt)>>1;
if(pos<=mid) Modify(leftt,mid,t[k].son[0],pos,val);
if(pos>=mid+1) Modify(mid+1,rightt,t[k].son[1],pos,val);
}
}
namespace BIT{
inline int lowbit(int i){return i&(-i);}
void Push(int p,int tag){
for(int i=p;i>=1;i-=lowbit(i)){
if(!tag)rts[++t0][0]=root[i];
else rts[++t1][1]=root[i];
}
}
void Modify(int p,int val,int tag){
if(!p)return;
for(int i=p;i<=N;i+=lowbit(i))
CMT::Modify(1,top,root[i],val,tag);
}
int Getrank(int L,int R,int k){
t0=0;t1=0;
rts[++t0][0]=root[!(L-1)?0:(L+N-1)];
rts[++t1][1]=root[R+N];
Push(L-1,0);
Push(R,1);
return CMT::Qrank(1,top,k);
}
int Getnum(int L,int R,int k){
t0=0;t1=0;
rts[++t0][0]=root[!(L-1)?0:(L+N-1)];
rts[++t1][1]=root[R+N];
Push(L-1,0);
Push(R,1);
return CMT::Qnum(1,top,k);
}
int Getcnt(int L,int R,int val){
t0=0;t1=0;
rts[++t0][0]=root[!(L-1)?0:(L+N-1)];
rts[++t1][1]=root[R+N];
Push(L-1,0);
Push(R,1);
return CMT::Qcnt(1,top,val);
}
}
namespace solution{
void Prepare(){
N=read();M=read();
up(i,1,N){
a[i]=read();
num[++top]=a[i];
}
up(i,1,M){
qry[i].op=read();
if(qry[i].op!=3)qry[i].L=read(),qry[i].R=read(),qry[i].k=read();
else qry[i].p=read(),qry[i].k=read();
if(qry[i].op!=2)num[++top]=qry[i].k;
}
sort(num+1,num+top+1);
top=unique(num+1,num+top+1)-(num+1);
up(i,1,N)a[i]=lower_bound(num+1,num+top+1,a[i])-num;
up(i,1,M)if(qry[i].op!=2)qry[i].k=lower_bound(num+1,num+top+1,qry[i].k)-num;
up(i,N+1,(N<<1))CMT::Build(1,top,root[i],root[i-1],a[i-N]);
}
void Solve(){
int op,L,R,k,p;
up(i,1,M){
op=qry[i].op;
if(op==1){
L=qry[i].L;R=qry[i].R;k=qry[i].k;
printf("%d\n",BIT::Getrank(L,R,k));
}
if(op==2){
L=qry[i].L;R=qry[i].R;k=qry[i].k;
int p=BIT::Getnum(L,R,k);
printf("%d\n",num[p]);
}
if(op==3){
p=qry[i].p;k=qry[i].k;
BIT::Modify(p,a[p],-1);
BIT::Modify(p,k,1);
a[p]=k;
}
if(op==4||op==5){
L=qry[i].L;R=qry[i].R;k=qry[i].k;
int cnt=BIT::Getcnt(L,R,k),rnk=BIT::Getrank(L,R,k);
int p=BIT::Getnum(L,R,rnk+(op==4?-1:cnt));
printf("%d\n",num[p]);
}
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
Prepare();
Solve();
return 0;
}