(luogu2617)Dynamic Rankings

发表于 分类于 ， ，

原题链接

思路:

这题有两种解法， 最标准的解法是树状数组套主席树 (其实是套线段树), 可以做到在线解决，缺点是写起来挺麻烦. (实际上用了离散化还是离线的)

同时题目可以离线解决，意味着可以使用整体二分.

由于转为整体二分后变成单点修改区间查询，所以使用树状数组.

代码:

(整体二分): 

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <iostream>
#include <cctype>
#include <algorithm>
using namespace std;
const int Mn(100500);
void qrd(int& x) {
    x = 0;
    char c=getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}
inline int lb(int x) {  //lowbit
    return x&(-x);
}

int n,m;
int sn;

int a[Mn],shf[Mn*2];    //原数组, 离散化数组

struct Query {  //操作及询问
    bool t; //是否修改
    int x,y,z,id;
}q[Mn*3],tq[Mn*3];  //tq为辅助数组

int ans[Mn];    //答案

int c[Mn];
void add(int p,int x) { //BIT修改
    for(;p<=n;p += lb(p)) {
        c[p] += x;
    }
}
int sum(int p) {    //BIT前缀和
    int ret(0);
    for(;p;p -= lb(p)) {
        ret += c[p];
    }
    return ret;
}

void solve(int l,int r,int ql,int qr) { //二分主函数
    if(ql>qr) { //ql>qr说明无需处理, 直接返回
        return;
    }
    if(l==r) {
        for(int i(ql);i<=qr;++i) {
            Query& nq(q[i]);
            if(!nq.t) {
                ans[nq.id] = shf[l];    //l==r对每个询问记录答案
            }
        }
        return;
    }
    int mid((l+r)/2);
    int pl(ql-1), pr(qr+1); //左右指针
    for(int i(ql);i<=qr;++i) {
        Query& nq(q[i]);
        if(nq.t) {
            if(nq.y<=shf[mid]) {    //放入左边并修改
                add(nq.x,nq.z);
                tq[++pl] = nq;
            } else {    //放入右边
                tq[--pr] = nq;
            }
        } else {
            int sz = sum(nq.y) - sum(nq.x-1);   //查询
            if(sz >= nq.z) {    //放入左边
                tq[++pl] = nq;
            } else {
                nq.z -= sz; //注意减去左边区间贡献
                tq[--pr] = nq;
            }
        }
    }
    for(int i(ql);i<=qr;++i) {
        Query& nq(q[i]);
        if(nq.t && nq.y<=shf[mid]) {
            for(int p(nq.x);p<=n;p+=lb(p)) {
                c[p] = 0;       //清零
            }
        }
    }
    int cnt(ql-1);
    for(int i(ql);i<=pl;++i) {  //并入左区间
        q[++cnt] = tq[i];
    }
    for(int i(qr);i>=pr;--i) {  //并入右区间
        q[++cnt] = tq[i];
    }
    solve(l,mid,ql,pl);     //递归解决
    solve(mid+1,r,pl+1,qr);
}

int main() {
    qrd(n), qrd(m);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
        q[i] = {true,i,a[i],1,0};   //将初始化视为添加操作
        shf[i] = a[i];
    }
    sn = n;
    int qrc(0),qc(n);
    for(int i(n+1);i<=n+m;++i) {
        char op;
        cin >> op;
        if(op=='Q') {
            q[++qc].t = false;
            qrd(q[qc].x), qrd(q[qc].y), qrd(q[qc].z);
            q[qc].id = ++qrc;
        } else {
            int x,y;
            qrd(x), qrd(y);
            shf[++sn] = y;
            q[++qc] = {true,x,a[x],-1,0};   //修改分为添加和删除
            q[++qc] = {true,x,y,1,0};
            a[x] = y;
        }
    }

    sort(shf+1,shf+sn+1);
    sn = unique(shf+1,shf+sn+1)-shf-1;
    solve(1,sn,1,qc);
    for(int i(1);i<=qrc;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

(树套树): 

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <cstdio>
#include <iostream>
#include <cctype>
#include <algorithm>
using namespace std;
const int Mn(100500);
void qrd(int& x) {
    x = 0;
    char c=getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}
inline int lb(int x) {
    return x&(-x);
}

int a[Mn],shf[Mn*2];

struct Query {
    int t,x,y,z;
}q[Mn];

struct Sgn {    //线段树结点
    int v;
    Sgn *ls,*rs;
}*bitr[Mn];
Sgn *nil = new Sgn();   //空结点
void bud(int l,int r,Sgn* p) {  //建空树
    p->v = 0;
    if(l==r) {
        p->ls = p->rs = nil;
        return;
    }
    int mid((l+r)/2);
    p->ls = new Sgn();
    p->rs = new Sgn();
    bud(l,mid,p->ls);
    bud(mid+1,r,p->rs);
}
void mdf(int l,int r,int mp,int mv,Sgn*& p) {   //修改线段树
    if(p==nil) {
        p = new Sgn();
        p->ls = p->rs = nil;
    }
    if(l==r) {
        p->v += mv;
        return;
    }
    int mid((l+r)/2);
    if(mid>=mp) {
        mdf(l,mid,mp,mv,p->ls);
    } else {
        mdf(mid+1,r,mp,mv,p->rs);
    }
    p->v = p->ls->v + p->rs->v;
}
Sgn *tmpq[2][Mn];   //查询根
int qcn[2]; //根数量
int qry(int l,int r,int k) {    //查询
    if(l==r) {
        return shf[l];
    }
    //计算左儿子
    int sum(0);
    for(int i(1);i<=qcn[1];++i) {
        sum += tmpq[1][i]->ls->v;
    }
    for(int i(1);i<=qcn[0];++i) {
        sum -= tmpq[0][i]->ls->v;
    }
    int mid((l+r)/2);
    if(k <= sum) {
        for(int i(1);i<=qcn[1];++i) {
            tmpq[1][i] = tmpq[1][i]->ls;
        }
        for(int i(1);i<=qcn[0];++i) {
            tmpq[0][i] = tmpq[0][i]->ls;
        }
        return qry(l,mid,k);
    } else {
        for(int i(1);i<=qcn[1];++i) {
            tmpq[1][i] = tmpq[1][i]->rs;
        }
        for(int i(1);i<=qcn[0];++i) {
            tmpq[0][i] = tmpq[0][i]->rs;
        }
        return qry(mid+1,r,k-sum);
    }
}

int main() {
    nil->ls = nil->rs = nil;    //初始化
    int n,m;
    qrd(n), qrd(m);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
        shf[i] = a[i];
    }
    int sn(n);
    for(int i(1);i<=m;++i) {
        char op;
        cin >> op;
        if(op=='Q') {
            q[i].t = 0;
            qrd(q[i].x), qrd(q[i].y), qrd(q[i].z);
        } else {
            q[i].t = 1;
            qrd(q[i].x), qrd(q[i].y);
            shf[++sn] = q[i].y;
        }
    }

    sort(shf+1,shf+sn+1);
    sn = unique(shf+1,shf+sn+1)-shf-1;
    for(int i(1);i<=n+1;++i) {
        bitr[i] = nil;
    }
    for(int i(1);i<=n;++i) {
        int t(i);
        int mp = lower_bound(shf+1,shf+sn+1,a[i])-shf;
        while(t<=n) {
            mdf(1,sn,mp,1,bitr[t]);
            t += lb(t);
        }
    }

    for(int i(1);i<=m;++i) {
        Query& d(q[i]);
        if(d.t==0) {
            if(d.y==1) {
                printf("%d\n",a[1]);
                continue;
            }
            qcn[0] = qcn[1] = 0;
            d.x -= 1;
            while(d.x) {    //装入左端点相关根
                tmpq[0][++qcn[0]] = bitr[d.x];
                d.x -= lb(d.x);
            }
            while(d.y) {    //装入右端点相关根
                tmpq[1][++qcn[1]] = bitr[d.y];
                d.y -= lb(d.y);
            }
            int ans = qry(1,sn,d.z);
            printf("%d\n",ans);
        } else {
            int tmp(d.x);
            int mp = lower_bound(shf+1,shf+sn+1,a[d.x])-shf;
            while(tmp<=n) {
                mdf(1,sn,mp,-1,bitr[tmp]);  //嵌套修改
                tmp += lb(tmp);
            }
            a[d.x] = d.y;
            tmp = d.x;
            mp = lower_bound(shf+1,shf+sn+1,d.y)-shf;
            while(tmp<=n) {
                mdf(1,sn,mp,1,bitr[tmp]);
                tmp += lb(tmp);
            }
        }
    }
    return 0;
}