[BZOJ 1901] Dynamic Rankings

Posted on | Edited on | In , | Views:

题目链接

BZOJ 1901

前言

首先不得不说某些博客名称写的是树状数组套主席树的人，实际上写的是树状数组套权值线段树，这种把权值线段树和主席树划等号的人，简直是误人子弟。主席树实际上是可持久化的权值线段树，他的核心思想是现在这个时刻的权值线段树要继承上个时刻的权值线段树，而这道题目中没有用到这种方法，这里必须要申明一下。
当然也有一些神犇用的确实是树状数组套主席树，%%%%

题解

我们的这个东西相当于解决一个区间查询，单点修改的问题。于是我们想到了树状数组，我们对于树状数组的每一个节点建一颗权值线段树，那么我们想得到一个区间的权值线段树的话，只要用树状数组得到前缀的权值线段树然后减一减就行了，然后修改的话，我们只要把包含这个点的权值线段树加一加减一减就行了，这个可以用树状数组处理。
复杂度分析一波的话，每次查询和修改都会访问到log颗权值线段树，然后权值线段树查询第k大也是log的，所以总时间复杂度是两个log的，空间的话用动态开点实现，也是两个log的。

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define INF (2139062143)
#define N (10005)
using namespace std;
int n,m,cnt,x,y,z,t1,t2;
int a[N],q1[N],q2[N],root[N];
int lson[N*32*14*2],rson[N*32*14],size[N*32*14];
char c[11];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
void insert(int &u,int l,int r,int op){
    if (!u) u=++cnt;
    size[u]++;
    if (l==r) return;
    int mid=l+r>>1;
    if (op<=mid) insert(lson[u],l,mid,op);
    else insert(rson[u],mid+1,r,op); 
}
void del(int u,int l,int r,int op){
    size[u]--;
    if (l==r) return;
    int mid=l+r>>1;
    if (op<=mid) del(lson[u],l,mid,op);
    else del(rson[u],mid+1,r,op);
} 
inline void add(int x,int data){
    for (int i=x;i<=n;i+=i&-i) insert(root[i],0,1e9,data);
}
inline void change(int x,int data){
    for (int i=x;i<=n;i+=i&-i) insert(root[i],0,1e9,data),del(root[i],0,1e9,a[x]);
}
int query(int l,int r,int k){
    if (l==r) return l;
    int lsize=0;
    for (int i=1;i<=t1;i++) lsize+=size[lson[q1[i]]];
    for (int i=1;i<=t2;i++) lsize-=size[lson[q2[i]]];
    int mid=l+r>>1;
    //printf("%d %d %d\n",l,mid,lsize); 
    if (k>lsize){
        for (int i=1;i<=t1;i++) q1[i]=rson[q1[i]];
        for (int i=1;i<=t2;i++) q2[i]=rson[q2[i]];
        return query(mid+1,r,k-lsize);
    }
    else{
        for (int i=1;i<=t1;i++) q1[i]=lson[q1[i]];
        for (int i=1;i<=t2;i++) q2[i]=lson[q2[i]];
        return query(l,mid,k);
    }
}
struct node{
    int id,data;
}b[N<<1];
int main(){
    read(n),read(m);
    for (int i=1;i<=n;i++){
        read(a[i]);
        add(i,a[i]);
    }
    for (int i=1;i<=m;i++){
        scanf("%s",c);
        if (c[0]=='Q'){
            read(x),read(y),read(z);
            t1=0,t2=0; 
            for (int j=y;j;j-=j&-j) q1[++t1]=root[j];
            for (int j=x-1;j;j-=j&-j) q2[++t2]=root[j];
            printf("%d\n",query(0,1e9,z));
        }
        if (c[0]=='C'){
            read(x),read(z);
            change(x,z);
            a[x]=z;
        }
    }
    return 0;
}