【Bzoj1901】Dynamic Rankings

来源和评测点

Author: XIN, Tao
Source: Online Contest of Christopher’s Adventure
Bzoj1901
Zju2112 多组数据
Luogu2617
Caioj1442

题目

【题目大意】
给n(1<=n<=50000)个数字,进行m(1<=m<=10000)次操作,有两种操作:
Q l r k:询问l到r第k小的数。
C x k:改变第x个数的值为k。
【输入格式】
第一行为n和m。
接下来一行n个数。
接下来m行为m个操作。
【输出格式】
遇到Q操作就输出。
【输入样例】
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
【输出样例】
3
6
3
6

分析

建议先阅读本文:【OI之路】06树-6主席树

可持续线段树(主席树)套树状数组

修改操作:
原本的add是直接+1,现在考虑添加参数o,表示c要加上o
然后先把原本数字删掉,添加新数字即可。
但这样修改一个就要修改后面的全部,所以像许多其他题目一样,
经典的带修改时用树状数组代替前缀和。

询问操作:
也有些不同,因为统计左边部分时,用的只是某一层的值,
所以用getsum时,引入函数turn来转向效果更佳~

然鹅,Zoj死都SF,调了一整天,狂对拍,狂检查,
都无济于事,又放弃了……

代码

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
//Zory-2018
//*******************主函数******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
//*******************全局常量*******************
const int MAXN=51000,MAXM=11000;
//*******************全局定义*******************
int n;
int ust[MAXN];
int rx;//离散化后最大值
//*******************主席树*******************
struct nod
{
int c;
int lc,rc;
}p[MAXN*17];
int rt[MAXN];
int cnt;
void add(int &x,int l,int r,int pos,int c)
{
if(x==0) x=++cnt;
p[x].c+=c;
if(l==r) return;//debug
int mid=(l+r)>>1;
if(pos<=mid) add(p[x].lc,l,mid,pos,c);
else add(p[x].rc,mid+1,r,pos,c);
}
//*******************树状数组*******************
int lowbit(int x) {return x&(-x);}
void change(int x,int p,int c)
{
while(x<=n)
{
add(rt[x],1,rx,p,c);
x+=lowbit(x);
}
}
int lsum(int x)
{
int sum=0;
while(x>=1)
{
sum+=p[ p[ust[x]].lc ].c;
x-=lowbit(x);
}
return sum;
}
//*******************实现******************
int now[MAXN];
void solve1(int x,int k)
{
change(x,now[x],-1);
now[x]=k;
change(x,now[x],1);
}
void turn(int x,int tn)
{
while(x>=1)
{
if(tn==0) ust[x]=rt[x];
if(tn<0) ust[x]=p[ ust[x] ].lc;
if(tn>0) ust[x]=p[ ust[x] ].rc;
x-=lowbit(x);
}
}
int ask(int x,int y,int l,int r,int k)//l、r锁定
{
if(l==r) return l;
int lm=lsum(y)-lsum(x);
int mid=(l+r)/2;
if(k<=lm)
{
turn(x,-1);turn(y,-1);
return ask(x,y,l,mid,k);
}
else
{
turn(x,1);turn(y,1);
return ask(x,y,mid+1,r,k-lm);
}
}
int solve2(int x,int y,int k)
{
turn(x-1,0);turn(y,0);//初始化
return ask(x-1,y,1,rx,k);
}
//*******************离散化*******************
struct Qes
{
int op;
int x,y,k;
}q[MAXM];
int num[MAXN+MAXM];//原值
struct Lsh
{
int x,id,z;
}a[MAXN+MAXM];
bool cmp(Lsh a,Lsh b) {return a.x<b.x;}
void lsh(int all)
{
sort(a+1,a+all+1,cmp);
rx=0;a[0].x=-666;//debug
for(int i=1;i<=all;i++)
{
if(a[i-1].x!=a[i].x) num[++rx]=a[i].x;
if(a[i].id<=n) a[a[i].id].z=rx;
else q[a[i].id-n].k=rx;
}
}
//*******************主函数******************
char s[5];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(rt,0,sizeof(rt));
int m;scanf("%d%d",&n,&m);
for(int i=1;i<=cnt;i++) p[i].c=p[i].lc=p[i].rc=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i;
int qs=0;
for(int i=1;i<=m;i++)
{
scanf("%s",s);
if(s[0]=='C')
{
q[i].op=0;
scanf("%d%d",&q[i].x,&q[i].k);
qs++;
a[n+qs].x=q[i].k;
a[n+qs].id=n+i;
}
else
{
q[i].op=1;
scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].k);
}
}
lsh(n+qs);
cnt=0;
for(int i=1;i<=n;i++) change(i,a[i].z,1),now[i]=a[i].z;
for(int i=1;i<=m;i++)
{
if(q[i].op==0) solve1(q[i].x,q[i].k);
else printf("%d\n",num[ solve2(q[i].x,q[i].y,q[i].k) ]);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/8705.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%