| 记录编号 |
575061 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[TYVJ1730]二逼平衡树 |
最终得分 |
100 |
| 用户昵称 |
 瑆の時間~無盡輪迴·林蔭 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
3.477 s |
| 提交时间 |
2022-09-02 11:54:55 |
内存使用 |
124.18 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
const int N=50001,LOG=20;
struct PE
{
int val,size,cnt,ch[2],ff;
PE()
{
val=0;
size=0;
cnt=0;
ch[0]=0;
ch[1]=0;
ff=0;
};
};
PE t[N*LOG*5];
int RT[N*LOG],tot=0,VAL[N],n,m;
int ls(int x)
{
return t[x].ch[0];
}
int rs(int x)
{
return t[x].ch[1];
}
void pushup(int x)
{
t[x].size=t[x].cnt+t[ls(x)].size+t[rs(x)].size;
}
void rotate(int x)
{
int y=t[x].ff;
int z=t[y].ff;
int k=(t[y].ch[1]==x);
t[z].ch[t[z].ch[1]==y]=x;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].ff=y;
t[x].ch[k^1]=y;
t[y].ff=x;
t[x].ff=z;
pushup(y);
pushup(x);
}
void Splay(int x,int goal,int IDX)
{
while(t[x].ff!=goal)
{
int y=t[x].ff;
int z=t[y].ff;
if(z!=goal)
{
(t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);
}
rotate(x);
}
if(goal==0)
{
RT[IDX]=x;
}
}
void Insert(int x,int IDX)
{
int u=RT[IDX],ff=0;
if(!u)
{
u=++tot;
t[u].ch[0]=0;
t[u].ch[1]=0;
t[u].val=x;
t[u].cnt=1;
t[u].size=1;
RT[IDX]=u;
return;
}
while(u&&t[u].val!=x)
{
ff=u;
u=t[u].ch[t[u].val<x];
}
if(t[u].val==x&&u)
{
t[u].cnt++;
}
else
{
u=++tot;
t[u].val=x;
t[u].ch[0]=0;
t[u].ch[1]=0;
t[u].cnt=1;
t[u].size=1;
t[u].ff=ff;
if(ff)
{
t[ff].ch[t[ff].val<x]=u;
}
}
Splay(u,0,IDX);
}
void Find(int x,int IDX)
{
int u=RT[IDX];
while(t[u].ch[t[u].val<x]&&t[u].val!=x)
{
u=t[u].ch[t[u].val<x];
}
Splay(u,0,IDX);
}
int Next(int x,int F,int IDX)
{
Find(x,IDX);
int u=RT[IDX];
if(t[u].val<x&&!F)
return u;
if(t[u].val>x&&F)
{
return u;
}
u=t[u].ch[F];
while(t[u].ch[F^1])
u=t[u].ch[F^1];
return u;
}
void Delete(int x,int IDX)
{
int u=RT[IDX];
int pre=Next(x,0,IDX);
int nxt=Next(x,1,IDX);
Splay(pre,0,IDX);
Splay(nxt,pre,IDX);
int del=t[nxt].ch[0];
if(t[del].cnt>1)
{
t[del].cnt--;
Splay(del,0,IDX);
}
else
{
t[nxt].ch[0]=0;
return;
}
}
void Build(int x,int l,int r)
{
Insert(998244353,x);
Insert(-998244353,x);
if(l==r)
{
return;
}
int mid=(l+r)>>1;
Build(x<<1,l,mid);
Build(x<<1|1,mid+1,r);
}
void Fir_Insert(int x,int l,int r,int k,int s)
{
Insert(s,x);
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(k<=mid)
Fir_Insert(x<<1,l,mid,k,s);
else
Fir_Insert(x<<1|1,mid+1,r,k,s);
}
void Fir_Delete(int x,int l,int r,int k,int s)
{
Delete(s,x);
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(k<=mid)
Fir_Delete(x<<1,l,mid,k,s);
else
Fir_Delete(x<<1|1,mid+1,r,k,s);
}
void CHANGE(int pos,int s)
{
Fir_Delete(1,1,n,pos,VAL[pos]);
VAL[pos]=s;
Fir_Insert(1,1,n,pos,VAL[pos]);
}
int Fir_Rank(int x,int l,int r,int nl,int nr,int k)
{
//RANK算出的并不是该数排名，而是比这个数字小的数的个数
if(nl<=l&&nr>=r)
{
Find(k,x);
int u=RT[x];
if(t[u].val>=k)
{
return t[ls(u)].size-1;//开始插入了冗余量
}
else
{
return t[ls(u)].size+t[u].cnt-1;
}
}
int mid=(l+r)>>1,ans=0;
if(nl<=mid)
{
ans+=Fir_Rank(x<<1,l,mid,nl,nr,k);
}
if(nr>mid)
ans+=Fir_Rank(x<<1|1,mid+1,r,nl,nr,k);
return ans;
}
int Fir_Front(int x,int l,int r,int nl,int nr,int k)
{
if(nl<=l&&nr>=r)
{
return t[Next(k,0,x)].val;
}
int mid=(l+r)>>1,res=-998244353;
if(nl<=mid)
res=max(res,Fir_Front(x<<1,l,mid,nl,nr,k));
if(nr>mid)
res=max(res,Fir_Front(x<<1|1,mid+1,r,nl,nr,k));
return res;
}
int Fir_Back(int x,int l,int r,int nl,int nr,int k)
{
if(nl<=l&&nr>=r)
{
return t[Next(k,1,x)].val;
}
int mid=(l+r)>>1,res=998244353;
if(nl<=mid)
res=min(res,Fir_Back(x<<1,l,mid,nl,nr,k));
if(nr>mid)
res=min(res,Fir_Back(x<<1|1,mid+1,r,nl,nr,k));
return res;
}
int Fir_KTH(int nl,int nr,int k)
{
int L=0,R=100000000,mid,Check,ans;
while(L<=R)
{
mid=(L+R)>>1;
Check=Fir_Rank(1,1,n,nl,nr,mid)+1;
//Check实际上才是mid的排名
if(Check>k)
{
R=mid-1;
}
else
{
ans=mid;
L=mid+1;
}
}
return ans;
}
int main()
{
freopen("psh.in","r",stdin);
freopen("psh.out","w",stdout);
scanf("%d%d",&n,&m);
int a1,a2,a3,a4;
Build(1,1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&VAL[i]);
Fir_Insert(1,1,n,i,VAL[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a1,&a2,&a3);
if(a1==1)
{
scanf("%d",&a4);
printf("%d\n",Fir_Rank(1,1,n,a2,a3,a4)+1);
}
if(a1==2)
{
scanf("%d",&a4);
printf("%d\n",Fir_KTH(a2,a3,a4));
}
if(a1==3)
{
CHANGE(a2,a3);
}
if(a1==4)
{
scanf("%d",&a4);
printf("%d\n",Fir_Front(1,1,n,a2,a3,a4));
}
if(a1==5)
{
scanf("%d",&a4);
printf("%d\n",Fir_Back(1,1,n,a2,a3,a4));
}
}
return 0;
}