自动搬运

查看原文

来自洛谷，原作者为

	天南星魔芋 我回来了，我就没走

搬运于2025-08-24 22:10:08，当前版本为作者最后更新于2020-10-26 09:39:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻由于被教练的贪心虐爆，故找了道数据结构题找自信。

先看题，题目要求我们模拟四种数据结构 队列、栈、大根堆和小根堆，

由于本蒟蒻不会同时用一种数据结构维护，所以我对以上结构进行了在线模拟。

先看时间复杂度 $0≤N≤10^5$ ，

队列是 $O(N)$ , 栈是 $O(N)$ , 堆是 $O(NlogN)$ ,

故总复杂度是 $O(2\times(N+NlogN))$ ，

也就是 三百六十万 ...够了。

另外 题上没说数据为空时不能取出，

所以我们要加特判；

接下来就上代码啦：

#include<bits/stdc++.h>
using namespace std;
int dd[60000],xd[60000],dl[60005],zan[50005];
//四种结构  dd 大根 堆  xd  小根 堆   dl  队列   zan 栈 

int dtop=0,xtop=0,l=1,r=0,top=0;
//指针   dtop 大根堆  xtop  小根堆   l r  队列   top 栈 

int n;
int pd;//存数---详见 
bool qwq[10];//判断数据结构是否符合 

//------------------------------------------------//堆放入 
void ddn(int x){                                 // 大根堆 
	if(x!=1){                                   //
		if(dd[x]>dd[x/2]){                     //
		swap(dd[x],dd[x/2]);                  //
		ddn(x/2);                            //
		}                                   //
	}                                      //
	return ;                              //
}                                        //
//--------------------------------------// 
void xdn(int x){                       // 小根堆 
	if(x!=1){                         //
		if(xd[x]<xd[x/2]){           //
		swap(xd[x],xd[x/2]);        //
		xdn(x/2);                  //
		}                         //
	}                            //
	return ;                    //
}                              //
//----------------------------//

//-------------------------------------------------------------//比大小 
int pdx(int x){                                               //小根堆 
	if(xd[x]<=xd[x*2]&&xd[x]<=xd[x*2+1])return 1;            //
	else return xd[x*2]<xd[x*2+1]? 2:3;                     //
}//--------------------------------------------------------//
int pdd(int x){                                           //大根堆 
	if(dd[x]>dd[x*2]&&dd[x]>dd[x*2+1])return 1;          //
	else return dd[x*2]>dd[x*2+1]? 2:3;                 //
}                                                      //
//----------------------------------------------------// 

//----------------------------------------------------------------------//取出 
void ddm(int x){                                                       //大根堆 
	if(x*2+1<=dtop){                                                  //
		pd=pdd(x);                                                   //
		if(pd==2){                                                  //
			swap(dd[x],dd[x*2]);ddm(x*2);                          //
		}else if(pd==3){                                          //
			swap(dd[x],dd[x*2+1]);ddm(x*2+1);                    //
		}                                                       //
	}                                                          //
	else if(x*2<=dtop){                                       //
		if(dd[x]<dd[x*2])                                    //
			swap(dd[x],dd[x*2]);                            //
	}                                                      //
	return ;                                              //
}                                                        //
//------------------------------------------------------// 
void xdm(int x){                                       //小根堆 
	if(x*2+1<=xtop){                                  //
		pd=pdx(x);                                   //
		if(pd==2){                                  //
			swap(xd[x],xd[x*2]);xdm(x*2);          //
		}else if(pd==3){                          //
			swap(xd[x],xd[x*2+1]);xdm(x*2+1);    //
		}                                       //
	}                                          //
	else if(x*2<=xtop){                       //
		if(xd[x]>xd[x*2])                    //
			swap(xd[x],xd[x*2]);            //
	}                                      //
	return ;                              //
}                                        //
//--------------------------------------// 

int main(){
	memset(qwq,1,sizeof(qwq));//初始化 
	scanf("%d",&n);
	int op,shu;
	for(int i=1;i<=n;i++){//在线算法--可省个数组 
		scanf("%d%d",&op,&shu);
		if(op==1){
			//加入 
			zan[++top]=shu;
			dl[++r]=shu;
			dd[++dtop]=shu;
			xd[++xtop]=shu;
			ddn(dtop);
			xdn(xtop);
		}
		else if(op==2){
			if(top>0){//特判---是否为空-----------------------// 
			if(shu!=dl[l])qwq[1]=0;//------------------------//不是 
			if(shu!=zan[top])qwq[2]=0;                      // 
			if(shu!=dd[1])qwq[3]=0;                        // 
			if(shu!=xd[1])qwq[4]=0;                       // 
			top--;                                       // 
			l++;                                        // 
			dd[1]=dd[dtop];                            // 
			xd[1]=xd[xtop];                           // 
			dtop--;                                  // 
			xtop--;                                 // 
			ddm(1);                                // 
			xdm(1);                               // 
			}                                    // 
			else {//----------------------------//是 
				for(int i=1;i<=4;i++){         // 
				qwq[i]=0;                     // 
				}                            // 
			}//-----------------------------// 
		}
		/*for(int i=1;i<=4;i++){//调试组，调试堆 
			cout<<qwq[i]<<"   ";
		}cout<<endl;
		for(int i=1;i<=xtop;i++){
			cout<<"   "<<xd[i]<<"  "<<dd[i]<<endl;
		}*/
	}
	
	for(int i=1;i<=4;i++){
		if(qwq[i]==1)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

好了，这篇题解就到这里了。

这是我的一篇题解，有不当之处请指出。

$update:$ 修补了$\LaTeX$