「BZOJ1901」 Dynamic Rankings - 树套树/整体二分

本文主要是介绍「BZOJ1901」 Dynamic Rankings - 树套树/整体二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个长度为N的已知序列 $A[i](1\le i\le N)$ ，要求维护这个序列，能够支持以下两种操作：

查询 $A[i],A[i+1],A[i+2],…,A[j](1\le i\le j\le N)$ 中，升序排列后排名第k的数。
修改 $A [i]$ 的值为 $t$ 。

输入格式

第一行有两个正整数 $n, m$ 。分别表示序列的长度和指令的个数。第二行有 $n$ 个数，表示 $a[1],a[2],\cdots,a[n]$ 。接下来的 $m$ 行描述每条指令，每行的格式是下面两种格式中的一种。Q i j k或者C i t $(1 \leq i \leq j \leq n, 1 \leq k \leq j - i + 1)$ ，分别表示询问 $a[i],a[i+1],\cdots,a[j]$ 中第k小的数。把 $a [i]$ 改变成为 $t$ 。

输出格式

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

数据范围

$20\%$ 的数据中, $m, n \leq 100;$

$40\%$ 的数据中, $m, n \leq 1000;$

$100\%$ 的数据中, $m,n≤10000，a[i]\le 10^9.$

分析

在这里总结一下各种求区间第 $k$ 小的数据结构（对于划分树这种不常见的数据结构就不再介绍）。

树状数组套主席树

首先主席树是可以求区间第 $k$ 小的。如果对第 $i$ 个位置的线段树进行修改，则对于所有的 $j\ge i$ 都要进行修改，所以在外层套一个树状数组，就可以做到在 $O(\log^2n)$ 的时间内做到修改。

查询时先用 $p o s$ 在树状数组中跑一遍，找到需要查询的根节点，再调用函数。为了求得当前节点的值，可以用找到的根节点，将所有信息相加。最后所有根同时向左或向右走。

修改时先删除原来的值，在加入现在的值，同样在树状数组中，对每一个根进行一次修改。

由于是权值线段树，所以还要离线进行离散化。

代码

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=100005,M=N*25;
int L[M],R[M];
int n,m,c[M],a[N];
int root[N],tot,ntot;
vector<int> Li,Ri,ert;
int Qtype[N],Qx[N],Qy[N],Qk[N];
#define lowbit(x) ((x)&-(x))
int Build(int l,int r) {int rt=++tot;if (l==r) {c[rt]=0;return rt;}int mid=(l+r)>>1;L[rt]=Build(l,mid);R[rt]=Build(mid+1,r);return rt;
}
int Change(int p,int l,int r,int x,int v) {int rt=++tot;L[rt]=L[p];R[rt]=R[p];c[rt]=c[p];if (l==r) {c[rt]+=v;return rt;}int mid=(l+r)>>1;if (x<=mid) L[rt]=Change(L[p],l,mid,x,v);else R[rt]=Change(R[p],mid+1,r,x,v);c[rt]=c[L[rt]]+c[R[rt]];return rt;
}
void Need(int x,vector<int>& v) {//找到所需要的根 while (x) {v.push_back(root[x]);x-=lowbit(x);}
}
void BecomeL(vector<int>& v) {for (int i=0;i<v.size();i++) v[i]=L[v[i]];}
void BecomeR(vector<int>& v) {for (int i=0;i<v.size();i++) v[i]=R[v[i]];}
int Ask(int l,int r,int k) {if (l==r) return l;int suml=0,sumr=0;for (int i=0;i<Li.size();i++) suml+=c[L[Li[i]]];//累加 for (int i=0;i<Ri.size();i++) sumr+=c[L[Ri[i]]];int minus=sumr-suml;int mid=(l+r)>>1;if (minus>=k) {BecomeL(Li);//同向左 BecomeL(Ri);return Ask(l,mid,k);} else {BecomeR(Li);//同向右 BecomeR(Ri);return Ask(mid+1,r,k-minus);}
}
void Updata(int x,int v,int dt) {while (x<=n) {//它在树状数组中的对应所有的有关都要修改 root[x]=Change(root[x],1,ntot,v,dt);x+=lowbit(x);}
}
int GetNum(int val) {int t=lower_bound(ert.begin(),ert.end(),val)-ert.begin();return t+1;
}
int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) {scanf("%d",&a[i]);ert.push_back(a[i]);}while (getchar()!='\n');for (int i=1;i<=m;i++) {int x,y,k;char op[10];scanf("%s%d%d",op,&x,&y);if (op[0]=='C') {Qtype[i]=1;Qx[i]=x;Qy[i]=y;ert.push_back(y);} else {scanf("%d",&k);Qtype[i]=0;Qx[i]=x;Qy[i]=y;Qk[i]=k;}}sort(ert.begin(),ert.end());//离散化 vector<int>::iterator it=unique(ert.begin(),ert.end());ert.erase(it,ert.end());ntot=ert.size();root[0]=Build(1,ntot);for (int i=1;i<=n;i++)Updata(i,GetNum(a[i]),1);for (int i=1;i<=m;i++) {int x,y,k;x=Qx[i];y=Qy[i];k=Qk[i];if (Qtype[i]) {//修改 Updata(x,GetNum(a[x]),-1);//先删除 a[x]=y;Updata(x,GetNum(a[x]),1);//再加入 } else {//查询 Li.clear();Ri.clear();Need(x-1,Li);Need(y,Ri);printf("%d\n",ert[Ask(1,ntot,k)-1]);}}return 0;
}

线段树套平衡树

说起全局第 $k$ 小，首先想到的肯定是平衡树，然后对于区间操作，容易想到线段树。所以将这两个棵树结合起来就可以了。对于线段树的每个节点，为它所控制的区间的平衡树。

修改时将根到该节点路径上的节点的平衡树先删除原来的值，再加入当前值。时间复杂度 $O(\log^2n)$

查询时发现不能直接求得答案，但可以通过二分答案来求。设当前二分答案为 $m i d$ ，则在区间中查询有多少个元素小于 $m i d$ ，记为 $t$ ，若 $t\ge k$ ，则在令 $R = m i d$ ，否则令 $L = m i d + 1$ ，在新的区间内继续二分。时间复杂度 $O(\log^3n)$

代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=100005,M=N*25;
const int INF=0x7fffffff;
int c[M][2],f[M];
int sz[M],v[M],ct[M];
int rt[N<<2],ans,temp;
int a[N],n,m,tot;
//---------------Splay相关-----------------//
void Pushup(int x) {sz[x]=sz[c[x][0]]+sz[c[x][1]]+ct[x];}
void Rotate(int x) {//旋转 int y=f[x],z=f[y];int k=c[y][1]==x,w=c[x][k^1];if (z) c[z][c[z][1]==y]=x;c[y][k]=w;c[x][k^1]=y;f[y]=x;f[x]=z;f[w]=y;Pushup(y);Pushup(x);
}
void Splay(int x,int p,int at=0) {//伸展 while (f[x]!=at) {int y=f[x],z=f[y];if (z) Rotate((c[y][1]==x)^(c[z][1]==y)?x:y);Rotate(x);}if (!at) rt[p]=x;
}
void Insert(int p,int val) {//插入 if (!rt[p]) {rt[p]=++tot;sz[rt[p]]=ct[rt[p]]=1;v[rt[p]]=val;return;}int w=rt[p];while (1) {sz[w]++;if (v[w]==val) {ct[w]++;Splay(w,p);return;}int nxt=val<v[w]?0:1;if (!c[w][nxt]) {c[w][nxt]=++tot;f[tot]=w;sz[tot]=ct[tot]=1;v[tot]=val;Splay(tot,p);return;}w=c[w][nxt];}
}
int Find(int p,int val) {//查找 int w=rt[p];while (w) {if (v[w]==val) return w;if (val<v[w]) w=c[w][0];else w=c[w][1];}return 0;
}
void Remove(int p,int val) {//删除 int t;if (!(t=Find(p,val))) return;Splay(t,p);if (ct[t]>1) {ct[t]--;sz[t]--;return;}if (!c[t][0]) {f[c[t][1]]=0;p=c[t][1];return;}int lc=c[t][0];while (c[lc][1]) lc=c[lc][1];Splay(lc,p);f[c[t][1]]=lc;c[lc][1]=c[t][1];c[t][0]=c[t][1]=0;f[t]=0;sz[t]=ct[t]=v[t]=0;Pushup(lc);
}
int Pre(int p,int val) {//后继 int tmp=0,vt=-INF,w=rt[p];while (w) {if (v[w]==val) {int lc=c[w][0];if (lc) {while (c[lc][1]) lc=c[lc][1];tmp=lc;}break;}if (v[w]<val&&v[w]>vt) {tmp=w;vt=v[w];}w=(val<v[w]?c[w][0]:c[w][1]);}return tmp;
}
int Next(int p,int val) {//前驱 int tmp=0,vt=INF,w=rt[p];while (w) {if (v[w]==val) {int rc=c[w][1];if (rc) {while (c[rc][0]) rc=c[rc][0];tmp=rc;}break;}if (v[w]>val&&v[w]<vt) {tmp=w;vt=v[w];}w=(val<v[w]?c[w][0]:c[w][1]);}return tmp;
}
//-------------以上为Splay相关-------------//
//---------------线段树相关----------------//
void Build(int p,int l,int r) {//建树 Insert(p,-INF/2);Insert(p,INF/2);for (int i=l;i<=r;i++)Insert(p,a[i]);if (l==r) return;int mid=(l+r)>>1;Build(p<<1,l,mid);Build(p<<1|1,mid+1,r);
}
void AskRank(int p,int l,int r,int L,int R,int val) {//查询 if (L<=l&&r<=R) {int t=Find(p,val);if (!t) t=Next(p,val);Splay(t,p);ans+=sz[c[rt[p]][0]]-1;return;}int mid=(l+r)>>1;if (L<=mid) AskRank(p<<1,l,mid,L,R,val);if (R>mid) AskRank(p<<1|1,mid+1,r,L,R,val);
}
void Change(int p,int l,int r,int x,int val) {//修改 Remove(p,a[x]);Insert(p,val);if (l==r) return;int mid=(l+r)>>1;if (x<=mid) Change(p<<1,l,mid,x,val);else Change(p<<1|1,mid+1,r,x,val);
}
//---------------以上线段树相关--------------//
int GetKth(int x,int y,int k) {int mid,l,r;l=-INF/2,r=INF/2;while (l<r) {mid=(l+r)>>1;ans=0;AskRank(1,1,n,x,y,mid);//在线段树中查找它的排名即为小于mid的个数 if (ans<k) l=mid+1; else r=mid;}return l-1;
}
int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]);Build(1,1,n);//建树 for (int i=1;i<=m;i++) {int l,r,x,pos;char op[10];scanf("%s",op);if (op[0]=='C') scanf("%d%d",&pos,&x);else scanf("%d%d%d",&l,&r,&x);if (op[0]=='Q') {printf("%d\n",GetKth(l,r,x));} else if (op[0]=='C') {Change(1,1,n,pos,x);a[pos]=x;}}return 0;
}

整体二分

离线处理，整体二分。对于每一个初始值看成修改操作，每一个修改转为删除原来的值，加入当前的值两种操作，查询正常。然后在值域内进行整体二分。总时间复杂度 $O(n\log^2n)$

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N=10005;
const int INF=0x7fffffff;
struct Query {int x,y,v,id;
}q[N*3],ql[N*3],qr[N*3];
int a[N],n,m;
int tot,qtot;
int ans[N];
struct Bit {int c[N],res;void Add(int x,int v) {for (;x<=n;x+=x&-x) c[x]+=v;}int Ask(int x) {for (res=0;x;x-=x&-x) res+=c[x];return res;}int Ask(int l,int r) {return Ask(r)-Ask(l-1);}
}t;
void Solve(int l,int r,int L,int R) {if (l>r) return;//操作序列为空返回 if (L==R) {//递归到叶子节点，答案为L for (int i=l;i<=r;i++)if (q[i].y) ans[q[i].id]=L;return;}int mid=(L+R)>>1;int lt=0,rt=0;for (int i=l;i<=r;i++) {//依次处理每个操作 if (!q[i].y) {//修改 if (q[i].x<=mid) {//符合条件 t.Add(q[i].id,q[i].v);//在树状数组对应位置加 ql[++lt]=q[i];//分到左区间 } else qr[++rt]=q[i];//分到右区间 } else {//查询 int cnt=t.Ask(q[i].x,q[i].y);//询问区间内小于mid的个数 if (cnt<q[i].v) {//小于说明不够，分到右区间 q[i].v-=cnt;//减去贡献 qr[++rt]=q[i];} else ql[++lt]=q[i];//多了，分到右区间 }}for (int i=1;i<=lt;i++)//撤销对树状数组的操作 if (!ql[i].y)t.Add(ql[i].id,-ql[i].v);for (int i=1;i<=lt;i++) q[l+i-1]=ql[i];//合并 for (int i=1;i<=rt;i++) q[l+lt+i-1]=qr[i];Solve(l,l+lt-1,L,mid);//递归二分 Solve(l+lt,r,mid+1,R);
}
int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) {scanf("%d",&a[i]);//初始值 q[++tot]=(Query){a[i],0,1,i};}for (int i=1;i<=m;i++) {char op[10];int x,y,v;scanf("%s",op);if (op[0]=='Q') {//查询 scanf("%d%d%d",&x,&y,&v);q[++tot]=(Query){x,y,v,++qtot};} else {//修改 scanf("%d%d",&x,&v);q[++tot]=(Query){a[x],0,-1,x};a[x]=v;q[++tot]=(Query){a[x],0,1,x};}}Solve(1,tot,0,INF);for (int i=1;i<=qtot;i++)printf("%d\n",ans[i]);return 0;
}