这道题其实之前也做过
https://blog.csdn.net/weixin_44226181/article/details/126685857
不过当时是用优先队列做的。这次用AVL 试试。
【题意】
黑盒子代表一个原始数据库,保存一个整数数组和一个特殊的i 变量。在最初的时刻,黑盒子是空的,i =0。黑盒子处理一系列命令(事务),有以下两种类型的事务。
示例:
写一个有效的算法来处理给定的事务序列。
ADD和GET事务的最大数量均为30000。使用两个整数数组来描述事务的顺序。
【输入输出】
(1)A(1),A(2),…,A(M):包含在黑盒子中的一系列元素。A值是绝对值不超过2 000 000 000的整数,M ≤30 000。对于示例,序列A =(3, 1, -4, 2, 8, -1000, 2)。
(2)u (1),u (2),…,u (N ):表示在第1个,第2个,…,第N个GET事务时包含在黑盒子中的元素个数。对于示例,u =(1, 2, 6, 6)。
假设自然数序列u (1),u (2),…,u (N)按非降序排序,N ≤M 且每个p (1≤p ≤N )对不等式p ≤u (p )≤M 都有效。由此得出这样的事实:对于u 序列的第p 个元素,执行GET事务,给出A(1),A(2),…,A(u (p ))序列第p 小的数。
输入:
输入包含M ,N ,A(1) ,A(2) ,…,A(M ) ,u (1) ,u (2) ,…,u (N )。
输出:
根据给定的事务顺序输出答案序列,每行一个数字。
【样例】
【新思路分析】
建立一棵平衡二叉树,查找第 k 小
【算法实现】
#include
#include
#include
using namespace std;
int m,n;
int num[200010],num1[200010];
typedef struct AVLNode{
int data;
int height,size,num;//高度,子树大小,结点重复个数
struct AVLNode *lchild;
struct AVLNode *rchild;
}*AVLTree;
int Height(AVLTree T){//计算高度,防止为空时无值
if(T==NULL) return 0;
return T->height;
}
int Size(AVLTree T){//计算大小,防止为空时无值
if(T==NULL) return 0;
return T->size;
}
void updateHeight(AVLTree &T){//更新高度
T->height=max(Height(T->lchild),Height(T->rchild))+1;
T->size=Size(T->lchild)+Size(T->rchild)+T->num;
}
AVLTree LL_Rotation(AVLTree &T){//LL旋转
AVLTree temp=T->lchild;
T->lchild=temp->rchild;
temp->rchild=T;
updateHeight(T);//更新高度
updateHeight(temp);
return temp;
}
AVLTree RR_Rotation(AVLTree &T){//RR旋转
AVLTree temp=T->rchild;
T->rchild=temp->lchild;
temp->lchild=T;
updateHeight(T);//更新高度
updateHeight(temp);
return temp;
}
AVLTree LR_Rotation(AVLTree &T){//LR旋转
T->lchild=RR_Rotation(T->lchild);
return LL_Rotation(T);
}
AVLTree RL_Rotation(AVLTree &T){//RL旋转
T->rchild=LL_Rotation(T->rchild);
return RR_Rotation(T);
}
AVLTree Insert(AVLTree &T,int x){
if(T==NULL){ //如果为空,创建新结点
T=new AVLNode;
T->lchild=T->rchild=NULL;
T->data=x;
T->num=1;
T->size=1;
T->height=1;
return T;
}
if(T->data==x){//查找成功
T->num++;//数量增1即可
T->size++;//坑点!!!!
return T;
}
if(x<T->data){//插入到左子树
T->lchild=Insert(T->lchild,x);//注意插入后返回结果挂接到T->lchild
if(Height(T->lchild)-Height(T->rchild)==2){//插入后如果不平衡插入高度大的那一边
if(x<T->lchild->data)//判断是LL还是LR
T=LL_Rotation(T);
else
T=LR_Rotation(T);
}
}
else{//插入到右子树
T->rchild=Insert(T->rchild,x);
if(Height(T->rchild)-Height(T->lchild)==2){
if(x>T->rchild->data)
T=RR_Rotation(T);
else
T=RL_Rotation(T);
}
}
updateHeight(T);
return T;
}
int Findkth(AVLTree T,int k){//找第k小
int t;
if(!T)
return 0;
if(T->lchild)
t=T->lchild->size;
else
t=0;
if(k<t+1)
return Findkth(T->lchild,k);
else if(k>t+T->num)
return Findkth(T->rchild,k-(t+T->num));
else return T->data;
}
int main(){
while(~scanf("%d%d",&n,&m)){
AVLTree root=NULL;//置空
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
for(int i=1;i<=m;i++)
scanf("%d",&num1[i]);
int t=1;
int k=1;
while(t<=m){
while(k<=num1[t]){
Insert(root,num[k++]);
}
int ans=Findkth(root,t++);
printf("%d\n",ans);
}
}
return 0;
}