# BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 9094  Solved: 3808

[Submit][Status][Discuss]

## Description

],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改

## Input

Q i j k 或者 C i t

Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）

C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t

m,n≤10000

## Output

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

## Sample Input

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

3 6

## Source

```#include<cstdio>
#include<cstring>
#include<vector>
#define lowbit(x) ((x) & (-x))
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
char buf[1 << 21], *p1 = buf, *p2 = buf;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
struct Query {
int opt, l, r, k, id;
};
vector<Query> Q;
int N, M, a[MAXN], ans[MAXN], T[MAXN];
void Add(int pos, int val) { for(int i = pos; i <= N; i += lowbit(i)) T[i] += val;}
int Sum(int pos) {
int ans = 0;
for(int i = pos; i > 0; i -= lowbit(i)) ans += T[i];
return ans;
}
void Solve(int lb, int rb, vector<Query> &Q) {
if(Q.empty()) return ;
if(rb - lb == 1) {
for(int i = 0; i < Q.size(); i++)
if(Q[i].opt == 1)
ans[Q[i].id] = lb;
return ;
}
vector<Query>L, R;
int mid = (lb + rb) >> 1;
for(int i = 0; i < Q.size(); i++) {
Query p = Q[i];
if(p.opt == 0) {// l:pos  r:opt   k:val
if(p.k < mid) Add(p.l, p.r), L.push_back(p);
else R.push_back(p);
} else {// l: Ql   R: Ql  k:you know
int kth = Sum(p.r) - Sum(p.l - 1);
if(kth >= p.k) L.push_back(p);
else p.k -= kth, R.push_back(p);
}
}
for(int i = 0; i < L.size(); i++)
if(L[i].opt == 0)
Solve(lb, mid, L); Solve(mid, rb, R);
}
main() {
for(int i = 1; i <= N; i++) Q.push_back((Query){0, i, 1, a[i] = read(), 0});
for(int i = 1; i <= M; i++) {
char c = '_';while(c != 'C' && c != 'Q') c = getchar();
if(c == 'C') {
Q.push_back((Query){0, pos, -1, a[pos], 0});
Q.push_back((Query){0, pos, 1, a[pos] = val, 0});
} else {
Q.push_back((Query){1, ll, rr, kth, i});
}
}
memset(ans, -0x3f, sizeof(ans));
Solve(0, 1e9, Q);
for(int i = 1; i <= M; i++)
if(ans[i] >= -INF)
printf("%d\n", ans[i]);
return 0;
} ```

1811 篇文章114 人订阅

0 条评论

## 相关文章

1331

1021

882

### 1856: [Scoi2010]字符串

1856: [Scoi2010]字符串 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 847  Solved: ...

3676

3345

2753

### POJ 3278 Catch That Cow(BFS,板子题)

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions...

2965

2543

### fastjson详解

fastjson用于将Java Bean序列化为JSON字符串，也可以从JSON字符串反序列化到JavaBean。

6631

### java如何获取一个对象的大小

When---什么时候需要知道对象的内存大小 在内存足够用的情况下我们是不需要考虑java中一个对象所占内存大小的。但当一个系统的内存有限，或者某块程序代码允许...

1.2K7