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 + 10, INF = 1e9 + 10;
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    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)
            Add(L[i].l, -L[i].r);
    Solve(lb, mid, L); Solve(mid, rb, R);
}
main() { 
    N = read(); M = read();
    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') {
            int pos = read(), val = read();
            Q.push_back((Query){0, pos, -1, a[pos], 0});
            Q.push_back((Query){0, pos, 1, a[pos] = val, 0});
        } else {
            int ll = read(), rr = read(), kth = read();
            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;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏進无尽的文章

Swift| 基础语法(四)

总结下 swift下的基础语法,里面涉及到:常量&变量、Swift中的数据类型、逻辑分支、循环、字符串相关、数组和字典、方法的书写调用等内容,考虑到阅读体验分多...

1331
来自专栏Hongten

python开发_python代码风格(coding style)

1021
来自专栏desperate633

LintCode 单词切分题目分析

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

882
来自专栏HansBug's Lab

1856: [Scoi2010]字符串

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

3676
来自专栏10km的专栏

fastjson:javabean按字段(field)序列化存储为Map并反序列化

大部分json工具对java对象整体序列化都提供了简单的调用方式,以fastjson为例: Model model = new Model(); String ...

3345
来自专栏对角另一面

lodash源码分析之获取数据类型

所有的悲伤,总会留下一丝欢乐的线索,所有的遗憾,总会留下一处完美的角落,我在冰峰的深海,寻找希望的缺口,却在惊醒时,瞥见绝美的阳光! ——几米 本文为读...

2753
来自专栏小樱的经验随笔

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

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

2965
来自专栏cmazxiaoma的架构师之路

你应该会的一道多线程笔试题

2543
来自专栏java、Spring、技术分享

fastjson详解

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

6631
来自专栏Java开发者杂谈

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

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

1.2K7

扫码关注云+社区