Dynamic Rankings 動態排名系統 (zju 2112)

解決這個和問題,需要用到“樹套樹”。建立一棵線段樹,維護N的節點的所有區間,每個線段樹節點上有一個平衡樹,用來維護當前區間內所有數的動態排名。很顯然,每個線段樹節點上的平衡樹,都是這個線段樹節點的兩個子節點的平衡樹的合併。由於我們無法實現高效的平衡樹合併,只好用這種以空間換時間的方法。

對於每個修改操作,只需先在線段樹找出單位區間[i,i]上平衡樹中的唯一節點,就是A[i]的原值,然後把線段樹從根到該節點路徑上所有節點的平衡樹中都刪除掉A[i]的原值,然後插入新值j。

查詢操作爲比較特殊,因爲給定的區間[i,j]可能對應線段樹中若干個區間的並,所以首先找出這對應的q區間的平衡樹T[1],T[2],T[3],...,T[q],找出其中的最大值Max和最小值Min,然後在[Min,Max]之間二分答案。對於給定的答案r,判斷是符合要求,否則按照單調性縮小二分區間。

如何求給定的r值的總排名,由於r可能不在某些甚至所有的q個平衡樹中,所以有時求r的排名是沒有意義的,換而我們可以求r在所有平衡樹中後繼的最小值MinSucc的排名。對於第i個平衡樹,要求r在T[i]中的後繼(不大於r的最小值)的排名S[i],MinSucc的排名就是k1=Σ{S[i]-1} + 1。但是相同的MinSucc的值可能會有多個,所以MinSucc的排名實際上是屬於一個區間的,應在所有的平衡樹中找出MinSucc一共的個數Count,MinSucc的最大排名就是k2=k1+Count-1。如果k屬於[k1,k2],那麼結果就是MinSucc。如果k2<k,則應向增大的方向二分答案,否則向減小的方向二分答案。

代碼很長,最後一句話,細節決定成敗!

感謝slxg,正如你所說的,我寫錯了。現在錯誤已經修正。看來zju的數據還是不夠強大,原來有點錯的也能AC。

/* 
 * Problem: Zju2112 dynrank
 * Author: Guo Jiabao
 * Time: 2009.2.9 14:14
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

struct treap_node
{
    treap_node *left,*right;
    int v,fix,size,weight;
    inline int lsize() {return left ?left ->size:0;}
    inline int rsize() {return right?right->size:0;}
};

struct sgt_node
{
    sgt_node *left,*right;
    int a,b;
    treap_node *treap;
};

const int MAXN=50001,MAXM=10001,INF=0x7FFFFFFF/2;
const int MAXTN=(MAXN+MAXM)*16,MAXSN=MAXN*2;
treap_node TS[MAXTN];
sgt_node SS[MAXSN];
int D,N,M,TC,SC,Tcnt;
sgt_node *sgt_root;
treap_node *T[MAXN];

inline treap_node* new_treap_node(int v)
{
    TS[++TC].v=v;
    TS[TC].left=TS[TC].right=0;
    TS[TC].size=TS[TC].weight=1;
    TS[TC].fix=rand();
    return &TS[TC];
}

inline void treap_rotate_right(treap_node *&p)
{
    treap_node *q=p->left;
    p->left=q->right;
    q->right=p;
    p=q;
    q=p->right;
    q->size=q->lsize() + q->rsize() +q->weight;
    p->size=p->lsize() + p->rsize() +p->weight;
}

inline void treap_rotate_left(treap_node *&p)
{
    treap_node *q=p->right;
    p->right=q->left;
    q->left=p;
    p=q;
    q=p->left;
    q->size=q->lsize() + q->rsize() +q->weight;
    p->size=p->lsize() + p->rsize() +p->weight;
}

int treap_find(treap_node *p,int v)
{
    if (!p)
        return 0;
    else if (v<p->v)
        return treap_find(p->left,v);
    else if (v>p->v)
        return treap_find(p->right,v);
    else
        return p->weight;
}

void treap_insert(treap_node *&p,int v)
{
    if (!p)
        p=new_treap_node(v);
    else
    {
        p->size++;
        if (v < p->v)
        {
            treap_insert(p->left,v);
            if (p->left->fix < p->fix)
                treap_rotate_right(p);
        }
        else if (v > p->v)
        {
            treap_insert(p->right,v);
            if (p->right->fix < p->fix)
                treap_rotate_left(p);
        }
        else
            p->weight++;
    }
}

void treap_delete(treap_node *&p) //real deletion
{
    if (p->left && p->right)
    {
        if (p->left->fix < p->right->fix)
        {
            treap_rotate_right(p);
            treap_delete(p->right);
        }
        else
        {
            treap_rotate_left(p);
            treap_delete(p->left);
        }
    }
    else
    {
        if (p->left)
            p=p->left;
        else
            p=p->right;
    }
}

void treap_delete(treap_node *&p,int v) //lazy deletion
{
    if (v==p->v)
    {
        p->weight--;
        p->size--;
        if (p->weight==0)
            treap_delete(p);
    }
    else
    {
        if (v < p->v)
            treap_delete(p->left,v);
        else
            treap_delete(p->right,v);
        p->size--;
    }
}

void treap_succ(treap_node *p,int v,int &rs)
{
    if (!p) return;
    if (p->v >= v)
    {
        rs=p->v;
        treap_succ(p->left,v,rs);
    }
    else
        treap_succ(p->right,v,rs);
}

int treap_getmin(treap_node *p)
{
    while (p->left)
        p=p->left;
    return p->v;
}

int treap_getmax(treap_node *p)
{
    while (p->right)
        p=p->right;
    return p->v;
}

void treap_rank(treap_node *p,int v,int cur,int &rank)
{
    if (v == p->v)
        rank=p->lsize() + cur + 1;
    else if (v < p->v)
        treap_rank(p->left,v,cur,rank);
    else
        treap_rank(p->right,v,p->lsize() + cur + p->weight,rank);
}

inline sgt_node* new_sgt_node()
{
    SS[++SC].treap=0;
    SS[SC].a=SS[SC].b=0;
    SS[SC].left=SS[SC].right=0;
    return &SS[SC];
}

void sgt_build(sgt_node *&p,int a,int b)
{
    p=new_sgt_node();
    if (a==b)
        p->a=p->b=a;
    else
    {
        int m=(a+b) >> 1;
        sgt_build(p->left,a,m);
        sgt_build(p->right,m+1,b);
        p->a=a;p->b=b;
    }
}

int sgt_edit(sgt_node *p,int k,int v,bool del)
{
    int delter=0;
    if (p->a==p->b)
    {
        if (del)
            delter=p->treap->v;
    }
    else
    {
        int m=(p->a+p->b) >> 1;
        if (k>=p->a && k<=m)
            delter=sgt_edit(p->left,k,v,del);
        else
            delter=sgt_edit(p->right,k,v,del);
    }
    if (del)
        treap_delete(p->treap,delter);
    treap_insert(p->treap,v);
    return delter;
}

void sgt_get(sgt_node *p,int a,int b)
{
    if (p->a==a && p->b==b)
        T[++Tcnt]=p->treap;
    else
    {
        int m=(p->a+p->b) >> 1;
        if (b<=m)
            sgt_get(p->left,a,b);
        else if (a>=m+1)
            sgt_get(p->right,a,b);
        else
        {
            sgt_get(p->left,a,m);
            sgt_get(p->right,m+1,b);
        }
    }
}

void init()
{
    int i,v;
    TC=SC=-1;
    sgt_root=0;
    scanf("%d%d",&N,&M);
    sgt_build(sgt_root,1,N);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&v);
        sgt_edit(sgt_root,i,v,false); //non-deletion
    }
}

int check(int result,int k)
{
    int totalrankL,totalrankR,minsucc=INF;
    int i,rank,succ,totalrank=0,totalcount=0;
    for (i=1;i<=Tcnt;i++)
    {
        succ=INF;
        treap_succ(T[i],result,succ);
        if (succ==INF)
            rank=T[i]->size+1;
        else
            treap_rank(T[i],succ,0,rank);
        totalrank+=rank-1;
        if (succ < minsucc)
            minsucc=succ;
    }
    for (i=1;i<=Tcnt;i++)
        totalcount+=treap_find(T[i],minsucc);
    totalrankL=++totalrank;
    totalrankR=totalrank+totalcount-1;
    if (k>=totalrankL && k<=totalrankR)
    {
        printf("%dn",minsucc);
        return 0;
    }
    else if (totalrankL > k)
        return 1;
    else
        return -1;
}

void binary(int a,int b,int k)
{
    int Min=INF,Max=0,i,m,r;
    Tcnt=0;
    sgt_get(sgt_root,a,b);
    for (i=1;i<=Tcnt;i++)
    {
        m=treap_getmax(T[i]);
        if (m>Max)
            Max=m;
        m=treap_getmin(T[i]);
        if (m<Min)
            Min=m;
    }
    m=(Max+Min)>>1;
    do
    {
        r=check(m,k); //-1=smaller 1=bigger
        if (r<0)
        {
            Min=m;
            m=(m+Max+1)>>1;
        }
        else if (r>0)
        {
            Max=m;
            m=(Min+m)>>1;
        }
    }while (r!=0);
}

void request()
{
    int i,a,b,c,j=0;
    for (i=1;i<=M;i++)
    {
        do c=getchar(); while (c==10 ||c==13);
        if (c=='C')
        {
            scanf("%d%d",&a,&b);
            sgt_edit(sgt_root,a,b,true);
        }
        else
        {
            scanf("%d%d%d",&a,&b,&c);
            binary(a,b,c);
        }
    }
}

int main()
{
    freopen("dynrank.in","r",stdin);
    freopen("dynrank.out","w",stdout);
    scanf("%d",&D);
    for (int i=1;i<=D;i++)
    {
        init();
        request();
    }
    return 0;
}

我的轉述 動態排名系統

[問題描述]
給定一個長度爲N的已知序列A[i](1&lt;=i&lt;=N),要求維護這個序列,能夠支持以下兩種操作:
1、查詢A[i],A[i+1],A[i+2],...,A[j](1&lt;=i&lt;=j&lt;=N)中,升序排列後排名第k的數。
2、修改A[i]的值爲j。

所謂排名第k,指一些數按照升序排列後,第k位的數。例如序列{6,1,9,6,6},排名第3的數是6,排名第5的數是9。

[輸入格式]
第一行包含一個整數D(0&lt;=D&lt;=4),表示測試數據的數目。接下來有D組測試數據,每組測試數據中,首先是兩個整數N(1&lt;=N&lt;=50000),M(1&lt;=M&lt;=10000),表示序列的長度爲N,有M個操作。接下來的N個不大於1,000,000,000正整數,第i個表示序列A[i]的初始值。然後的M行,每行爲一個操作
Q i j k 或者
C i j
分別表示查詢A[i],A[i+1],A[i+2],...,A[j](1&lt;=i&lt;=j&lt;=N)中,升序排列後排名第k的數,和修改A[i]的值爲j。

[輸出格式]
對於每個查詢,輸出一行整數,爲查詢的結果。測試數據之間不應有空行。

[樣例輸入]
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

[樣例輸出]
3
6
3
6

題目原貌

Dynamic Rankings

Time limit: 10 Seconds Memory limit: 65536K

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like : what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.

Your task is to write a program for this computer, which

- Reads N numbers from the input (1<=N<=50,000)

- Processes M instructions of the input (1<=M<=10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.

Input

The first line of the input is a single number X (0<X<=4), the number of the test cases of the input. Then X blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format

<p align="left"><span><span><span>Q i j k           or
C i t</span></span></span>
<p align="left"><span><span><span>It represents to query the k-th number of a[i], a[i+1],..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.</span></span></span></p>
<p align="left"><span><span>There're NO breakline between two continuous test cases.</span></span></p>
<p align="left"><span><span><strong>Output</strong></span></span></p>
<p align="left"><span><span>For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])</span></span></p>
<p align="left"><span><span><strong>There're NO breakline between two continuous test cases.</strong></span></span></p>
<p align="left"><span><span><strong>Sample Input</strong></span></span></p>

<p align="left"><span><span><span>2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3</span></span></span>
<p align="left"><span><span><strong>Sample Output</strong></span></span></p>

<p align="left"><span><span><span>3
6
3
6</span></span></span>
<p align="left"><span><span><span><strong>Author:</strong></span></span><span><span> XIN, Tao (chief editor), ZHU, Zeyuan (subeditor), PAN, Zhenhao (adviser)</span></span></span></p>
<p align="left"><span><span><span><strong>Site: </strong></span></span><span><span>http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm</span></span></span></p>

相關日誌