1. 题目

传送门= ̄ω ̄=

大意:给你一个数组和一堆询问,询问有三个参数 l,r,k,要你输出数组区间 [l,r] 中排名第 k 的数字是多少

出题人你个傻逼又不说数据组数范围不然分块也能过结果你卡得我线段树不打读入优化都不一定能过,还必须打 inline信不信我切了你的小鸡鸡╭(╯^╰)╮

2. 题解

首先简单讲下分块的写法吧

先分块,再对每个块排序,最后二分答案,对于每个枚举出的答案,在块内二分、块外暴力,算出它的排名,最后就可以确定答案了。

代码长这样(Warning: 会 TLE!):

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>void IN(_Tp&dig)
{
    char c=getchar();dig=0;int f=1;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')f=-1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    dig*=f; 
}
int t,n,q,sqn,arr[101000],d[101000],bi[101000],minl,maxl;
inline int read()
{
    bool minus=0;int dig=0;char c=getchar();
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')minus=1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    return minus?-dig:dig;
}
inline int getpos(int l,int r,int k)
{
    int pos=0,lim=min(bi[l]*sqn,r);
    for(int i=l;i<=lim;i++)if(arr[i]<k)++pos;
    if(bi[l]!=bi[r])for(int i=(bi[r]-1)*sqn+1;i<=r;i++)if(arr[i]<k)++pos;
    for(int i=bi[l]+1;i<bi[r];i++)
        pos+=(int)(lower_bound(d+(i-1)*sqn+1,d+i*sqn+1,k)-(d+(i-1)*sqn+1));
    return pos;
}
inline void getans(int l,int r,int k)
{
    int a=minl,b=maxl,m;
    while(a!=b)
    {
        m=(a+b)>>1;
        if(getpos(l,r,m)<k)a=m+1;else b=m;
    }
    printf("%d\n",a-1);
}
int main()
{
    IN(t);
    while(minl=INT_MAX,maxl=INT_MIN,t-->0)
    {
        IN(n),IN(q),sqn=sqrt(n);
        for(int i=1;i<=n;i++)
            IN(arr[i]),d[i]=arr[i],
            maxl=max(maxl,arr[i]),minl=min(minl,arr[i]),bi[i]=(i-1)/sqn+1;
        minl--,maxl++;
        for(int i=1;i<=bi[n];i++)sort(d+1+(i-1)*sqn,d+1+min(n,i*sqn));
        for(int i=1,l,r,k;i<=q;i++)IN(l),IN(r),IN(k),getans(l,r,k);
    }
    return 0;
}

上面那个理论上没错,只是会 TLE

所以我们必须打线段树。

线段树嘛,维护区间。每个节点都会对应着一个区间,那我们就让每个节点里有一个数组,这个数组就是它对应的区间排序后的样子。然后我们二分答案以后检测答案是否合法,就直接找到区间对应的节点们,在节点的数组里二分找到当前答案在这个区间里排第几,最后加在一起就是它的排名了。

区间排序就在建树时用归并排序搞掉了。

至于每个节点要对应一个数组,直接用 int 的话空间太大,$N^2$的空间复杂度,无法接受。而开 vector 又太慢了。所以就搞个 “公共储存池”(其实是我瞎 YY 出的名字,就是个公共数组而已),每个节点记录在这个公共数组里它所占用的数组左端点编号,数组右端点编号。这样空间复杂度是 $NlogN$的。

这样每次查询是 $log^3 N$的。最后复杂度就是 $Mlog^3 N$的,总共复杂度就是 $TMlog^3 N$的。

代码:

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();dig=0;int f=1;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')f=-1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    dig*=f; 
}
struct N{int l,r,a,b;}e[400005];
int t,n,m,lim1,lim2,d[2000005],dtop;
inline void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r,e[a].a=dtop,e[a].b=dtop+r-l,dtop+=r-l+1;
    if(l==r)
    {
        IN(d[e[a].a]),lim1=min(lim1,d[e[a].a]),lim2=max(lim2,d[e[a].a]);
        return;
    }
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a));
    int i=e[LS(a)].a,j=e[RS(a)].a,k=e[a].a;
    while(i<=e[LS(a)].b||j<=e[RS(a)].b)
    {
        if(i>e[LS(a)].b)d[k++]=d[j++];
        else if(j>e[RS(a)].b)d[k++]=d[i++];
        else if(d[i]<d[j])d[k++]=d[i++];
        else d[k++]=d[j++]; 
    }
}
inline int query(int l,int r,int k,int a)
{
    if(l<=e[a].l&&e[a].r<=r)
        return (int)(lower_bound(d+e[a].a,d+e[a].b+1,k)-(d+e[a].a));
    int tot=0;
    if(l<=((e[a].l+e[a].r)>>1))tot+=query(l,r,k,LS(a));
    if(r>((e[a].l+e[a].r)>>1))tot+=query(l,r,k,RS(a));
    return tot;
} 
inline int work(int a,int b,int k)
{
    int l=lim1,r=lim2,m;
    while(l!=r)
    {
        m=(l+r+1)>>1;
        int tmp=query(a,b,m,1);
        if(tmp<k)l=m;else r=m-1;
    }
    return l;
}
int main()
{
    IN(t);
    while(lim1=INT_MAX,lim2=INT_MIN,dtop=0,t--)
    {
        IN(n),IN(m),build(1,n,1);
        for(int i=1,a,b,k;i<=m;i++)IN(a),IN(b),IN(k),printf("%d\n",work(a,b,k));
    }
    return 0;
} 
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

6 条评论

boshi · 2017年7月2日 2:29 下午

为什么不是 TMlog2n 啊?这里不是二分一下再查询一下马?

    konnyakuxzy · 2017年7月2日 7:29 下午

    哦,打错了。
    谢谢 dalao~

    konnyakuxzy · 2018年2月5日 9:43 下午

    QvQ 突然发现这条回复
    重新补充一下啊,经过仔细研究,,,这里这个算法复杂度是 $O(TMlog_2^3N)$的

boshi · 2017年7月2日 2:25 下午

inline+register=-1s

【题解】 Dynamic Rankings 动态区间第k小问题 二分答案+树套树(线段树套splay) BZOJ – 1901 | K-XZY · 2018年1月4日 3:59 下午

[…] 二分答案套线段树:传送门= ̄ω ̄= […]

【题解】 K-th Number 主席树 POJ – 2104 | K-XZY · 2018年1月4日 1:29 下午

[…] 以前写过一个二分套线段树的题解:传送门= ̄ω ̄=(题目一样,就是那个有多组数据这个没有)[…]

回复 boshi 取消回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注