题解 P5356 【[Ynoi2017]由乃打扑克】

· · 题解

前言

UPD by 2020.11.30，找到了更优的解法

旧题解已转移至这里

一年前，我写这道题时弄出了一个“缩减二分长度”的优化

这项剪枝表现出了优异的效果，我没加什么优化就过了这题甚至没加快读

然后写了篇题解，通俗易懂，码风清新，备受好评

但是现在看来那篇题解写得太烂了，表述不严谨且仍有优化空间，于是我决定重新投一份(配合旧题解食用更佳)

正片

一些变量/预处理

分块算法，首先我们要给块内排序，这里我们不使用结构体(可以减小常数且代码更美观)

int a[N],lazy[N/block+5];//原数组，整体加标记 
int p[N];bool cmp(int x,int y){return a[x]<a[y];}//排序数组 
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    B=(n-1)/block+1;
    for(int i=1;i<=B;i++)
    {
        bl[i]=br[i-1]+1;
        br[i]=br[i-1]+block;
    }br[B]=n;//分块基本操作 
    for(int i=1;i<=B;i++)
    {
        for(int j=bl[i];j<=br[i];j++)w[p[j]=j]=i;
        sort(p+bl[i],p+br[i]+1,cmp);
    }//对于一个块内的p数组，其对应的a数组是从小到大的 
    /*
    ......
    */
    return 0;
}

可以看到，p数组 反映了 a数组 的大小关系

修改

大段打 lazy标记，小段暴力修改 a数组，然后用归并排序的思想来维护 p数组

小段里面有两类数，一部分是不需要修改的数，另一部分则需要 +k

我们知道 p数组 存的是一堆下标，对应到 a数组 是排好序的

于是我们只要把 p数组 按上述规则划分开来，然后来个简单的归并即可维护

int c1[N],t1;
int c2[N],t2;//tmp数组 
void msort(int L,int R,int l,int r,int k)
{//块左端，块右端，区间加范围 
    t1=t2=0;//搞完以后c里面是一堆下标，对应a数组是从小到大的 
    for(int i=L;i<=R;i++)(l<=p[i]&&p[i]<=r)?a[c1[++t1]=p[i]]+=k:c2[++t2]=p[i];
    while(t1&&t2)p[R--]=(a[c1[t1]]>a[c2[t2]])?c1[t1--]:c2[t2--];//从大到小丢进去 
    while(t1)p[R--]=c1[t1--];
    while(t2)p[R--]=c2[t2--];//归并排序基本操作 
}

查询（重点）

二分答案，设二分值域为L和R，每次枚举mid

然后查询区间内 小于等于mid 的数 的个数 (记为s)

若 s<k，则 mid 显然不为答案，令L=mid+1

若 s>=k，则令 ans=mid ，R=mid-1

如何得知区间内 小于等于mid 的数 的个数 呢？

再套一个二分就行，正常思路是小段暴力，大段用 p数组 二分

（优化1）

后来我发现，哎，为什么小段要暴力呢？

其实我们可以再弄一个 c数组，把小段像修改操作那样归并一下

然后我们就可以“在小段上二分了”

我原来的题解里是没有这个优化的，两端都是暴力统计（我太菜了）

当我想起来时，然后去看别人的题解，发现他们都加了。。。

（优化2）

预先确定二分的值域范围，不要直接L=-2147483648，R=2147483647

因为题目的数据有一句“每次加上的数和原序列的数在[-2 \times 10^4 , 2 \times 10^4]内”

（优化3）

这也是我在旧题解里面提出的一个大优化

假设我们某次枚举了一个mid，然后其中有一个块 [l,r]，我们得出 [l,pos] 这些东西 小于等于mid

这一轮的 mid 枚举结束后

若 s<k ，则说明 mid 比正确答案小了，那么以后我们枚举的MID就比这个mid大

那么对于上述的块 [l,r]，我们以后得出的位置一定大于等于pos

我们便可以把左端点拉过来，减少块内二分位置的区域

若 s>=k ，那么以后我们枚举的MID就比这个mid小

那么对于上述的块 [l,r]，我们以后得出的位置一定小于等于pos

我们便可以把右端点拉过来，减少块内二分位置的区域

在随机数据下，这个优化快到离谱，但是也不是不能卡掉，hack数据很简单，然后可以把我的代码卡到10s

以下为hack数据生成代码

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<random>
using namespace std;
mt19937 rnd;
int random(int x){return (rnd()%x+x)%x;}//[0,x-1]
int main()
{
    freopen("1.in","w",stdout);
    rnd.seed(time(0));
    int n=100000,m=100000;printf("%d %d\n0",n,m);
    for(int i=2;i<=n;i++)printf(" 20000");
    puts("");
    for(int i=1;i<=50000;i++)puts("2 2 100000 20000");
    for(int i=50001;i<=100000;i++)puts("1 1 100000 100000");
    return 0;
}

不过很抱歉，这玩意是可以处理的

因为“每次加上的数和原序列的数在[-2 \times 10^4 , 2 \times 10^4]内”

这样会导致部分区间的值域范围大小很小

我们只要在块内二分前先判断一下，是否整个块都比mid大/小 (优化4)

这样可以使得 优化3 变快不少，其他题解也提到了这个，不过lxl的数据很水，随便使用几个优化即可AC

复杂度

空间复杂度O(N)是跑不掉的

我的代码时间复杂度随机情况下是O(N\sqrt{NΔ})，最坏是O(N\sqrt{N}Δ)，其中Δ是二分次数，你大概可以看成20到30

这里的最优复杂度块长取(\sqrt{NΔ})，最坏复杂度块长取(\sqrt{N}Δ)

也就是说数据越随机，块长我就取得越小，代码就能跑得更快，但是数据毒瘤一点的话复杂度就会退化

至此，我们得出了一个空间复杂度为O(N)，时间复杂度是O(N\sqrt{N}Δ)的在线做法，但是因为剪枝多，跑得非常快，测了一下上面的hack数据，没加读入输出优化（只有O2）跑了2秒

但这个代码可以卡掉，经过与大佬的讨论，我们只需构造出多个相似的段，比如说\sqrt{N}个块长得一模一样而且里面1到\sqrt{N}每个数都出现一次，当然这种数据不常见，但是我们这是学术研究，不能随便口糊过去

于是这种做法就宣告失败了，但是这道题还是能过的

关于本题数据

lxl的数据水到什么程度呢？

如果你把上面的数据生成器弄出来的数据给目前所有题解测一下，你会发现都过不了（截至2020.11.30），TLE也就算了（最快的大概跑到5秒），但是有几个题解是WA？

然后看了下WA掉的题解，发现他们二分答案的初始范围是错的(会爆int)

下面给出我的代码（抄就抄吧，抄不走我对分块的热情）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
const int block=700;
int B,bl[N/block+5],br[N/block+5],w[N];//左，右，从属块 

int a[N],lazy[N/block+5];//原数组，整体加标记 
int p[N];bool cmp(int x,int y){return a[x]<a[y];}//排序数组 

int c1[N],t1;
int c2[N],t2;//tmp数组 
void msort(int L,int R,int l,int r,int k)
{//块左端，块右端，区间加范围 
    t1=t2=0;//搞完以后c里面是一堆下标，对应a数组是从小到大的 
    for(int i=L;i<=R;i++)(l<=p[i]&&p[i]<=r)?a[c1[++t1]=p[i]]+=k:c2[++t2]=p[i];
    while(t1&&t2)p[R--]=(a[c1[t1]]>a[c2[t2]])?c1[t1--]:c2[t2--];//从大到小丢进去 
    while(t1)p[R--]=c1[t1--];
    while(t2)p[R--]=c2[t2--];//归并排序基本操作 
}

int c[N],t;

int asl[N/block+5],asr[N/block+5],as[N/block+5];

int main()
{
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    B=(n-1)/block+1;
    for(int i=1;i<=B;i++)
    {
        bl[i]=br[i-1]+1;
        br[i]=br[i-1]+block;
    }br[B]=n;//分块基本操作 
    for(int i=1;i<=B;i++)
    {
        for(int j=bl[i];j<=br[i];j++)w[p[j]=j]=i;
        sort(p+bl[i],p+br[i]+1,cmp);
    }//对于一个块内的p数组，其对应的a数组是从小到大的 

    while(m--)
    {
        int cz,l,r,k;scanf("%d%d%d%d",&cz,&l,&r,&k);
        int ql=w[l],qr=w[r];
        if(cz==1)//查询 
        {
            if(k>r-l+1){puts("-1");continue;}
            if(ql==qr)
            {
                for(int i=bl[ql],j=0;i<=br[ql];i++)
                {
                    if(l<=p[i]&&p[i]<=r&&++j==k)
                    {
                        printf("%d\n",a[p[i]]+lazy[ql]);break;
                    }//不要漏掉lazy标记... 
                }
            }
            else
            {
                t1=t2=t=0;//把小段取出来归并，不过要注意此时c数组的处理方式和修改操作不一样 
                for(int i=br[ql];i>=bl[ql];i--)if(l<=p[i])c1[++t1]=a[p[i]]+lazy[ql];//左边 
                for(int i=br[qr];i>=bl[qr];i--)if(p[i]<=r)c2[++t2]=a[p[i]]+lazy[qr];//右边 
                while(t1&&t2)c[++t]=(c1[t1]<c2[t2])?c1[t1--]:c2[t2--];//从小到大丢进去 
                while(t1)c[++t]=c1[t1--];
                while(t2)c[++t]=c2[t2--];

                if(ql+1==qr){printf("%d\n",c[k]);continue;}

                //然后的情况是从c数组和很多个大段里面找第k小，注意此时c数组是确定的值，且无需lazy标记 
                int L=c[1],R=c[t],ans;
                for(int i=ql+1;i<qr;i++)
                {
                    L=min(L,a[p[bl[i]]]+lazy[i]);
                    R=max(R,a[p[br[i]]]+lazy[i]);
                    as[i]=asl[i]=bl[i]-1;asr[i]=br[i]+1;
                }as[0]=asl[0]=0;asr[0]=t+1;//找到最值以及预处理，这个下标0是给c数组用的 
                while(L<=R)//二分开始！ 
                {
                    int mid=(L+R)/2,s=0,fucl,fucr,fucmid;//mid为二分值，s为比mid小或者等于mid的个数 
                    fucl=asl[0]+1;fucr=asr[0]-1;
                    if(fucl<=fucr)
                    {
                        if(c[fucr]<=mid){as[0]=fucr;fucl=fucr+1;}//优化 
                        else if(c[fucl]>mid)fucr=fucl-1;
                        while(fucl<=fucr)
                        {
                            fucmid=(fucl+fucr)/2;
                            if(c[fucmid]<=mid){as[0]=fucmid;fucl=fucmid+1;}
                            else fucr=fucmid-1;
                        }
                    }
                    s+=as[0];
                    if(s<k)
                    {
                        for(int i=ql+1;i<qr;i++)
                        {
                            fucl=asl[i]+1;fucr=asr[i]-1;//asl和asr是不可以踩到的地方 
                            if(fucl<=fucr)
                            {
                                if(a[p[fucr]]+lazy[i]<=mid){as[i]=fucr;fucl=fucr+1;}//优化 
                                else if(a[p[fucl]]+lazy[i]>mid)fucr=fucl-1;
                                while(fucl<=fucr)//合法范围 
                                {
                                    fucmid=(fucl+fucr)/2;
                                    if(a[p[fucmid]]+lazy[i]<=mid){as[i]=fucmid;fucl=fucmid+1;}//bl[i]~fucmid都小于等于mid 
                                    else fucr=fucmid-1;
                                }
                            }
                            s+=as[i]-bl[i]+1;
                            if(s>=k)//你s都大于等于k了说明什么，ans必能更新啊，还二分个锤子 
                            {//mid的排名一定>=s，当s>=k时，mid>=k，此时可以更新答案ans 
                                while(i>ql){asr[i]=as[i]+1;as[i]=asl[i];i--;}
                                break;
                            }
                        }
                    }
                    if(s>=k)
                    {
                        asr[0]=as[0]+1;as[0]=asl[0];
                        ans=mid;R=mid-1;//ans只会越来越小 
                    }
                    else
                    {
                        L=mid+1;asl[0]=as[0];
                        for(int i=ql+1;i<qr;i++)asl[i]=as[i];
                    }
                }
                printf("%d\n",ans);
            }
        }
        else //修改 
        {
            if(ql==qr)msort(bl[ql],br[ql],l,r,k);//使用归并思想处理小块 
            else
            {
                msort(bl[ql],br[ql],l,br[ql],k);
                msort(bl[qr],br[qr],bl[qr],r,k);
                for(int i=ql+1;i<qr;i++)lazy[i]+=k;//打标记 
            }
        }
    }
    return 0;
}

难道你觉得这份题解已经结束了吗？

并不，这题还剩一个条件没有用过，就是“离线”

有的人可能会问了，区间加还能离线？

那你可以康康这题（话说这题怎么时限变750ms了）

在某个奇妙的冬夜，我裹着被子翻来覆去，然后脑子里冒出了一个idea...

还记得我们二分答案后要求什么吗？区间有多少数小于等于mid

现在来这么一道经典题目，有两种操作

1.$区间加 $k 其实这题是可以$O(N\sqrt{N})$离线做的（块长取$\sqrt{N}$），套用P4118的思想即可 那么我们只要应用这项黑科技，就可以直接大力二分答案 然后复杂度是$O(N\sqrt{N}Δ)$的，这种做法似乎和众多题解的复杂度相当 但是这里又能优化，就很离谱 ## 以下内容不难，但是涉及上面的思想，而且我不会过于详细地解释 设块长为$B$，我们有$N$个小段修改，$\frac{N^2}{B}$个大段询问， 因为二分答案的缘故，我们要搞$Δ$次，每次重构会浪费很多复杂度 我们对比二分操作中询问的两个不同的$mid$，然后发现修改操作完全一致 于是我们可以先预处理出小段修改后的序列，这样可以将复杂度从$O(NΔ(B+\frac{N}{B}))$变成$O(N(B+Δ\frac{N}{B}))$， 然后块长取$(\sqrt{NΔ})$，复杂度似乎就是$O(N\sqrt{NΔ})

但是这里有个小瑕疵，就是块长比块的数量大一些

每一个大段的询问均摊不是O(1)的，最终我们选取块长略大于(\sqrt{NΔ})

复杂度也许是O(N\sqrt{NkΔ})，其中 k 近似于 loglogN 级别

上面这部分本来是口糊的

但与大佬交流了一下，他说这样做还真的可以O(N\sqrt{NkΔ})

于是我们的新做法：时空复杂度都略大于O(N\sqrt{NΔ})，但是肯定比O(N\sqrt{N}Δ)小不少

虽然不及神仙的O(N\sqrt{NlogN})做法，但是这也不失为一种优秀的做法

结语

跟大佬交流，虽然看起来被D飞了，但是学到的真的不少

如果还有什么好的意见，欢迎提出