旧题解由乃打扑克

2018heyuyang · 2020-11-30 14:41:02 · 个人记录

这题不用卡常的……

lxl数据水了……

只要学会几个剪枝即可 (并不是搜索)

预处理

我们弄个简单的分块，对块排序，得到原数组和一个排序的数组

排序数组为一个结构体，另一个元素记录原位置

预处理复杂度O(\frac{N}{B}\times BlogB)=O(NlogB)

查询时二分答案，每次求出段内有几个数小于等于这个答案 (mid)

如果个数不足k，那么答案>mid

否则答案<=mid

然后暴力统计两端的数量

中间的大段就在排好序的数组里二分求一下

此时我们的复杂度是O(M\times\frac{N}{B}\times logB\times log(int))

修改

修改操作，中间大段打lazy标记

两边小段的原数组暴力修改，再去考虑排序数组

因为排序数组有序

所以我们把排序数组拆为两部分

一部分是这次修改没覆盖到的数，这一部分在排序数组里是有序的

另一部分是要加的，我们给他们加上k，然后还是有序的

关于TLE

显然我们的复杂度都在查询操作里

或许你可以玄学调块长，再砸 fread 什么的优化可以卡过去

我们还是从本质上优化代码会更好

首先快长调到大于\sqrt N一点点，然后开始剪枝吧

二分答案的左右端点分别取区间最小值和区间最大值

直接在排序数组里取最小的和最大的就行

两边的小段都一样的，反正能剪掉二分答案次数就对了

（剪枝1）

审视我们二分答案之后的操作

小段就不说了，这不是复杂度的瓶颈

大段：二分位置，记录小于等于mid的数的位置，sum+=块的左端点到 p 的数的个数

然后判断 sum 和 k 的大小关系

那么以后在块内二分的最终位置一定>=p

把左端点拉过来，减少块内二分位置的区域

那么以后在块内二分的最终位置一定<=p

把右端点拉过来，减少块内二分位置的区域

（剪枝2）

使用如上两个剪枝可以AC

复杂度也许是O(M\times\sqrt N\times log(int))

反正时间是O(玄学)就对了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
const int block=400;
int B,bl[N/block+5],br[N/block+5],w[N],lazy[N/block+5];
int a[N],t1,t2,t3;
struct node
{
    int z,p;
}b[N],c1[N],c2[N];bool cmp(node n1,node n2){return n1.z<n2.z;}
int asl[N/block+5],asr[N/block+5],as[N/block+5];
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[j]=i;b[b[j].p=j].z=a[j];}
        sort(b+bl[i],b+br[i]+1,cmp);
    }
    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;}
            int L=-2000000000,R=2000000000,ans=0;
            for(int i=ql;i<=qr;i++)
            {
                L=min(L,b[bl[i]].z+lazy[i]);
                R=max(R,b[br[i]].z+lazy[i]);
                asl[i]=bl[i];asr[i]=br[i];as[i]=bl[i]-1;
            }
            while(L<=R)
            {
                int mid=(L+R)/2,s=0;
                if(ql==qr)
                {
                    for(int i=l;i<=r;i++)if(a[i]+lazy[ql]<=mid)s++;
                }
                else
                {
                    for(int i=l;i<=br[ql];i++)if(a[i]+lazy[ql]<=mid)s++;
                    for(int i=bl[qr];i<=r;i++)if(a[i]+lazy[qr]<=mid)s++;
                    for(int i=ql+1;i<qr;i++)
                    {
                        int fucl=asl[i],fucr=asr[i];as[i]=bl[i]-1;
                        while(fucl<=fucr)
                        {
                            int fucmid=fucl+fucr>>1;
                            if(b[fucmid].z+lazy[i]<=mid){as[i]=fucmid;fucl=fucmid+1;}
                            else fucr=fucmid-1;
                        }
                        s+=as[i]-bl[i]+1;
                    }
                }
                if(s>=k)
                {
                    ans=mid;R=mid-1;
                    for(int i=ql+1;i<qr;i++)asr[i]=as[i];
                }
                else
                {
                    L=mid+1;
                    for(int i=ql+1;i<qr;i++)asl[i]=max(as[i],bl[i]);
                }
            }
            printf("%d\n",ans);
        }
        else
        {
            if(ql==qr)
            {
                for(int i=l;i<=r;i++)a[i]+=k;
                t1=t2=0;t3=br[ql];
                for(int j=bl[ql];j<=br[ql];j++)
                {
                    if(l<=b[j].p&&b[j].p<=r){b[j].z+=k;c1[++t1]=b[j];}
                    else c2[++t2]=b[j];
                }
                while(t1&&t2)
                {
                    if(c1[t1].z>c2[t2].z)b[t3--]=c1[t1--];
                    else b[t3--]=c2[t2--];
                }
                while(t1)b[t3--]=c1[t1--];
                while(t2)b[t3--]=c2[t2--];
            }
            else
            {
                for(int i=l;i<=br[ql];i++)a[i]+=k;
                t1=t2=0;t3=br[ql];
                for(int j=bl[ql];j<=br[ql];j++)
                {
                    if(l<=b[j].p&&b[j].p<=br[ql]){b[j].z+=k;c1[++t1]=b[j];}
                    else c2[++t2]=b[j];
                }
                while(t1&&t2)
                {
                    if(c1[t1].z>c2[t2].z)b[t3--]=c1[t1--];
                    else b[t3--]=c2[t2--];
                }
                while(t1)b[t3--]=c1[t1--];
                while(t2)b[t3--]=c2[t2--];

                for(int i=bl[qr];i<=r;i++)a[i]+=k;
                t1=t2=0;t3=br[qr];
                for(int j=bl[qr];j<=br[qr];j++)
                {
                    if(bl[qr]<=b[j].p&&b[j].p<=r){b[j].z+=k;c1[++t1]=b[j];}
                    else c2[++t2]=b[j];
                }
                while(t1&&t2)
                {
                    if(c1[t1].z>c2[t2].z)b[t3--]=c1[t1--];
                    else b[t3--]=c2[t2--];
                }
                while(t1)b[t3--]=c1[t1--];
                while(t2)b[t3--]=c2[t2--];

                for(int i=ql+1;i<qr;i++)lazy[i]+=k;
            }
        }
    }
    return 0;
}