BZOJ 1901 Dynamic Rankings 线段树套Treap

Description#

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。

Input#

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input#

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output#

3
6

题解#

区间k大+修改
直接树套树

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<algorithm>
5
using namespace std;
6
int a[10005],n;
7
class Treap{
8
    class Node{
9
    public:
10
        int size,v,key;
11
        Node *ch[2];
12
        Node(int x){
13
            key=rand();v=x;size=1;
14
            ch[0]=ch[1]=NULL;
15
        }
16
        #define size(_) ((_)?(_)->size:0)
17
        void Pushup(){
18
            size=size(ch[0])+size(ch[1])+1;
19
        }
20
    }*root;
21
    Node *Merge(Node *A,Node *B){
22
        if(!A)return B;
23
        if(!B)return A;
24
        if(A->key>B->key){
25
            A->ch[1]=Merge(A->ch[1],B);
26
            A->Pushup();
27
            return A;
28
        }
29
        else {
30
            B->ch[0]=Merge(A,B->ch[0]);
31
            B->Pushup();
32
            return B;
33
        }
34
    }
35
    typedef pair<Node*,Node*> DNode;
36
    DNode Split(Node *rt,int k){
37
        if(!rt)return DNode(NULL,NULL);
38
        DNode o;
39
        if(size(rt->ch[0])>=k){
40
            o=Split(rt->ch[0],k);
41
            rt->ch[0]=o.second;
42
            rt->Pushup();
43
            o.second=rt;
44
        }
45
        else{
46
            o=Split(rt->ch[1],k-size(rt->ch[0])-1);
47
            rt->ch[1]=o.first;
48
            rt->Pushup();
49
            o.first=rt;
50
        }
51
        return o;
52
    }
53
public:
54
    Treap(){
55
        root=NULL;
56
    }
57
    int kth(int k){
58
        DNode x=Split(root,k-1);
59
        DNode y=Split(x.second,1);
60
        Node *ans=y.first;
61
        root=Merge(x.first,Merge(y.first,y.second));
62
        return ans->v;
63
    }
64
    int rank(int x){
65
        return rank(root,x);
66
    }
67
    int rank(Node *rt,int x){
68
        if(!rt)return 0;
69
        return x<=rt->v?rank(rt->ch[0],x):rank(rt->ch[1],x)+size(rt->ch[0])+1;
70
    }
71
    void Insert(int x){
72
        int k=rank(root,x);
73
        DNode y=Split(root,k);
74
        Node *n=new Node(x);
75
        root=Merge(Merge(y.first,n),y.second);
76
    }
77
    void remove(int x){
78
        int k=rank(root,x);
79
        DNode a=Split(root,k);
80
        DNode b=Split(a.second,1);
81
        root=Merge(a.first,b.second);
82
    }
83
}root[40000];
84
#define lch l,m,rt<<1
85
#define rch m+1,r,rt<<1|1
86

87
void build(int l,int r,int rt){
88
    for(int i=l;i<=r;i++) root[rt].Insert(a[i]);
89
}
90
void buildtree(int l,int r,int rt){
91
    build(l,r,rt);
92
    if(l==r)return;
93
    int m=l+r>>1;
94
    buildtree(lch);
95
    buildtree(rch);
96
}
97
void updata(int k,int x,int y,int l,int r,int rt){
98
    root[rt].remove(y);
99
    root[rt].Insert(x);
100
    if(l==r)return;
101
    int m=l+r>>1;
102
    if(k<=m) updata(k,x,y,lch);
103
    else updata(k,x,y,rch);
104
}
105
int rank(int L,int R,int x,int l,int r,int rt){
106
    if(L<=l&&R>=r)return root[rt].rank(x);
107
    int m=l+r>>1;
108
    if(R<=m)return rank(L,R,x,lch);
109
    if(L>m) return rank(L,R,x,rch);
110
    return rank(L,R,x,lch)+rank(L,R,x,rch);
111
}
112
int kth(int L,int R,int k){
113
    int l=-1e10,r=1e10;
114
    while(l<=r){
115
        int m=l+r>>1;
116
        int num=rank(L,R,m,1,n,1)+1;
117
        if(num<=k)l=m+1;
118
        else r=m-1;
119
    }
120
    return r;
121
}
122
int main()
123
{
124
    int m;
125
    scanf("%d%d",&n,&m);
126
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
127
    buildtree(1,n,1);
128
    char s[5];int i,j,k,t;
129
    while(m--){
130
        scanf("%s",s);
131
        if(s[0]=='Q'){
132
            scanf("%d%d%d",&i,&j,&k);
133
            printf("%d\n",kth(i,j,k));
134
        }
135
        else{
136
            scanf("%d%d",&i,&t);
137
            updata(i,t,a[i],1,n,1);
138
            a[i]=t;
139
        }
140
    }
141
}