Dynamic Rankings

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112

Description

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

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

HINT

题意

动态第k大

1. Q x y k,查询区间[x,y]第k大的数是啥

2. C x y，把第x个数变成y

题解：

树套树

在每一个区间里面，我们都套入一个Treap/Splay就好了

1操作很简单，暴力进行二分就好了，我们在[L,R]区间所在的Treap里面查询Rank

2操作，在所有这个数所在的区间，我们都删除原来的，再加入新的就好了

代码：

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<cstring>

#include<ctime>

using namespace std;

#define maxn 1000001

int tmp = ;

////////////////treap

struct Treap

{

    int root[maxn],sz,s[maxn],ls[maxn],rs[maxn],v[maxn],w[maxn],rnd[maxn];

    void init()

    {

        memset(root,,sizeof(root));

        sz=;

    }

    void Updata(int k)

    {

        s[k]=s[ls[k]]+s[rs[k]]+w[k];

    }

    void Rturn(int &k)

    {

        int t;

        t=ls[k],ls[k]=rs[t],rs[t]=k,s[t]=s[k];

        Updata(k);k=t;

    }

    void Lturn(int &k)

    {

        int t;

        t=rs[k],rs[k]=ls[t],ls[t]=k,s[t]=s[k];

        Updata(k);k=t;

    }

    void Insert(int &k,int num)

    {

        if(!k)

        {

            k=++sz;s[k]=w[k]=;ls[k]=rs[k]=;rnd[k]=rand();

            v[k]=num;return;

        }

        s[k]++;

        if(v[k]==num)w[k]++;

        else if(num<v[k])

        {

            Insert(ls[k],num);

            if(rnd[ls[k]]<rnd[k])

                Rturn(k);

        }

        else

        {

            Insert(rs[k],num);

            if(rnd[rs[k]]<rnd[k])

                Lturn(k);

        }

    }

    void Del(int &k,int num)

    {

        if(v[k]==num)

        {

            if(w[k]>){

                w[k]--;

                s[k]--;

                return;

            }

            if(ls[k]*rs[k]==)

                k=ls[k]+rs[k];

            else if(rnd[ls[k]]<rnd[rs[k]])

                Rturn(k),Del(k,num);

            else

                Lturn(k),Del(k,num);

        }

        else if(num<v[k]){

            Del(ls[k],num);

            s[k]--;

        }

        else{

            Del(rs[k],num);

            s[k]--;

        }

    }

    void Find(int k,int num)

    {

        if(!k)return;

        if(v[k]<=num){

            tmp+=s[ls[k]]+w[k];

            Find(rs[k],num);

        }

        else Find(ls[k],num);

    }

}Tr;

/////////////////////

/////////////////////线段树

void Seg_insert(int k,int l,int r,int x,int num)

{

    Tr.Insert(Tr.root[k],num);

    if(l==r)return;

    int mid=(l+r)/;

    if(x<=mid)Seg_insert(k*,l,mid,x,num);

    else Seg_insert(k*+,mid+,r,x,num);

}

void Seg_change(int k,int l,int r,int x,int Now,int Pre)

{

    Tr.Del(Tr.root[k],Pre);

    Tr.Insert(Tr.root[k],Now);

    if(l==r)return;

    int mid=(l+r)/;

    if(x<=mid)Seg_change(k*,l,mid,x,Now,Pre);

    else Seg_change(k*+,mid+,r,x,Now,Pre);

}

void Seg_query(int k,int l,int r,int L,int R,int num)

{

    if(l==L&&r==R)

    {

        Tr.Find(Tr.root[k],num);

        return;

    }

    int mid = (l+r)/;

    if(mid>=R)

        Seg_query(k*,l,mid,L,R,num);

    else if(mid<L)

        Seg_query(k*+,mid+,r,L,R,num);

    else{

        Seg_query(k*,l,mid,L,mid,num);

        Seg_query(k*+,mid+,r,mid+,R,num);

    }

}

///////////////////////////

int a[maxn];

int main()

{

    srand(time(NULL));

    int t;scanf("%d",&t);

    while(t--)

    {

        Tr.init();

        int n,m;scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

            Seg_insert(,,n,i,a[i]);

        }

        char op[];

        for(int i=;i<=m;i++)

        {

            scanf("%s",op);

            if(op[]=='C')

            {

                int x,y;scanf("%d%d",&x,&y);

                Seg_change(,,n,x,y,a[x]);

                a[x]=y;

            }

            else

            {

                int x,y,z;scanf("%d%d%d",&x,&y,&z);

                int l = ,r = 1e9;

                while(l<=r)

                {

                    int mid = (l+r)/;

                    tmp = ;Seg_query(,,n,x,y,mid);

                    if(tmp>=z)r=mid-;

                    else l=mid+;

                }

                printf("%d\n",l);

            }

        }

    }

}

巴特西

zoj 2112 Dynamic Rankings 动态第k大线段树套Treap

Dynamic Rankings

题目连接

Description

HINT

最新文章

热门文章

巴特西

zoj 2112 Dynamic Rankings 动态第k大 线段树套Treap

Dynamic Rankings

题目连接

Description

HINT

最新文章

热门文章

zoj 2112 Dynamic Rankings 动态第k大线段树套Treap