题解 P5356 [Ynoi2017] 由乃打扑克

gxy001 · 2021-02-06 15:15:26 · 题解

UPD2: 实际上，只要把 \frac 13 换成更小的数平衡常数就能通过此题，现在的代码已更换可以通过的选择的数为 \frac 1{10}。

UPD: 在大佬 @DPair 的卡常帮助下，这个算法可以通过本题，提交记录。

本篇题解将会给出 \mathrm O(n\sqrt{n\log n}) 的做法和参考实现，不过我的实现不够精细，被卡常了。

我们发现原做法的复杂度瓶颈在查询时的多序列二分，考虑用分散层叠优化，不会分散层叠的可以先看这题。

因为带修，所以我们要换一种合并方式，考虑线段树，每个叶子节点存放一块序列，非叶节点合并子节点序列各 \frac{1}{3}，这样修改时重构的复杂度为 \mathrm O(B+\frac{2}{3}B+\frac{4}{9}B+...)=O(B)。

查询时遍历整颗线段树就行。B 取 O(\sqrt{n\log n}) 最优。

具体的看代码就行了：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
namespace IO{
    #define BUFSIZE 10000000
    struct read{
        char buf[BUFSIZE],*p1,*p2,c,f;
        read():p1(buf),p2(buf){}
        inline char gc(void){
            return p1==p2&&(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++;
        }
        inline read& operator >>(int& x){
            for(c=gc(),f=0,x=0;c!=EOF&&(c<'0'||c>'9');c=gc())if(c=='-')f=1;
            if(f)for(;c>='0'&&c<='9';c=gc())x=x*10-(c-'0');
            else for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
            return *this;
        }
    }in;
    struct write{
        char buf[BUFSIZE],*p1,*p2,s[50],f;
        int tp;
        write():p1(buf){}
        ~write(){fwrite(buf,1,p1-buf,stdout);}
        inline write& operator <<(int x){
            if(x<0)f=1,*p1++='-';else f=0;
            if(f)do{s[tp++]=-x%10+'0',x/=10;}while(x);
            else do{s[tp++]=x%10+'0',x/=10;}while(x);
            while(tp)*p1++=s[--tp];
            return *this;
        }
        inline write& operator <<(char const &x){
            *p1++=x;
            return *this;
        }
    }out;
}
using IO::in;
using IO::out;
int n,m,a[100010],B,bel[100010],bcnt,L[510],R[510];
struct node{
    int v,nxt1,nxt2;
    node():v(),nxt1(),nxt2(){}
    node(int const &x):v(x),nxt1(),nxt2(){}
    node(int const &x,int const &i):v(x),nxt1(i),nxt2(){}
    bool operator <(node const &x)const{return v<x.v;} 
}pool[300010],*it=pool,*tr[2010];
int tag[2010],sz[2010];
inline void build(int x=1,int l=1,int r=bcnt){
    if(l==r){
        tr[x]=it;
        for(int i=L[l];i<=R[l];i++)it[i-L[l]]=node(a[i],i);
        sz[x]=R[l]-L[l]+2;
        it+=sz[x]-1;
        *it++=node(0x7fffffff);
        std::sort(tr[x],it);
        return;
    }
    int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    static node tmp1[10010],tmp2[10010];
    node *it1=tmp1,*it2=tmp2;
    for(int i=0;i<sz[ls]-1;i+=10)*it1++=tr[ls][i].v;
    for(int i=0;i<sz[rs]-1;i+=10)*it2++=tr[rs][i].v;
    std::merge(tmp1,it1,tmp2,it2,tr[x]=it);
    int &len=sz[x]=it1-tmp1+it2-tmp2+1;
    it+=len-1;
    *it++=node(0x7fffffff);
    int i=0,j=0;
    while(i<len&&j<sz[ls])if(tr[x][i].v<=tr[ls][j].v) tr[x][i++].nxt1=j;else j++;
    i=0,j=0;
    while(i<len&&j<sz[rs])if(tr[x][i].v<=tr[rs][j].v) tr[x][i++].nxt2=j;else j++;
}
inline void update(int pl,int pr,int k,int x=1,int l=1,int r=bcnt){
    if(pl==L[l]&&pr==R[r]) return tag[x]+=k,void();
    static node tmp1[10010],tmp2[10010];
    node *it1=tmp1,*it2=tmp2;
    if(l==r){
        for(int i=0;i<sz[x]-1;i++)
            if(tr[x][i].nxt1<=pr&&tr[x][i].nxt1>=pl)*it1++=node(tr[x][i].v+k,tr[x][i].nxt1);
            else *it2++=node(tr[x][i].v,tr[x][i].nxt1);
        *it2++=node(0x7fffffff);
        std::merge(tmp1,it1,tmp2,it2,tr[x]);
        return;
    }
    int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
    if(pr<=R[mid]) update(pl,pr,k,ls,l,mid);
    else if(pl>R[mid]) update(pl,pr,k,rs,mid+1,r);
    else update(pl,R[mid],k,ls,l,mid),update(R[mid]+1,pr,k,rs,mid+1,r);
    for(int i=0;i<sz[ls]-1;i+=10)*it1++=tr[ls][i].v+tag[ls];
    for(int i=0;i<sz[rs]-1;i+=10)*it2++=tr[rs][i].v+tag[rs];
    *it2++=node(0x7fffffff);
    std::merge(tmp1,it1,tmp2,it2,tr[x]);
    int &len=sz[x];
    int i=0,j=0;
    while(i<len&&j<sz[ls]-1)if(tr[x][i].v<=tr[ls][j].v+tag[ls]) tr[x][i++].nxt1=j;else j++;
    while(i<len)tr[x][i++].nxt1=sz[ls]-1;
    i=0,j=0;
    while(i<len&&j<sz[rs]-1)if(tr[x][i].v<=tr[rs][j].v+tag[rs]) tr[x][i++].nxt2=j;else j++;
    while(i<len)tr[x][i++].nxt2=sz[rs]-1;
}
int d1[10010],d2[10010],d[20010];
int *c1;
inline void collect(int pl,int pr,int v=0,int x=1,int l=1,int r=bcnt){
    if(l==r){
        for(int i=0;i<sz[x];i++)
            if(tr[x][i].nxt1<=pr&&tr[x][i].nxt1>=pl) *c1++=tr[x][i].v+v+tag[x];
        return;
    }
    int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
    if(pr<=R[mid]) collect(pl,pr,v+tag[x],ls,l,mid);
    else collect(pl,pr,v+tag[x],rs,mid+1,r);
}
inline int query(int pl,int pr,int v,int k,int x=1,int l=1,int r=bcnt){
    while(k&&tr[x][k-1].v>v-tag[x])--k;
    if(l==r) return k;
    int ls=x<<1,rs=x<<1|1,mid=(l+r)>>1;
    if(pr<=mid) return query(pl,pr,v-tag[x],tr[x][k].nxt1,ls,l,mid);
    if(pl>mid) return query(pl,pr,v-tag[x],tr[x][k].nxt2,rs,mid+1,r);
    return query(pl,mid,v-tag[x],tr[x][k].nxt1,ls,l,mid)+query(mid+1,pr,v-tag[x],tr[x][k].nxt2,rs,mid+1,r); 
}
inline int getans(int pl,int pr,int k){
    if(pl>pr) return 0;
    return query(pl,pr,k,std::upper_bound(tr[1],tr[1]+sz[1],node(k))-tr[1]);
}
int main(){
    in>>n>>m;
    B=sqrt(n*log2(n));if(!B)B=1;
    for(int i=1;i<=n;i++)in>>a[i],bel[i]=(i-1)/B+1;
    for(int i=1;i<=n;i++)R[bel[i]]=i;
    for(int i=n;i;i--)L[bel[i]]=i;
    bcnt=bel[n];
    build();
    while(m--){
        int op,l,r,k;
        in>>op>>l>>r>>k;
        if(op==1){
            if(r-l+1<k)out<<-1;
            else{
                int x=0x8000000f,y=-x,ans=0,mid;
                if(bel[l]==bel[r]){
                    c1=d,collect(l,r);
                    while(x<=y){ 
                        mid=(1ll*x+y)>>1;
                        if(std::upper_bound(d,c1,mid)-d>=k)ans=mid,y=mid-1;
                        else x=mid+1;
                    }
                }else{
                    c1=d1,collect(l,R[bel[l]]);
                    c1=d2,collect(L[bel[r]],r);
                    std::merge(d1,d1+R[bel[l]]-l+1,d2,d2+r-L[bel[r]]+1,d);
                    c1=d+R[bel[l]]-l+1+r-L[bel[r]]+1;
                    while(x<=y){
                        mid=(1ll*x+y)>>1;
                        if(std::upper_bound(d,c1,mid)-d+getans(bel[l]+1,bel[r]-1,mid)>=k)ans=mid,y=mid-1;
                        else x=mid+1;
                    }
                }
                out<<ans<<'\n';
            }
        }else update(l,r,k);
    }
    return 0;
}