Dynamic Rankings

Time Limit: 10 Sec Memory Limit: 128 MB

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，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。

Input

第一行有两个正整数
　　分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]。
　　接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。
　　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。

Output

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

Sample Input

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

Sample Output

3
　6

HINT

m,n≤10000 , 0≤ai≤1e9。

Main idea

询问区间中第k小的数是多少，需要支持单点修改点的权值。

Solution

我们看到这道题，发现对于一个询问应该是可以二分查找答案的，那么我们从整体二分的角度来思考。

我们发现，如果没有修改的话，显然很简单，直接整体二分将所有询问一起操作即可。

但是我们有操作，那应该怎么办呢？

我们对于每一次修改，记录一下原来的值，简单来说，就是对于每一次操作，记录一下若opt=1，则表示这个点在这个状态的值；若opt=3，则表示这是一个询问，

我们对于修改来说，新增一个opt=2，表示在修改之前的值。也就是说，我们在执行一个区间的操作时，如果发现一个opt=2，那么之前一定有一个一样的值的opt为1，并且其已经对答案造成影响，现在那个元素已经被修改了，就要相应地减去它之前对答案的影响，这样就完成了修改。

然后我们整体二分权值，像静态查询kth那样修改一下即可。思路一气呵成 (≧▽≦)/

Code

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
147
148
149
150
151
152
#include<bits/stdc++.h>
using namespace std;

const int ONE=30005;
const int INF=1e9+1;

int n,m;
int x,y,k;
char ch[3];
int cnt,Num;
int a[ONE],record[ONE];
int Ans[ONE];

struct power
{
    int opt,cnt;
    int l,r,k;
    int pos,value;
    int cur;
}oper[ONE],qL[ONE],qR[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

namespace Bit
{
    struct power
    {
        int value;
    }Node[ONE];

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

    void Update(int R,int x)
    {
        for(int i=R;i<=n;i+=lowbit(i))
            Node[i].value+=x;
    }

    int Query(int R)
    {
        int res=0;
        for(int i=R;i>=1;i-=lowbit(i))
            res+=Node[i].value;
        return res;
    }
}

void Solve(int l,int r,int L,int R)
{
    if(l>r) return;
    if(L==R)
    {
        for(int i=l;i<=r;i++)
            if(oper[i].opt==3)
                Ans[oper[i].cnt] = L;
        return;
    }

    int M=(L+R)>>1;
    for(int i=l;i<=r;i++)
    {
        if(oper[i].opt==1 && oper[i].value<=M)
            Bit::Update(oper[i].pos,1);
        if(oper[i].opt==2 && oper[i].value<=M)
            Bit::Update(oper[i].pos,-1);
        if(oper[i].opt==3)
            record[i]=Bit::Query(oper[i].r) - Bit::Query(oper[i].l-1);
    }

    for(int i=l;i<=r;i++)
    {
        if(oper[i].opt==1 && oper[i].value<=M)
            Bit::Update(oper[i].pos,-1);
        if(oper[i].opt==2 && oper[i].value<=M)
            Bit::Update(oper[i].pos,1);
    }

    int l_num=0,r_num=0;
    for(int i=l;i<=r;i++)
    {
        if(oper[i].opt!=3)
        {
            if(oper[i].value <= M)
                qL[++l_num]=oper[i];
            else
                qR[++r_num]=oper[i];
        }
        else
        {
            if(oper[i].cur + record[i] >= oper[i].k)
                qL[++l_num]=oper[i];
            else
            {
                qR[++r_num]=oper[i];
                qR[r_num].cur+=record[i];
            }
        }
    }

    int t=l;
    for(int i=1;i<=l_num;i++) oper[t++]=qL[i];
    for(int i=1;i<=r_num;i++) oper[t++]=qR[i];


    Solve(l,l+l_num-1,L,M);
    Solve(l+l_num,r,M+1,R);
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=n;i++)
    {
        a[i]=get();
        oper[++cnt].opt=1;    oper[cnt].pos=i;    oper[cnt].value=a[i];
    }

    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch);
        if(ch[0]=='Q')
        {
            x=get();    y=get();    k=get();
            oper[++cnt].opt=3;    oper[cnt].l=x;    oper[cnt].r=y;    oper[cnt].k=k;
            oper[cnt].cnt=++Num;
        }
        else
        {
            x=get();    y=get();
            oper[++cnt].opt=2;    oper[cnt].pos=x;    oper[cnt].value=a[x];
            oper[++cnt].opt=1;    oper[cnt].pos=x;    oper[cnt].value=y;
            a[x]=y;
        }
    }

    Solve(1,cnt,0,INF);

    for(int i=1;i<=Num;i++)
        printf("%d\n",Ans[i]);
}