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

Mine_King · 2020-08-25 21:00:34 · 题解

我的第一道 Ynoi，来写篇题解祭一下QwQ。

首先这题需要再开一个数组存储每个块排序之后的数组，同时记录在原数组的位置，方便之后二分查找。

那么对于这题的两个操作，首先是查询操作，我们可以二分答案 k，然后然后查询这个区间内小于等于 k 的数。对于二分的左右边界，取 -2e9,2e9 是最保险的，但是效率太低，我们可以直接取整个区间内的最小值和最大值。小优化：若要求的是第 1 小或第块长小的值，可以直接输出左边界 or 右边界。
查询区间内小于等于 k 的数的个数：
对于左右两个碎块，自然是直接枚举即可，而对于整块，我们可以在块内二分，求出这个块里有多少数小于等于 k。然后呢，这里有个小优化，就是如果块内最大值小于等于 k 就直接加上整个块的大小，同理，如果块内最小值大于 k 则直接跳过。这个优化看似平常，但是加了之后 25.06s \rightarrow 13.66s。

然后是修改操作。
对于整块的修改，并不会对相互之间的大小关系产生变化，所以和普通的分块一样打标记即可。而对于碎块，是会对互相之间的大小关系产生变化的，那么我们就要考虑如何维护。如果直接插入的话，效率是最低的，绝对不行。那么我们用归并排序的思想，把整个块分成两部分，分别是更新过的和未更新的。未更新的一定是有序的，而更新过的由于加的是同一个值所以互相之间的大小关系也不会变，也是有序的，就可以直接合并了。

最后就是大家 喜闻乐见 的卡常了，除了上面说的那些小优化，以及快读快输，还有一些就是，块长不一定是 \sqrt{n}，据说这题取 \sqrt{n} \times log_2 n，也可能是常数（比如我取了 1000）。

然后，如果还过不了的话……（加个火车头（小声
code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2")
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,b[200005];
int sq,q[200005],lzy[200005];
struct node
{
    int num,id;
}a[200005];//存排序后的数组
node pp[2005],qq[2005];
bool cmp(node x,node y){return x.num<y.num;}
inline int read()//快读
{
    int x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
inline void write(int x)//快输
{
    if(x<0){x=~(x-1);putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return ;
}
void change(int l,int r,int k)
{
    int lp=0,lq=0;
    for(int i=(q[l]-1)*sq+1;i<=q[l]*sq;i++)//记录全新的值
    {
        if(i>=l&&i<=r) b[i]+=k;
        if(a[i].id>=l&&a[i].id<=r)
            qq[++lq]=(node){a[i].num+k,a[i].id};
        else pp[++lp]=a[i];
    }
    int pi=1,qi=1,t=(q[l]-1)*sq+1;
    while(t<=q[l]*sq)//合并
    {
        if(pi<=lp&&(qi>lq||pp[pi].num<qq[qi].num)) a[t++]=pp[pi],pi++;
        else a[t++]=qq[qi],qi++;
    }
    //左碎块
    if(q[l]!=q[r])
    {
        lp=0,lq=0;
        for(int i=(q[r]-1)*sq+1;i<=q[r]*sq;i++)
        {
            if(i>=l&&i<=r) b[i]+=k;
            if(a[i].id>=l&&a[i].id<=r)
                qq[++lq]=(node){a[i].num+k,a[i].id};
            else pp[++lp]=a[i];
        }
        pi=1,qi=1,t=(q[r]-1)*sq+1;
        while(t<=q[r]*sq)
        {
            if(pi<=lp&&(qi>lq||pp[pi].num<qq[qi].num)) a[t++]=pp[pi],pi++;
            else a[t++]=qq[qi],qi++;
        }
    }
    //右碎块
    for(int i=q[l]+1;i<q[r];i++) lzy[i]+=k;//整块
    return ;
}
int query(int l,int r,int k)
{
    int res=0;
    for(int i=l;i<=min(q[l]*sq,r);i++)
        if(b[i]+lzy[q[l]]<=k) res++;
    //左碎快
    if(q[l]!=q[r])
        for(int i=(q[r]-1)*sq+1;i<=r;i++)
            if(b[i]+lzy[q[r]]<=k) res++;
    //右碎块
    for(int i=q[l]+1;i<q[r];i++)
    {
        int le=(i-1)*sq+1,ri=i*sq;
        if(a[ri].num+lzy[i]<=k)
        {
            res+=ri-le+1;
            continue;
        }
        if(a[le].num+lzy[i]>k) continue;
        //小优化
        while(le<ri)
        {
            int mid=(le+ri)/2+1;
            if(a[mid].num+lzy[i]<=k) le=mid;
            else ri=mid-1;
        }
        if(a[le].num+lzy[i]<=k) res+=le-(i-1)*sq;
    }
    return res;
}
int main()
{
    n=read(),m=read();
    sq=1000;
    for(int i=1;i<=n;i++)
    {
        b[i]=a[i].num=read();
        q[i]=(i-1)/sq+1;
        a[i].id=i;
    }
    for(int i=1;i<=n;)//块内排序
    {
        int j;
        for(j=i;q[j]==q[i];j++);
        sort(a+i,a+j,cmp);
        i=j;
    }
    for(int i=1;i<=m;i++)
    {
        int opt=read(),l=read(),r=read(),k=read();
        if(opt==1)
        {
            int le=2e9,ri=-2e9;
            for(int i=l;i<=min(q[l]*sq,r);i++)
            {
                if(le>b[i]+lzy[q[l]])
                    le=b[i]+lzy[q[l]];
                if(ri<b[i]+lzy[q[l]])
                    ri=b[i]+lzy[q[l]];
            }
            if(q[l]!=q[r])
                for(int i=(q[r]-1)*sq+1;i<=r;i++)
                {
                    if(le>b[i]+lzy[q[r]])
                        le=b[i]+lzy[q[r]];
                    if(ri<b[i]+lzy[q[r]])
                        ri=b[i]+lzy[q[r]];
                }
            for(int i=q[l]+1;i<q[r];i++)
            {
                if(le>a[(i-1)*sq+1].num+lzy[i])
                    le=a[(i-1)*sq+1].num+lzy[i];
                if(ri<a[i*sq].num+lzy[i])
                    ri=a[i*sq].num+lzy[i];
            }
            //求左右边界
            if(k==1)
            {
                write(le);
                puts("");
                continue;
            }
            if(k==ri-le+1)
            {
                write(ri);
                puts("");
                continue;
            }
            //小优化
            int ans=-1;
            while(le<=ri)
            {
                int mid=(le+ri)/2;
                if(query(l,r,mid)<k) le=mid+1;
                else ans=mid,ri=mid-1;
            }
            write(ans);
            puts("");
        }
        else change(l,r,k);
    }
    return 0;
}