Luogu Dynamic Ranking (带修改的主席树)
题目大意:
网址:https://www.luogu.org/problemnew/show/2617
给定一个序列a[1]、a[2]、...、a[N],完成M个操作,操作有两种:
[1]Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。
[2]C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。
数据范围: \(1≤n≤10000,1≤m≤10000\)
解法:带修改的主席树:
原本的主席树是维护了一个线段树前缀。
那么前缀有没有想到什么东西? 树状数组\(Bits\)是不是很 ...... ?
那么现在,我们用树状数组套主席树,不就可以实现带修改的可持久化了吗。
具体来说 \(T[1]维护rt[1]\) , \(T[2]维护rt[1]、rt[2]\) , \(T[3]维护rt[3]\) ......
就与树状数组是一样的。
那么现在,两个具体的操作:
修改:
修改需要修改\(logN\)棵主席树,将涉及修改节点的\(log\)个主席树先删后加点即可。
具体来说,修改x位置的,则要修改:for(x; x; x -= (x&-x))Update(rt[x]);
查询:
考虑一下树状数组的查询,是用到了两个前缀相减的方法。
那么这里也是一样的,查询\([L,R]\)就是\([1,R]\)的值减去\([1,(L-1)]\)的值。
具体来说,对于\([L,R]\)区间对应的主席树,每个点的sum值为:
\[Sum[ro] = ∑sum[ro[u]] - ∑sum[ro[v]];u∈[1,R],v∈[1,L-1]\]
那么以查询第区间第\(k\)大为例子,直接将\(k\)与节点的\(Sum\)值比较即可。
总复杂度:
时间复杂度:\(O(NLog^2N)\) , 空间复杂度\(O(NLog^2N)\)
两个去重、二分的函数:
Unique去重函数:
对于a[1]、a[2]、....、a[N],去重函数为:
\[Length = Unique(a+1,a+N+1) - a - 1;\]
Unique函数返回的是 去重后后面第一个空位置,所以要长度减1。
去重完的序列即为a[1]、a[2]、....、a[Length];
Lower_Bound二分函数:
对于序列a[1]、a[2]、....、a[N],查找<=x的最接近数的序列位置,为:
k = lower_bound(a+1,a+N+1,x) - oder;
low_bound返回的是那个值的地址,应该要与第0个位置相减得到其确切的位置。
具体实现代码:
#include<bits/stdc++.h>
#define RG register
#define IL inline
#define maxn 200005
using namespace std;
int N,M,Q,cntl,cntr,lg;
struct Ques{int l,r,k;}qs[maxn];
int rt[2*maxn],ls[20*maxn],rs[20*maxn],sum[20*maxn],tpl[maxn],tpr[maxn];
int a[maxn],oder[2*maxn],cnt;
void Update(int &ro,int l,int r,int ps,int chg){
if(!ro)ro = ++cnt;
sum[ro] += chg;
if(l == r)return;
RG int mid = (l+r)>>1;
if(ps <= mid)Update(ls[ro],l,mid,ps,chg);
else Update(rs[ro],mid+1,r,ps,chg);
}
IL void Modify(RG int ps,RG int chg){
RG int k = lower_bound(oder+1,oder+lg+1,a[ps]) - oder;
for(RG int i = ps; i <= N; i += (i&-i))
Update(rt[i],1,lg,k,chg);
}
int Query(int l,int r,int k){
if(l == r)return l;
RG int mid = (l+r)>>1,Sum = 0;
for(RG int i = 1; i <= cntl; i ++)Sum -= sum[ls[tpl[i]]];
for(RG int i = 1; i <= cntr; i ++)Sum += sum[ls[tpr[i]]];
if(k <= Sum){
for(RG int i = 1; i <= cntl; i ++)tpl[i] = ls[tpl[i]];
for(RG int i = 1; i <= cntr; i ++)tpr[i] = ls[tpr[i]];
return Query(l,mid,k);
}
else{
for(RG int i = 1; i <= cntl; i ++)tpl[i] = rs[tpl[i]];
for(RG int i = 1; i <= cntr; i ++)tpr[i] = rs[tpr[i]];
return Query(mid+1,r,k-Sum);
}
}
IL int Get(RG int l,RG int r,RG int k){
cntl = cntr = 0;
for(RG int i = (l-1); i ; i -= (i&-i))
tpl[++cntl] = rt[i];
for(RG int i = r; i ; i -= (i&-i))
tpr[++cntr] = rt[i];
return Query(1,lg,k);
}
int main(){
freopen("testdate.in","r",stdin);
cin>>N>>M;
for(RG int i = 1; i <= N; i ++)
cin>>a[i] , oder[++lg] = a[i];
char od; int l,r,k;
for(RG int i = 1,c; i <= M; i ++){
cin>>od;
if(od == 'Q')cin>>l>>r>>k,qs[i] = (Ques){l,r,k};
else cin>>l>>k,qs[i] = (Ques){l,0,k},oder[++lg] = k;
}
sort(oder+1,oder+lg+1);
lg = unique(oder+1,oder+lg+1) - oder - 1;
for(RG int i = 1; i <= N; i ++)Modify(i,1);
for(RG int i = 1; i <= M; i ++)
{
if(!qs[i].r){
Modify(qs[i].l , -1);
a[qs[i].l] = qs[i].k;
Modify(qs[i].l , 1);
}
else printf("%d\n",oder[Get(qs[i].l,qs[i].r,qs[i].k)]);
}
return 0;
}
最新文章
- JS-reverse(数组内容颠倒)
- ASP.NET Core 1.0 入门——了解一个空项目
- SSH框架执行自己定义的SQL语句
- 内存,堆,栈,heap,stack,data
- android图片缓存(包含ReusableBitmapDrawable和BitmapPool)
- Windows Myeclipse 10 安装 Perl 插件
- linux清空日志文件内容 (转)
- Android Animation学习笔记
- phpstrom 与 xdebug 配合实现PHP单步调试
- 阿牛的EOF牛肉串
- 在线office文档编辑NTKO使用心得
- Java-IO之超类OutputStream
- Ubuntu18.04下可以完美运行Quake3 Arena
- [转]Oracle密码过期, 报:ORA-01017: 用户名/口令无效; 登录被拒绝
- AngularJS——第3章 指令
- [清华集训2015 Day1]主旋律-[状压dp+容斥]
- Python+Requests接口测试教程(2):requests
- Service(一):认识service、绑定Service
- asp.net 判断日期是否为空
- pytest文档27-pytest分布式执行(pytest-xdist)