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 下午

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

发表评论

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

你是机器人吗? =。= *