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

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 = 0;
////////////////treap
struct Treap
{
    int root[maxn],sz,s[maxn],ls[maxn],rs[maxn],v[maxn],w[maxn],rnd[maxn];
    void init()
    {
        memset(root,0,sizeof(root));
        sz=0;
    }
    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]=1;ls[k]=rs[k]=0;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]>1){
                w[k]--;
                s[k]--;
                return;
            }
            if(ls[k]*rs[k]==0)
                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)/2;
    if(x<=mid)Seg_insert(k*2,l,mid,x,num);
    else Seg_insert(k*2+1,mid+1,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)/2;
    if(x<=mid)Seg_change(k*2,l,mid,x,Now,Pre);
    else Seg_change(k*2+1,mid+1,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)/2;
    if(mid>=R)
        Seg_query(k*2,l,mid,L,R,num);
    else if(mid<L)
        Seg_query(k*2+1,mid+1,r,L,R,num);
    else{
        Seg_query(k*2,l,mid,L,mid,num);
        Seg_query(k*2+1,mid+1,r,mid+1,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=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            Seg_insert(1,1,n,i,a[i]);
        }
        char op[10];
        for(int i=1;i<=m;i++)
        {
            scanf("%s",op);
            if(op[0]=='C')
            {
                int x,y;scanf("%d%d",&x,&y);
                Seg_change(1,1,n,x,y,a[x]);
                a[x]=y;
            }
            else
            {
                int x,y,z;scanf("%d%d%d",&x,&y,&z);
                int l = 0,r = 1e9;
                while(l<=r)
                {
                    int mid = (l+r)/2;
                    tmp = 0;Seg_query(1,1,n,x,y,mid);
                    if(tmp>=z)r=mid-1;
                    else l=mid+1;
                }
                printf("%d
",l);
            }
        }
    }
}