好吧当我什么都没说,push的那个地方应该是add[j]
by Scarlet_Lightning @ 2019-01-26 20:45:24
排序二叉树:
```cpp
#include <cstdio>
using namespace std;
int n,m,x,k,knum,root,num;
struct tree
{
int key,t,l,r,f;
bool IF;
}t[1000005];
int a[1000005];
void insert(int x,int y)
{
if(!t[x].IF)
{
t[x].key=y;t[x].t=1;t[x].IF=true;
knum++;t[x].l=knum;t[knum].f=x;
knum++;t[x].r=knum;t[knum].f=x;
return ;
}
t[x].t++;
if(y<t[x].key)insert(t[x].l,y);
else insert(t[x].r,y);
}
void find(int x,int y)
{
int a=0;
if(!t[x].IF)a=1;
else a=t[t[x].l].t+1;
if(y==a)printf("%d\n",t[x].key);
else if(y<a)find(t[x].l,y);
else find(t[x].r,y-a);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
k=1;knum=1;root=1;num=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
for(int j=k;j<=x;j++){insert(root,a[k]);k++;}
find(root,++num);
}
return 0;
}
```
by ⚡LZSY01_XZY⚡ @ 2019-01-26 20:53:23
堆:
```cpp
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int M=1000005;
int n,m,a[M],k;
int minq[M],minr;
int maxq[M],maxr;
void min_insert(int x)
{
int i,j,tmp;
minr++;minq[minr]=x;i=minr;
while((i>1)&&(minq[i]<minq[i>>1]))
{
j=i>>1;
tmp=minq[i];minq[i]=minq[j];minq[j]=tmp;
i=i>>1;
}
}
void min_delete(int n)
{
int lc,rc,min,tmp;
lc=n<<1;rc=(n<<1)+1;
min=n;
if((lc<=minr)&&(minq[lc]<minq[min]))min=lc;
if((rc<=minr)&&(minq[rc]<minq[min]))min=rc;
if(min!=n)
{
tmp=minq[min];minq[min]=minq[n];minq[n]=tmp;
min_delete(min);
}
}
int get_min()
{
int res,i;
if(minr==0)return 0;
res=minq[1];minq[1]=minq[minr];minr--;
if(minr>1)min_delete(1);
return res;
}
void max_insert(int x)
{
int i,j,tmp;
maxr++;maxq[maxr]=x;i=maxr;
while((i>1)&&(maxq[i]>maxq[i>>1]))
{
j=i>>1;
tmp=maxq[i];maxq[i]=maxq[j];maxq[j]=tmp;
i=i>>1;
}
}
void max_delete(int n)
{
int lc,rc,min,tmp;
lc=n<<1;rc=(n<<1)+1;
min=n;
if((lc<=maxr)&&(maxq[lc]>maxq[min]))min=lc;
if((rc<=maxr)&&(maxq[rc]>maxq[min]))min=rc;
if(min!=n)
{
tmp=maxq[min];maxq[min]=maxq[n];maxq[n]=tmp;
max_delete(min);
}
}
int get_max()
{
int res,i;
if(maxr==0)return 0;
res=maxq[1];maxq[1]=maxq[maxr];maxr--;
if(maxr>1)max_delete(1);
return res;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
int x,t1,t2;
k=1;minr=0;maxr=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
for(int j=k;j<=x;j++)
{
min_insert(a[k]);
if((maxr>0)&&(minq[1]<maxq[1]))
{
t1=get_min();
t2=get_max();
min_insert(t2);
max_insert(t1);
}
k++;
}
t1=get_min();
printf("%d\n",t1);
max_insert(t1);
}
return 0;
}
```
by ⚡LZSY01_XZY⚡ @ 2019-01-26 20:53:38
%%%
by Carrator @ 2019-01-26 20:58:00
```Orz```
by momentous @ 2019-05-28 07:37:33