程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj 2112 Dynamic Rankings(主席樹&amp;動態第k大)

zoj 2112 Dynamic Rankings(主席樹&amp;動態第k大)

編輯：C++入門知識

Dynamic Rankings

Time Limit: 10 Seconds Memory Limit: 32768 KB

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
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

Q i j k or
C i t

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.

There're NO breakline between two continuous test cases.

Output

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])

There're NO breakline between two continuous test cases.

Sample Input

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

Sample Output

3
6
3
6

(adviser)
Site: http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm

Author: XIN, Tao

Source: Online Contest of Christopher's Adventure

題意：

給你一個長度為n(1 <= N <= 50,000)的序列。序列中每個值都不超過1e9.然後有m(1 <= M <= 10,000)次操作。

1.Q i j k 詢問i,j間第k大的值。

2.C i t 把序列的第i個值改成t。

思路：

明顯的主席樹。

網上關於主席樹的資料比較少。所以介紹下主席樹。一方面讓初學者少走彎路。另一方面方便自己溫習。避免過段時間自己的代碼都不認識了。。。

先講下主席樹相關的概念吧。

1.什麼是主席樹。

主席樹貌似是網上流傳的一種叫法。貌似學名叫函數式線段樹。相關概念可以自行百度。

2.主席樹有什麼用。

主席樹可以求解區間第k大問題。當然這個劃分樹也可以完成且時間和空間都比主席樹更優。那學主席樹還有什麼用。當然有用啦。劃分樹只能解決靜態第k大問題。也就是說。如果序列裡的值有更新的話劃分樹就不再適用了。這個時候就體現主席樹的優勢了。主席樹的其他應用還沒研究。等遇到了再補充。

3.主席樹到底是什麼。

其實所謂的主席樹就是一堆線段樹。一堆線段樹?一顆線段樹就耗那麼多內存了。一堆不會爆麼？這個就是主席樹的精華了。後面再解釋。

4.主席樹是怎麼實現查詢區間第k大問題的呢？

先從最基本的問題入手吧。如果區間是固定的就為[1,n]。然後詢問區間的第k大。很簡單吧。排個序就行了，但是我們要講的是線段樹的做法。考慮到序列的值可能很大。我們可以先對這n個值hash一下映射到1-n的范圍內。然後我們就把這n個值插入線段樹。線段樹的每個結點維護子樹中已經插入值的個數。那麼查找第k大就很簡單了。如果k>左子樹值的個數。那麼就在右子樹中找第（k-左子樹值個數）大值。否則在右子樹中找。遞歸進行直到到葉子結點。然後還原hash值就行了。

現在關鍵就是怎麼解決區間不是[1,n]的問題了。假如我們要查詢區間[l,r]的第k大值。如果我們有一顆線段樹R插入了裡面的值。當然就跟區間[1,n]的方法一樣了。假如我們建了n棵上面的線段樹。第i棵插入了[1,i]的值。感覺前綴的思想真的很巧妙。跟字符串的前綴有異曲同工之妙。第i棵線段樹的根為T[i]。那麼怎麼求[l,r]的第k大呢。其實和上面方法差不多。我們關鍵就是要知道線段樹R區間[l,r]內的值在左子樹的值有多少個。在右子樹有多少個。這個時候前綴的優勢就來了。(T[r]左子樹值的個數-T[l-1]左子樹值的個數)不就是R在左子樹值的個數麼。然後遞歸定位到葉子結點就行了。

但問題又來了。那麼多棵線段樹。就算內存不爆。建樹的時間也該爆了吧。精華部分來了。不得不歎服前人的智慧啊。由於這n棵線段樹結構形態一致。結點個數都一樣。這個很好理解吧。都是維護[1,n]值出現個數嘛。而更加爽的是。T[i+1]比T[i]多插一個值a[i+1].試想如果a[i+1]被插入了T[i+1]的左子樹。那麼T[i+1]的右子樹和T[i]的左子樹將完全相同。進入右子樹同理。那所以T[i+1]的右子樹完全不用建了。直接把T[i+1]右子樹指針指向T[i]右子樹就行了。共享結點。這是多麼機智。一下解決了一半的結點。這樣的做法遞歸進行。也就是T[i+1]只需建log2(n)的結點。這樣就可以解決靜態第k大了。

可以拿這個題開刀嘿嘿~

現在剩下的就是解決動態第k大問題了。這個地方我理解了很久。才明白。明白了其實很簡單。如果我們更新了arr[i]那麼它將會影響T[i]~T[n]。難道我們要一個一個改麼。這樣改顯然時間上不允許。但是你會發現它的改變對T[i]~T[n]的影響是一樣的。如果我們把影響（做子樹增加多少值。右子樹增加多少結點）記錄下來。那我們就只需用原始值減去變化值就好了。變化值我們可以用樹狀數組來記錄。我們把變化當作一個值，那麼就成了單點更新區間求和問題了。只是這裡不是一個值而是一個線段樹而已，但是我們可以類似的處理。

也就是每個樹狀數組的結點都是一棵線段樹。哈哈。真是刺激。那麼這個問題就圓滿解決了。分析下時空復雜度。首先建一棵空樹m*log2(m)。m為hash後值的個數。然後建n個樹.n*log2(m)。然後q次查詢操作.2*q*log2(m).所以總時間復雜度為。O((m+n+2*q)*log2(m))。空間復雜度。4*m+n*lon2(m)。

下面附上代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=60010;
const int maxm=2500010;
int ls[maxm],rs[maxm],c[maxm];//ls,rs左右兒子指針。c存值的個數
int arr[maxn],H[maxn],T[maxn];//arr存原序列.H存排序後值。T[i]第i棵線段樹的根
int s[maxn],ua[maxn],ub[maxn],*use;//s為樹狀數組結點。當然也是線段樹的根啦。
int n,m,tot;
struct node
{
    int l,r,k;
} qs[10010];//由於要先hash。
void init()//hash初始化
{
    sort(H,H+m);
    m=unique(H,H+m)-H;
}
int Hash(int x)
{
    return lower_bound(H,H+m,x)-H;
}
int build(int L,int R)//建空樹
{
    int rt=tot++,mid;
    c[rt]=0;
    if(L!=R)
    {
        mid=(L+R)>>1;
        ls[rt]=build(L,mid);
        rs[rt]=build(mid+1,R);
    }
    return rt;
}
int Insert(int prt,int x,int val)
{
    int nrt=tot++,tp=nrt,l=0,r=m-1,mid;
    c[nrt]=c[prt]+val;
    while(l>1;
        if(x<=mid)
        {
            ls[nrt]=tot++,rs[nrt]=rs[prt];//共享結點
            prt=ls[prt],nrt=ls[nrt];
            r=mid;
        }
        else
        {
            ls[nrt]=ls[prt],rs[nrt]=tot++;
            prt=rs[prt],nrt=rs[nrt];
            l=mid+1;
        }
        c[nrt]=c[prt]+val;
    }
    return tp;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int p,int d)//樹狀數組更新
{
    while(x<=n)
    {
        s[x]=Insert(s[x],p,d);
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ret=0;
    while(x)
    {
        ret+=c[ls[use[x]]];
        x-=lowbit(x);
    }
    return ret;
}
int qu(int L,int R,int k)
{
    int lrt=T[L-1],rrt=T[R],l=0,r=m-1,mid,tp,i,sa,sb;
    for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=s[i];
    sb=sum(L-1);
    for(i=R  ,use=ub;i;i-=lowbit(i)) use[i]=s[i];
    sa=sum(R);
    while(l>1;
        tp=sa-sb+c[ls[rrt]]-c[ls[lrt]];//初始值加改變值
        if(k<=tp)
        {
            r=mid;
            lrt=ls[lrt],rrt=ls[rrt];
            for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=ls[use[i]];//計算對應子樹改變
            sb=sum(L-1);
            for(i=R  ,use=ub;i;i-=lowbit(i)) use[i]=ls[use[i]];
            sa=sum(R);
        }
        else
        {
            l=mid+1;
            k-=tp;
            lrt=rs[lrt],rrt=rs[rrt];
            for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=rs[use[i]];
            sb=sum(L-1);
            for(i=R  ,use=ub;i;i-=lowbit(i)) use[i]=rs[use[i]];
            sa=sum(R);
        }
    }
    return l;
}
int main()
{
    int i,q,cas;
    char op[10];
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&q);
        tot=m=0;
        for(i=1;i<=n;i++)
            scanf("%d",&arr[i]),H[m++]=arr[i];
        for(i=0;i