「洛谷P2617」Dynamic Rankings

标算又是树套树?写不来QwQ…

传送门

BZOJ(是个权限题QwQ)

洛谷P2617

题解

据说这题可以用带修主席树、树套树、整体二分解。由于蒟蒻我实在太菜了QwQ,只好选择了整体二分。

把刚原始序列理解为n个添加操作,将修改操作理解为一个删除操作和一个添加操作。然后直接上整体二分,解法类似于「ZJOI2013」K大数查询。并且由于每次只需要修改一个位置的信息,所以用普通树状数组就行了呢poi,快得飞起(尽管我自带大常数QwQ)。

png1

代码

整体二分又好写又好理解呢poi

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
#include<cstdio>
using namespace std;
const int maxn=100005;
int n,m,tot,cnt,ans[maxn],A[maxn];
inline int read()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return ret*f;
}
struct BIT //封装好的树状数组
{
int Tree[maxn];
void Update(int pos,int delta){while(pos<=n){Tree[pos]+=delta;pos+=pos&-pos;}}
int Query(int pos){int ret=0;while(pos>0){ret+=Tree[pos];pos-=pos&-pos;}return ret;}
}Tr;
struct Command{int typ,idx,num,delta,L,R,k,id;}Q[maxn*4],Q1[maxn*4],Q2[maxn*4];
char GetChar() //读取操作类型,排除无用字符
{
char ch=getchar();
while(ch!='C'&&ch!='Q') ch=getchar();
return ch;
}
void BinarySearch(int L,int R,int S,int T) //整体二分
{
if(L>R||S>T) return;
int mid=L+R>>1,til1=0,til2=0;
if(L==R)
{
for(int i=S;i<=T;i++)
if(Q[i].typ)
ans[Q[i].id]=mid;
return;
}
for(int i=S;i<=T;i++)
{
if(!Q[i].typ)
{
if(Q[i].num<=mid)
{
Tr.Update(Q[i].idx,Q[i].delta);
Q1[++til1]=Q[i];
}
else Q2[++til2]=Q[i];
}
else
{
int cnt=Tr.Query(Q[i].R)-Tr.Query(Q[i].L-1);
if(cnt<Q[i].k)
{
Q[i].k-=cnt;
Q2[++til2]=Q[i];
}
else Q1[++til1]=Q[i];
}
}
for(int i=S;i<=T;i++) //别忘了还原树状数组哟poi
if(!Q[i].typ)
if(Q[i].num<=mid)
Tr.Update(Q[i].idx,-Q[i].delta);
for(int i=1;i<=til1;i++) Q[S+i-1]=Q1[i];
for(int i=1;i<=til2;i++) Q[S+til1+i-1]=Q2[i];
BinarySearch(L,mid,S,S+til1-1);
BinarySearch(mid+1,R,S+til1,T);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++){tot++;Q[tot].idx=i;Q[tot].num=A[i]=read();Q[tot].delta=1;}
for(int i=1;i<=m;i++)
{
if(GetChar()=='Q'){tot++;cnt++;Q[tot].typ=1;Q[tot].L=read();Q[tot].R=read();Q[tot].k=read();Q[tot].id=cnt;}
else
{
tot++;Q[tot].idx=read();Q[tot].num=read();Q[tot].delta=1;
tot++;Q[tot].idx=Q[tot-1].idx;Q[tot].num=A[Q[tot-1].idx];A[Q[tot-1].idx]=Q[tot-1].num;Q[tot].delta=-1;
}
}
BinarySearch(0,1000000000,1,tot);
for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
return 0;
}