裸的带修改主席树.. 之前用BIT套Splay( http://www.cnblogs.com/JSZX11556/p/4625552.html )A过..但是还是线段树好写...而且快(常数比平衡树小). 时空复杂度是O(Nlog(N)+Mlog^2(N))
-------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
#define H(v) (lower_bound(Hash, Hash + Hn, v) - Hash + 1)
const int maxn = 10009;
int N, Q;
int seq[maxn];
int Hash[maxn << 1], Hn;
int Val, Pos;
inline int read() {
char c = getchar();
for(; !isdigit(c); c = getchar());
int ret = 0;
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
struct Event {
int l, r, v;
Event(int _l = 0, int _r = 0, int _v = 0) :
l(_l), r(_r), v(_v) {
}
} q[maxn];
void Init() {
Hn = 0;
N = read(), Q = read();
for(int i = 1; i <= N; i++)
Hash[Hn++] = (seq[i] = read());
for(int i = 0; i < Q; i++) {
char c = getchar();
for(; c != 'C' && c != 'Q'; c = getchar());
if(c == 'C') {
int p = read(), v = read();
q[i] = Event(-1, p, v);
Hash[Hn++] = v;
} else {
int l = read() - 1, r = read();
q[i] = Event(l, r, read());
}
}
sort(Hash, Hash + Hn);
Hn = unique(Hash, Hash + Hn) - Hash;
}
struct Node {
Node *lc, *rc;
int v;
} pool[5000000], *pt, *Null, *Root[maxn], *V[maxn];
void Init_sgt() {
pt = pool;
Null = pt++;
Null->v = 0;
Null->lc = Null->rc = Null;
}
Node* Modify(Node* t, int l, int r) {
Node* o = pt++;
o->v = t->v + Val;
if(l != r) {
int m = (l + r) >> 1;
if(Pos <= m) {
o->lc = Modify(t->lc, l, m);
o->rc = t->rc;
} else {
o->lc = t->lc;
o->rc = Modify(t->rc, m + 1, r);
}
}
return o;
}
void Build() {
Root[0] = Null;
Val = 1;
for(int i = 1; i <= N; i++) {
Pos = seq[i] = H(seq[i]);
Root[i] = Modify(Root[i - 1], 1, Hn);
}
}
Node *L[20], *R[20];
int Ln, Rn;
void Work() {
for(int i = 1; i <= Hn; i++)
V[i] = Null;
for(int i = 0; i < Q; i++)
if(~q[i].l) {
Ln = Rn = 0;
for(int p = q[i].l; p; p -= p & -p)
L[Ln++] = V[p];
for(int p = q[i].r; p; p -= p & -p)
R[Rn++] = V[p];
Node *_L = Root[q[i].l], *_R = Root[q[i].r];
int l = 1, r = Hn;
while(l < r) {
int cnt = _R->lc->v - _L->lc->v, m = (l + r) >> 1;
for(int j = 0; j < Ln; j++)
cnt -= L[j]->lc->v;
for(int j = 0; j < Rn; j++)
cnt += R[j]->lc->v;
if(cnt >= q[i].v) {
_L = _L->lc;
_R = _R->lc;
for(int j = 0; j < Ln; j++)
L[j] = L[j]->lc;
for(int j = 0; j < Rn; j++)
R[j] = R[j]->lc;
r = m;
} else {
q[i].v -= cnt;
_L = _L->rc;
_R = _R->rc;
for(int j = 0; j < Ln; j++)
L[j] = L[j]->rc;
for(int j = 0; j < Rn; j++)
R[j] = R[j]->rc;
l = m + 1;
}
}
printf("%d\n", Hash[l - 1]);
} else {
Pos = seq[q[i].r], Val = -1;
for(int p = q[i].r; p <= Hn; p += p & -p)
V[p] = Modify(V[p], 1, Hn);
Pos = seq[q[i].r] = H(q[i].v), Val = 1;
for(int p = q[i].r; p <= Hn; p += p & -p)
V[p] = Modify(V[p], 1, Hn);
}
}
int main() {
Init();
Init_sgt();
Build();
Work();
return 0;
}
------------------------------------------------------------------------
1901: Zju2112 Dynamic Rankings
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 5988 Solved: 2489
[Submit][Status][Discuss]
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
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
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
20%的数据中，m,n≤100; 40%的数据中，m,n≤1000; 100%的数据中，m,n≤10000。
Source