Morris' Blog

2011-04-07 13:56:04Morris

d788. 排名順序

留言 0 收藏 0 推薦 0

內容：

考試成績出爐了 , 大家開始討論自己的分數高低

一個接著一個參與討論 , 新加入的那個人 , 想要知道自己目前排名是多少

但是太多人了 , 導致沒辦法一時得到他的排名

大家開始請求小光這個答案 ,

不過小光非常討厭排名 , 一點都不想幫忙

現在就交給你了

輸入說明：

每組輸入的第一行有一個數字 N ( 1 ≦ N ≦ 10,0000 )

代表接下來會有 N 個人陸續與討論，接下來會有 N 行，

代表接下來陸續加入的人的成績 M ， ( 1 ≦ M ≦ N )

而且每個人的成績都不會重複

輸出說明：

對於已經知道的成績，請陸續對每個加入的輸出他的排名

範例輸入：

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

範例輸出：

1
1
1
3
3
5

這題有3種作法，ST，BIT，AVL
只要符合加減法則，就可以使用BIT
/**********************************************************************************/
/*  Problem: d788 "排名順序" from ST | BIT | AVL                              */
/*  Language: C                                                                   */
/*  Result: AC (256ms, 586KB) on ZeroJudge                                        */
/*  Author: morris1028 at 2011-04-07 13:45:04                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
int C[131073];/*2^17=131072*/ 
int Lowbit(int N) {
    return N&(-N);
}
int Modify (int N, int L) {
    while(N<=L) {
        C[N]+=1;
        N+=Lowbit(N); 
    } 
}
int Operator (int N) {
    int Sum=0;
    while(N) {
        Sum+=C[N];
        N-=Lowbit(N); 
    } 
    return Sum; 
}
int Input() {   
    char cha;   
    int x=0;
    while(cha=getchar())
        if(cha!=' ' && cha!='\n') break;   
    x=cha-48;   
    while(cha=getchar()) {
        if(cha==' ' || cha=='\n') break;   
        x=x*10+cha-48;   
    }
    return x;   
}
main() {
    int N, M, a, B2[20]={1}, L;
    for(a=1;a<20;a++)
        B2[a]=B2[a-1]*2; 
    while(scanf("%d",&N)==1) {
            for(a=0;a<20;a++)
                if(B2[a]>=N) break;
            L=B2[a];
            for(a=1;a<=L;a++)   C[a]=0; 
            
            for(a=1;a<=N;a++) { 
                M=Input(); 
                Modify (M, L);
                printf("%d\n",a-Operator(M-1)); 
            } 
    } 
    return 0;
}
/**********************************************************************************/
/*  Problem: d788 "排名順序" from ST | BIT | AVL                              */
/*  Language: C                                                                   */
/*  Result: AC (342ms, 1156KB) on ZeroJudge                                       */
/*  Author: morris1028 at 2011-04-07 13:48:25                                     */
/**********************************************************************************/


#include<stdlib.h>
#include<stdio.h>
int A[100001], C[262145];
int  Get(int l, int h, int k, int x, int y) {
	if(l==x && h==y)  return C[k];
	else{
    	int m=(l+h)/2; 
        if(m >= y) return Get(l, m, 2*k, x, y);
        else if(m < x) return Get(m+1, h, 2*k+1, x, y); 
        else return Get(l, m, 2*k, x, m)+Get(m+1, h, 2*k+1, m+1, y);
    } 
} 
void No(int l, int h, int k) {
	if(l==h)    A[l]=k, C[k]=0;
    else{
        int m=(l+h)/2;
        No(l,  m,2*k);
        No(m+1,h,2*k+1);
        C[k]=0;
    } 
}
int Input() {   
    char cha;   
    int x=0;
    while(cha=getchar())
        if(cha!=' '&&cha!='\n') break;   
    x=cha-48;   
    while(cha=getchar()) {
        if(cha==' '||cha=='\n') break;   
        x=x*10+cha-48;   
    }
    return x;   
}
main() {
    int N, M, a, Index;
    while(scanf("%d",&N)==1) {
        No(1 , N, 1);
        for(a=1;a<=N;a++) {
            M=Input(), Index = A[M];
            while(Index)
                {C[Index]++,Index/=2;}
            printf("%d\n", Get(1,N,1,M,N));
        }
    }
    return 0;
}
/**********************************************************************************/
/*  Problem: d788 "排名順序" from ST | BIT | AVL                              */
/*  Language: C                                                                   */
/*  Result: AC (682ms, 2230KB) on ZeroJudge                                       */
/*  Author: morris1028 at 2011-04-07 13:53:02                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
struct BST { 
    int r, l, V, bf, child; 
} BST[100001]; 
int Top=100000, Head, Rank;
int Max(int x, int y) {
    if(x>y) return x;
    return y;
}
int Height(int x) {
	if(x==0)    return -1;
    else    return BST[x].bf;
}
int LL(int Now) {
    int l;
    l = BST[Now].l;
    BST[Now].l = BST[l].r;
    BST[l].r = Now;
    BST[l].bf = Max(Height(BST[l].l), Height(BST[l].r))+1;
    BST[l].child = (BST[BST[l].l].child+BST[BST[l].r].child)+1;
    BST[Now].bf = Max(Height(BST[Now].l), Height(BST[Now].r))+1;
    BST[Now].child = (BST[BST[Now].l].child+BST[BST[Now].r].child)+1;
    return l;
}
int RR(int Now) {
    int r;
    r = BST[Now].r;
    BST[Now].r = BST[r].l;
    BST[r].l = Now;
    BST[r].bf = Max(Height(BST[r].l), Height(BST[r].r))+1;
    BST[r].child = (BST[BST[r].l].child+BST[BST[r].r].child)+1;
    BST[Now].bf = Max(Height(BST[Now].l), Height(BST[Now].r))+1;
    BST[Now].child = (BST[BST[Now].l].child+BST[BST[Now].r].child)+1;
    return r;
}
int LR(int Now) {
    BST[Now].l= RR(BST[Now].l);
    return LL(Now);
}
int RL(int Now) {
    BST[Now].r= LL(BST[Now].r);
    return RR(Now);
}
int Set(int Now, int Value) {
	
	if(Value < BST[Now].V) {                    
        Rank+=BST[BST[Now].r].child+1;
        if(BST[Now].l){
            BST[Now].l = Set(BST[Now].l, Value);
            if(Height(BST[Now].l)-Height(BST[Now].r) ==2) {
                if(Value <  BST[BST[Now].l].V) 
                    Now= LL(Now);/*LL旋轉*/
                else    Now= LR(Now);/*LR旋轉*/
            } 
        }
        else    BST[Now].l=++Top, BST[Top].V=Value, BST[Top].bf=0, BST[Top].child=1; 
    }       
    
    else if(Value > BST[Now].V) {
        if(BST[Now].r) {
            BST[Now].r = Set(BST[Now].r, Value);
            if(Height(BST[Now].r)-Height(BST[Now].l) ==2) {
                if(Value >  BST[BST[Now].r].V) 
                    Now= RR(Now);/*RR旋轉*/
                else    Now= RL(Now);/*RL旋轉*/
            }
        }
        else    BST[Now].r=++Top, BST[Top].V=Value, BST[Top].bf=0, BST[Top].child=1;
    }
    
    BST[Now].bf = Max(Height(BST[Now].l), Height(BST[Now].r))+1;
    BST[Now].child = (BST[BST[Now].l].child+BST[BST[Now].r].child)+1; 
    return Now;
}
int Input() {   
    char cha;   
    int x=0;
    while(cha=getchar())
        if(cha!=' '&&cha!='\n') break;   
    x=cha-48;   
    while(cha=getchar()) {
        if(cha==' '||cha=='\n') break;   
        x=x*10+cha-48;   
    }
    return x;   
}
main() {
    int N, M, a, b;
    while(scanf("%d",&N)==1) {
        for(a=0;a<=Top;a++) 
            BST[a].r=0, BST[a].l=0, BST[a].V=0, BST[a].bf=0, BST[a].child=0;
        Head = 1, Top = 1;
        scanf("%d",&M), BST[1].V=M;
        puts("1"); 
        for(a=2;a<=N;a++) {
            M=Input(), Rank=1;
            Head = Set(Head, M);
            printf("%d\n",Rank); 
        } 
    } 
    return 0; 
}