UOJ Logo zgjkt的博客

博客

各种区间第K小问题

2015-11-16 13:23:03 By zgjkt

【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$次操作，操作分两种：

  1. 询问在区间$[l,r]$中第$k$小的数

  2. 把第$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);
        }
    }
}

在最后感谢$miskcoo$的一篇博文对我的启发

完结撒花！！！

评论

VivianWhite
orz 谢谢谢谢

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-04-26 10:56:38