Dynamic Rankings ZOJ - 2112

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
using namespace std;

struct node1
{
    int tp;
    int l;
    int r;
    int k;
};

struct node2
{
    int l;
    int r;
    int val;
};

node1 order[10010];
node2 tree[2000010];
int ary[50010],pre[60010],root[50010],groot[50010],use[50010];
int n,q,len,num;

int lowbit(int x)
{
    return x&(-x);
}

int build(int l,int r)
{
    int cur,m;
    cur=num++;
    tree[cur].l=0,tree[cur].r=0,tree[cur].val=0;
    if(l==r) return cur;
    m=(l+r)/2;
    tree[cur].l=build(l,m);
    tree[cur].r=build(m+1,r);
    return cur;
}

int query(int pl,int pr,int lrot,int rrot,int k,int l,int r)
{
    int i,res,m;
    if(l==r) return l;
    res=tree[tree[rrot].l].val-tree[tree[lrot].l].val;
    for(i=pr;i>=1;i-=lowbit(i)) res+=tree[tree[use[i]].l].val;
    for(i=pl;i>=1;i-=lowbit(i)) res-=tree[tree[use[i]].l].val;
    m=(l+r)/2;
    if(res>=k)
    {
        for(i=pr;i>=1;i-=lowbit(i)) use[i]=tree[use[i]].l;
        for(i=pl;i>=1;i-=lowbit(i)) use[i]=tree[use[i]].l;
        return query(pl,pr,tree[lrot].l,tree[rrot].l,k,l,m);
    }
    else
    {
        for(i=pr;i>=1;i-=lowbit(i)) use[i]=tree[use[i]].r;
        for(i=pl;i>=1;i-=lowbit(i)) use[i]=tree[use[i]].r;
        return query(pl,pr,tree[lrot].r,tree[rrot].r,k-res,m+1,r);
    }
}

int updateI(int rot,int tar,int val,int l,int r)
{
    int cur,m;
    cur=num++;
    tree[cur]=tree[rot];
    tree[cur].val+=val;
    if(l==r) return cur;
    m=(l+r)/2;
    if(tar<=m) tree[cur].l=updateI(tree[rot].l,tar,val,l,m);
    else tree[cur].r=updateI(tree[rot].r,tar,val,m+1,r);
    return cur;
}

void updateII(int pos,int val)
{
    int i,p;
    p=lower_bound(pre+1,pre+len+1,ary[pos])-pre;
    for(i=pos;i<=n;i+=lowbit(i)) groot[i]=updateI(groot[i],p,-1,1,len);
    p=lower_bound(pre+1,pre+len+1,val)-pre;
    for(i=pos;i<=n;i+=lowbit(i)) groot[i]=updateI(groot[i],p,1,1,len);
    ary[pos]=val;
}

int main()
{
    int t,i,j,p;
    char op[10];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&ary[i]);
            pre[i]=ary[i];
        }
        len=n;
        for(i=1;i<=q;i++)
        {
            scanf("%s",op);
            if(op[0]=='Q')
            {
                order[i].tp=0;
                scanf("%d%d%d",&order[i].l,&order[i].r,&order[i].k);
            }
            else
            {
                order[i].tp=1;
                scanf("%d%d",&order[i].l,&order[i].r);
                len++;
                pre[len]=order[i].r;
            }
        }
        sort(pre+1,pre+len+1);
        len=unique(pre+1,pre+len+1)-pre-1;
        num=0;
        root[0]=build(1,len);
        for(i=1;i<=n;i++)
        {
            p=lower_bound(pre+1,pre+len+1,ary[i])-pre;
            root[i]=updateI(root[i-1],p,1,1,len);
        }
        for(i=1;i<=n;i++)
        {
            groot[i]=root[0];
        }
        for(i=1;i<=q;i++)
        {
            if(order[i].tp==0)
            {
                for(j=order[i].r;j>=1;j-=lowbit(j)) use[j]=groot[j];
                for(j=order[i].l-1;j>=1;j-=lowbit(j)) use[j]=groot[j];
                p=query(order[i].l-1,order[i].r,root[order[i].l-1],root[order[i].r],order[i].k,1,len);
                printf("%dn",pre[p]);
            }
            else
            {
                updateII(order[i].l,order[i].r);
            }
        }
    }
    return 0;
}