【Ynoi2017】由乃打扑克

· · 题解

推销博客

YNOI。

首先我不会O(nsqrt(n))的做法，我这边还是带一个log的。

明显这道题应该无法达到log的这种级别，考虑简单的数列分块。

考虑每一块大小为lim，然后在块内排个二元组(a_i,i)的序，这样预处理的复杂度是O(\frac{n}{lim}\ast lim\ast log(lim))，即O(nlog(lim))。

首先是修改操作。整块的可以直接维护一个标记，不是整块的可以将其分成两个块，这样分出的两块还是有序的，于是对于那个要修改的块暴力修改掉，再把两块归并起来。这样的复杂度是O(\frac {n}{lim} +lim+lim)的。

然后是查询操作。同样的想法，不完整的块直接分成两个块，然后考虑二分答案，每个块里（包括分出来的块）内再二分查找个数就可以了。这样的复杂度应该是O(\frac {n}{lim} log^2(n))。

所以总的复杂度是O(\sum (\frac {n}{lim}+lim+\frac{n}{lim}log^2(n)))，lim取sqrt(n)log(n)时最优。

Update：之前那份代码没读入负数不知道为什么也能过，好奇怪啊

code:

//2019.5.22 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-10
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
//#define gc getchar
inline char gc() {
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
    res s=0,ch=gc(),w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s*w;
}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc();
//    while(ch<'0'||ch>'9')ch=gc();
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s;
//}
//inline void swap(res &x,res &y) {
//    x^=y^=x^=y;
//}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e5+10;
namespace MAIN {
    int K,n,m,sum,block,L[N],R[N],tag[N];
    Pair a[N<<1],A[N],B[N];
    inline int query(const res &I,res val){
        res l=L[I],r=R[I],ret=l-1;
        val-=tag[I];
        while(l<=r){
            res mid=(l+r)>>1;
            if(a[mid].fi<=val)l=mid+1,ret=mid;
            else r=mid-1;
        }
        return ret-L[I]+1;
    }
    inline int kth(const res &l,const res &r,const res &k){
        if(k>r-l+1)return -1;
        res pl=l/K,pr=r/K,st=n+1,ed=n;
        if(pl==pr){
            tag[block+1]=tag[pl];
            for(res i=L[pl];i<=R[pl];i++)if(a[i].se<=r&&a[i].se>=l)a[++ed]=a[i];
            L[block+1]=st,R[block+1]=ed;
            res Ll=0,Rr=sum,ret=0;
            while(Ll<=Rr){
                res mid=(Ll+Rr)>>1,p=query(block+1,mid);
                for(res i=pl+1;i<pr&&p<k;i++)p+=query(i,mid);
                if(p>=k)Rr=mid-1,ret=mid;
                else Ll=mid+1;
            }
            return ret;
        }
        tag[block+1]=tag[pl];
        for(res i=L[pl];i<=R[pl];i++)if(a[i].se<=r&&a[i].se>=l)a[++ed]=a[i];
        L[block+1]=st,R[block+1]=ed,st=ed+1,tag[block+2]=tag[pr];
        for(res i=L[pr];i<=R[pr];i++)if(a[i].se<=r)a[++ed]=a[i];
        L[block+2]=st,R[block+2]=ed;
        res Ll=0,Rr=sum,ret=0;
        while(Ll<=Rr){
            res mid=(Ll+Rr)>>1,p=query(block+1,mid)+query(block+2,mid);
            for(res i=pl+1;i<pr&&p<k;i++)p+=query(i,mid);
            if(p>=k)Rr=mid-1,ret=mid;
            else Ll=mid+1;
        }
        return ret;
    }
    inline void modify(const res &I,const res &l,const res &r,const res &val){
        res ax=0,bx=0;
        for(res i=L[I];i<=R[I];i++)
            if(a[i].se<l||a[i].se>r)A[++ax]=a[i];
            else B[++bx]=a[i],B[bx].fi+=val;
        res i=1,j=1,k=L[I];
        while(i<=ax&&j<=bx)a[k++]=(A[i]<B[j]?A[i++]:B[j++]);
        while(i<=ax)a[k++]=A[i++];
        while(j<=bx)a[k++]=B[j++];
    }
    inline void modify(const res &l,const res &r,const res &val){
        res pl=l/K,pr=r/K;
        if(pl==pr)modify(pl,l,r,val);
        else {
            modify(pl,l,r,val),modify(pr,l,r,val);
            for(res i=pl+1;i<pr;i++)tag[i]+=val;
        }
    }
    inline void MAIN(){
        n=read(),m=read(),K=int(sqrt(n*log2(n))),block=n/K;
        for(res i=1;i<=n;i++)a[i]=mp(read(),i),sum+=a[i].fi;
        for(res i=1;i<=n;i++)R[i/K]=i;
        for(res i=n;i;i--)L[i/K]=i;
        for(res i=0;i<=block;i++)sort(a+L[i],a+R[i]+1);
        while(m--){
            res opt=read(),l=read(),r=read(),k=read();
            if(opt==1)printf("%d\n",kth(l,r,k));
            else modify(l,r,k),sum+=k;
        }
    }
}
int main() {
//    srand((unsigned)time(NULL));
//    freopen("graph.in","r",stdin);
//    freopen("graph.out","w",stdout);
    MAIN::MAIN();
    return 0;
}