题解 P5375 【[THUPC2019]组合数据结构问题】

· · 题解

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

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

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

先看时间复杂度 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