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

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 9094 Solved: 3808
[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继续回答上面的问题。

Input

第一行有两个正整数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

m,n≤10000

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

Source

整体二分真是个好东西啊，

而且特别好写。

思想大概就是把所有的询问全都放到一块处理，然后剩下的就和普通的处理一样了。

修改操作的话就是先删除再增加

第$k$大为经典操作，每次找比当前小的有多少个的时候用树状数组维护

#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 + , INF = 1e9 + ;

char buf[ << ], *p1 = buf, *p2 = buf;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', 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 = ;

    for(int i = pos; i > ; i -= lowbit(i)) ans += T[i];

    return ans;

}

void Solve(int lb, int rb, vector<Query> &Q) {

    if(Q.empty()) return ;

    if(rb - lb == ) {

        for(int i = ; i < Q.size(); i++)

            if(Q[i].opt == )

                ans[Q[i].id] = lb;

        return ;

    }

    vector<Query>L, R;

    int mid = (lb + rb) >> ;

    for(int i = ; i < Q.size(); i++) {

        Query p = Q[i];

        if(p.opt == ) {// 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 - );

            if(kth >= p.k) L.push_back(p);

            else p.k -= kth, R.push_back(p);

        }

    }

    for(int i = ; i < L.size(); i++)

        if(L[i].opt == )

            Add(L[i].l, -L[i].r);

    Solve(lb, mid, L); Solve(mid, rb, R);

}

main() {

    N = read(); M = read();

    for(int i = ; i <= N; i++) Q.push_back((Query){, i, , a[i] = read(), });

    for(int i = ; i <= M; i++) {

        char c = '_';while(c != 'C' && c != 'Q') c = getchar();

        if(c == 'C') {

            int pos = read(), val = read();

            Q.push_back((Query){, pos, -, a[pos], });

            Q.push_back((Query){, pos, , a[pos] = val, });

        } else {

            int ll = read(), rr = read(), kth = read();

            Q.push_back((Query){, ll, rr, kth, i});

        }

    }

    memset(ans, -0x3f, sizeof(ans));

    Solve(, 1e9, Q);

    for(int i = ; i <= M; i++)

        if(ans[i] >= -INF)

            printf("%d\n", ans[i]);

    return ;

}

巴特西

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

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

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

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

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