【poj2104】$K-th\ Number$——无修改区间第K小问题
题目大意
给出一个有$n$个数的数列，执行$m$次询问
每次询问在区间$[l,r]$中第$k$小的数
数据范围
$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 5000$
题解
由于操作只有询问，不执行修改，那么可以直接套用可持久化线段树即可
Question Ⅰ：可持久化线段树是啥？可持久化线段树也叫主席树，它的特点就是能够充分利用历史信息
对于这道题，具体做法就是，建$n$棵权值线段树，第$i$棵树记录在数列区间$[1,i]$中权值出现的个数
然后由于这$n$棵权值线段树的结构都是相似的，所以询问区间$[l,r]$时，可以用第$r$棵权值线段树对应减去第$l-1$棵权值线段树，得到$[l,r]$区间权值的信息，最后沿着新树直接向下查找得到第$k$小的数
Question Ⅱ：建n棵权值线段树，不会空间溢出吗？直接大力造$n$棵权值线段树肯定会空间溢出啦，但可持久化线段树利用历史信息可以节省大量空间
具体来说，第$i$棵权值线段树和第$i-1$棵权值线段树相比，只是多更新了一个权值
那么这个权值在权值线段树中只是影响了单条路径而已，因此可以在第$i$棵线段树中把不影响的子节点直接指向第$i-1$棵线段树的对应节点，就可以节省好多好多空间啦！
Question Ⅲ：建立权值线段树，那么边界范围不会过大导致自取灭亡吗？离散化大法好！
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,size,tot;
int a[100500],num[100500],hash[100500];
int root[100500],ls[2000500],rs[2000500],sum[2000500];
inline int find(int x){
int l=1,r=tot;
while (l<=r){
int mid=(l+r)>>1;
if (hash[mid]<x) l=mid+1;
else r=mid-1;
}
return l;
}
inline void init(){
n=read(),m=read();
For(i,1,n) a[i]=read(),num[i]=a[i];
sort(num+1,num+n+1);
hash[++tot]=num[1];
For(i,2,n)
if (num[i]!=num[i-1]) hash[++tot]=num[i];
}
void insert(int l,int r,int x,int &y,int c){
y=++size;
sum[y]=sum[x]+1;
if (l==r) return;
ls[y]=ls[x];rs[y]=rs[x];
int mid=(l+r)>>1;
if (c<=mid) insert(l,mid,ls[x],ls[y],c);
else insert(mid+1,r,rs[x],rs[y],c);
}
int ask(int l,int r,int x,int y,int k){
if (l==r) return l;
int mid=(l+r)>>1;
if (sum[ls[y]]-sum[ls[x]]>=k) return ask(l,mid,ls[x],ls[y],k);
else return ask(mid+1,r,rs[x],rs[y],k-(sum[ls[y]]-sum[ls[x]]));
}
int main(){
init();
For(i,1,n) insert(1,tot,root[i-1],root[i],find(a[i]));
For(i,1,m){
int l=read(),r=read(),x=read();
printf("%d\n",hash[ask(1,tot,root[l-1],root[r],x)]);
}
return 0;
}【bzoj2588】Count on a tree——无修改树上第K小问题
题目大意
给定一棵$n$个节点的树，每个点有一个权值
强制在线执行$m$次询问，每次询问两个节点间路径中权值第$k$小的节点权值
数据范围
$n,m\leqslant 10^5$
题解
这道题和上题相似，实际上想法也是差不多，一样是建立权值线段树，然后统计区间信息即可
Question Ⅳ：可这不是数列哦，怎么在树上建权值线段树？每个节点到根节点的路径都是独一无二的，所以要先跑一遍$dfs$序，然后根据每条节点到根节点的路径建树
Question Ⅴ：两个节点间的路径要统计区间信息？对于询问两个节点$a,b$，跑一遍倍增$LCA$得到$LCA(a,b)=c$，设$c$节点的父亲为$d$节点
区间信息就可以表示为$tree[a]+tree[b]-tree[c]-tree[d]$，然后直接向下查找
Tips：当然，离散化不能丢程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Ford(i,r,l) for(int i=r;i>=l;i--)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,size,tot,et,cnt,lastans;
int root[100500],ls[2000500],rs[2000500],sum[2000500];
struct edge{int to,next;}e[200500];
int last[100500],deep[100500],f[100500][17];
int a[100500],tmp[100500],hash[100500];
int num[100500],pos[100500];
inline void addedge(int u,int v){
e[++et]=(edge){v,last[u]};last[u]=et;
e[++et]=(edge){u,last[v]};last[v]=et;
}
inline int find(int x){
int l=1,r=tot;
while (l<=r){
int mid=(l+r)>>1;
if (hash[mid]<x) l=mid+1;
else r=mid-1;
}
return l;
}
inline int lca(int x,int y){
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
For(i,0,16)
if ((1<<i)&t) x=f[x][i];
Ford(i,16,0)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
if (x==y) return x;
else return f[x][0];
}
inline void init(){
n=read(),m=read();
For(i,1,n) a[i]=read(),tmp[i]=a[i];
sort(tmp+1,tmp+n+1);
hash[++tot]=tmp[1];
For(i,2,n)
if (tmp[i]!=tmp[i-1]) hash[++tot]=tmp[i];
For(i,1,n) a[i]=find(a[i]);
}
void dfs(int x){
cnt++;num[cnt]=x;pos[x]=cnt;
For(i,1,16)
if ((1<<i)<=deep[x]) f[x][i]=f[f[x][i-1]][i-1];
else break;
goedge(i,x)
if (f[x][0]!=e[i].to){
deep[e[i].to]=deep[x]+1;
f[e[i].to][0]=x;
dfs(e[i].to);
}
}
void insert(int l,int r,int x,int &y,int c){
y=++size;
sum[y]=sum[x]+1;
if (l==r) return;
ls[y]=ls[x];rs[y]=rs[x];
int mid=(l+r)>>1;
if (c<=mid) insert(l,mid,ls[x],ls[y],c);
else insert(mid+1,r,rs[x],rs[y],c);
}
int query(int l,int r,int a,int b,int c,int d,int k){
if (l==r) return hash[l];
int mid=(l+r)>>1;
int temp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
if (temp>=k) return query(l,mid,ls[a],ls[b],ls[c],ls[d],k);
else return query(mid+1,r,rs[a],rs[b],rs[c],rs[d],k-temp);
}
int main(){
init();
For(i,1,n-1){
int u=read(),v=read();
addedge(u,v);
}
dfs(1);
For(i,1,n) insert(1,tot,root[pos[f[num[i]][0]]],root[i],a[num[i]]);
For(i,1,m){
int x=read()^lastans,y=read(),k=read(),t=lca(x,y),ft=f[t][0];
lastans=query(1,tot,root[pos[x]],root[pos[y]],root[pos[t]],root[pos[ft]],k);
printf("%d",lastans);
if (i!=m) puts("");
}
return 0;
}【bzoj1901】【zoj2112】Dynamic Rankings——有修改区间第K小问题
题目大意
给出一个有$n$个数的数列，执行$m$次操作，操作分两种：
询问在区间$[l,r]$中第$k$小的数
把第$i$个数改为$t$
数据范围
$1\leqslant n,m\leqslant 10000$
题解
每次修改需要我们更新$[i,n]$中$n-i+1$棵权值线段树，每棵都暴力重构会使得时间复杂度退化，怎么办呢？
由于修改和询问都是询问一个区间内权值线段树的信息，则区间修改和区间查询可以用树状数组来维护
具体做法就是在树状数组内建立权值线段树，表示这段区间内权值出现的个数，统计和修改信息只要跑一遍树状数组就好啦！
最后，建立权值线段树基本都是要离散化的，不然就会
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,tot,top,size;
int v[20500],hash[20500],num[20500];
int flag[10500],a[10500],b[10500],k[10500],root[10500];
int sum[2000500],ls[2000500],rs[2000500];
int l[100],r[100],aa,bb;
inline int lowbit(int x){return x&-x;}
inline int find(int x){
int l=1,r=tot;
while (l<=r){
int mid=(l+r)>>1;
if (hash[mid]<x) l=mid+1;
else r=mid-1;
}
return l;
}
inline void init(){
n=read(),m=read();
For(i,1,n) v[i]=read(),num[++top]=v[i];
For(i,1,m){
char s[10];scanf("%s",s+1);
a[i]=read(),b[i]=read();
if (s[1]=='Q') {k[i]=read();flag[i]=1;}
else num[++top]=b[i];
}
sort(num+1,num+top+1);
hash[++tot]=num[1];
For(i,2,top)
if (num[i]!=num[i-1]) hash[++tot]=num[i];
}
void insert(int wl,int wr,int x,int &y,int c,int add){
y=++size;
sum[y]=sum[x]+add;ls[y]=ls[x];rs[y]=rs[x];
if (wl==wr) return;
int mid=(wl+wr)>>1;
if (c<=mid) insert(wl,mid,ls[x],ls[y],c,add);
else insert(mid+1,wr,rs[x],rs[y],c,add);
}
int query(int wl,int wr,int k){
if (wl==wr) return wl;
int suml=0,sumr=0;
For(i,1,aa) suml+=sum[ls[l[i]]];
For(i,1,bb) sumr+=sum[ls[r[i]]];
int mid=(wl+wr)>>1;
if (k<=sumr-suml){
For(i,1,aa) l[i]=ls[l[i]];
For(i,1,bb) r[i]=ls[r[i]];
query(wl,mid,k);
}
else{
For(i,1,aa) l[i]=rs[l[i]];
For(i,1,bb) r[i]=rs[r[i]];
query(mid+1,wr,k-(sumr-suml));
}
}
int main(){
init();
For(i,1,n)
for(int j=i;j<=n;j+=lowbit(j)) insert(1,tot,root[j],root[j],find(v[i]),1);
For(i,1,m){
if (flag[i]==1){
aa=0;bb=0;a[i]--;
for(int j=a[i];j>0;j-=lowbit(j)) l[++aa]=root[j];
for(int j=b[i];j>0;j-=lowbit(j)) r[++bb]=root[j];
printf("%d\n",hash[query(1,tot,k[i])]);
}
else{
for(int j=a[i];j<=n;j+=lowbit(j)) insert(1,tot,root[j],root[j],find(v[a[i]]),-1);
v[a[i]]=b[i];
for(int j=a[i];j<=n;j+=lowbit(j)) insert(1,tot,root[j],root[j],find(b[i]),1);
}
}
}
鄂公网安备 42010202000505 号