POJ 1442 밸 런 스 트 리 Treap

클릭 하여 링크 열기
제목: m 개 수 를 입력 하고 n 개 수 를 묻 습 니 다. 첫 번 째 수 는 3 이면 m 의 세 번 째 수 를 입력 한 후 1 번 째 로 큰 수 를 출력 하고 두 번 째 는 두 번 째 로 큰 수 를 출력 합 니 다. 그러나 전 제 는 U [i] 개 수 를 입력 한 후에 입 니 다.
사고방식: 균형 트 리 Treap 로 K 의 큰 수, 모형 문 제 를 삽입 하고 조회 합 니 다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=100010;
class Treap{
    public:
struct Treap_Node{
    Treap_Node *left,*right;
    int value,fix,weight,size;//fix    ,      ,              ,wweight   ,size     
}*root,*null;
Treap(){
    null=new struct Treap_Node;
    null->size=0;
    null->weight=0;
    null->value=inf;
    null->left=null;
    null->right=null;
    null->fix=inf;
    root=null;
}
void Treap_Print(Treap_Node *P){//      
    if(P!=null){
        Treap_Print(P->left);
        printf("%d
",P->value); Treap_Print(P->right); } } void Treap_Left_Rotate(Treap_Node *&a){// Treap_Node *b=a->right; a->right=b->left; b->left=a; b->size=a->size; a->size=a->left->size+a->right->size+a->weight; a=b; } void Treap_Right_Rotate(Treap_Node *&a){// Treap_Node *b=a->left; a->left=b->right; b->right=a; b->size=a->size; a->size=a->left->size+a->right->size+a->weight; a=b; } int Treap_Find(Treap_Node *P,int value){// value if(P==null) return 0; if(P->value==value) return 1; else if(value<P->value) return Treap_Find(P->left,value); else return Treap_Find(P->right,value); } void Treap_Insert(Treap_Node *&P,int value){// if(P==null){ P=new Treap_Node; P->left=P->right=null;// P->value=value; P->fix=rand(); P->weight=1; P->size=1; }else if(value==P->value){ P->weight++; } else if(value<P->value){ Treap_Insert(P->left,value); if(P->left->fix<P->fix) Treap_Right_Rotate(P); }else{ Treap_Insert(P->right,value); if(P->right->fix<P->fix) Treap_Left_Rotate(P); } P->size=P->left->size+P->right->size+P->weight; } void Treap_Delete(Treap_Node *&P,int value){// if(P==null) return ; if(value<P->value) Treap_Delete(P->left,value); else if(value>P->value) Treap_Delete(P->right,value); else if(P->weight>1) P->weight--; else if((P->left==NULL)&&(P->right==NULL)){ delete P; P=NULL; }else{ if(P->left->fix<P->right->fix) Treap_Left_Rotate(P); else Treap_Right_Rotate(P); Treap_Delete(P,value); } P->size=P->left->size+P->right->size+P->weight; } int Treap_pred(Treap_Node *P,int value,Treap_Node *optimal){// if(P==null||value==P->value) return optimal->value; if(P->value<value) return Treap_pred(P->right,value,P); else return Treap_pred(P->left,value,optimal); } int Treap_succ(Treap_Node *P,int value,Treap_Node *optimal){// if(P==null||value==P->value) return optimal->value; if(P->value>value) return Treap_succ(P->left,value,P); else return Treap_succ(P->right,value,optimal); } int Treap_Findkth(Treap_Node *P,int k){// K if(P==null) return 0; int t=P->left->size; if(k<t+1) return Treap_Findkth(P->left,k); else if(k>t+P->weight) return Treap_Findkth(P->right,k-(t+P->weight)); else return P->value; } int Treap_Rank(Treap_Node *P,int value,int cur){// int t=P->left->size; if(value==P->value) return t+cur+1; else if(value<P->value) return Treap_Rank(P->left,value,cur); else return Treap_Rank(P->right,value,t+cur+P->weight); } void Treap_erase(Treap_Node *&P) {// if(P->left!=null) Treap_erase(P->left); if(P->right!=null) Treap_erase(P->right); delete P; } }; int num[30010],num1[50010]; int main(){ int n,a,b,m; while(scanf("%d%d",&n,&m)!=-1){ Treap tree; for(int i=1;i<=n;i++) scanf("%d",&num[i]); int t=1,k=1; for(int i=1;i<=m;i++) scanf("%d",&num1[i]); while(t<=m){ while(k<=num1[t]){ tree.Treap_Insert(tree.root,num[k]); k++; } int ans=tree.Treap_Findkth(tree.root,t++); printf("%d
",ans); } } return 0; }

좋은 웹페이지 즐겨찾기