POJ 1442 Black Box(treap練習)
2914 ワード
タイトルリンク:http://poj.org/problem?id=1442
題意:1つの数列を与えて、2つの操作:(1)1つの数字を加えて、それを挿入して数列を下げないようにします;(2)i番目に大きい数字を尋ねる.
考え方:ノードは左側のノードの個数、右側のノードの個数と自身の個数(同じ数字があるため)を記録します.この問題は実際にSTLの優先キューで数行のコードしか書かないので、後ろに貼っておきました.
題意:1つの数列を与えて、2つの操作:(1)1つの数字を加えて、それを挿入して数列を下げないようにします;(2)i番目に大きい数字を尋ねる.
考え方:ノードは左側のノードの個数、右側のノードの個数と自身の個数(同じ数字があるため)を記録します.この問題は実際にSTLの優先キューで数行のコードしか書かないので、後ろに貼っておきました.
struct node
{
int L,R,key,pri,cntL,cntR,cnt;
};
class treap
{
public:
node p[N];
int size,root;
void init()
{
srand(time(0));
size=root=-1;
}
void rotL(int &x)
{
int y=p[x].R;
p[x].R=p[y].L;
p[x].cntR=p[y].cntL;
p[y].L=x;
p[y].cntL=p[x].cntL+p[x].cntR+p[x].cnt;
x=y;
}
void rotR(int &x)
{
int y=p[x].L;
p[x].L=p[y].R;
p[x].cntL=p[y].cntR;
p[y].R=x;
p[y].cntR=p[x].cntL+p[x].cntR+p[x].cnt;
x=y;
}
void insert(int &k,int key)
{
if(k==-1)
{
k=++size;
p[k].L=p[k].R=-1;
p[k].cnt=1;
p[k].cntL=p[k].cntR=0;
p[k].key=key;
p[k].pri=rand();
}
else if(key<p[k].key)
{
p[k].cntL++;
insert(p[k].L,key);
if(p[p[k].L].pri>p[k].pri) rotR(k);
}
else if(key==p[k].key)
{
p[k].cnt++;
}
else
{
p[k].cntR++;
insert(p[k].R,key);
if(p[p[k].R].pri>p[k].pri) rotL(k);
}
}
int find(int k,int cnt)
{
if(cnt<=p[k].cntL) return find(p[k].L,cnt);
cnt-=p[k].cntL;
if(cnt<=p[k].cnt) return p[k].key;
cnt-=p[k].cnt;
return find(p[k].R,cnt);
}
};
treap a;
int n,m,b[N];
int main()
{
Rush(n)
{
RD(m); a.init();
int i;
FOR1(i,n) RD(b[i]);
i=1;
int x,t=0;
while(m--)
{
RD(x); t++;
while(i<=x) a.insert(a.root,b[i++]);
PR(a.find(a.root,t));
}
}
return 0;
}
#include <stdio.h>
#include <queue>
using namespace std;
int a[30005],b[30005],n,m;
int main()
{
int i,j,k;
priority_queue<int> Qmin,Qmax;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<=m;i++) scanf("%d",&b[i]);
for(i=1;i<=m;i++)
{
for(j=b[i-1]+1;j<=b[i];j++)
{
Qmin.push(a[j]);
k=-Qmin.top();
Qmin.pop();
Qmax.push(k);
}
k=-Qmax.top();
Qmax.pop();
Qmin.push(k);
printf("%d
",Qmin.top());
}
return 0;
}