分块

分块

struct Block
{
    static const int __=50005;
    static const int _b_=300;
    ll a[__];int n,bsz,bel[__];
    ll ad[_b_];
    vector<ll>ord[_b_];

    ll operator[](int x){return a[x]+ad[bel[x]];}

    void build()
    {
        bsz=(int)sqrt(n);
        for(int i=1;i<=n;i++)
            ord[bel[i]=(i-1)/bsz+1].pb(a[i]);
        for(int i=1;i<=bel[n];i++)
            sort(ord[i].begin(),ord[i].end());
    }

    void rebuild(int x)
    {
        int r=(bel[n]==x)?n:(x*bsz);
        ord[x].clear();
        for(int i=(x-1)*bsz+1;i<=r;i++)
            ord[x].pb(a[i]);
        sort(ord[x].begin(),ord[x].end());
    }

    void add(int l,int r,ll val)
    {
        for(int i=l;i<=min(r,bel[l]*bsz);i++)
            a[i]+=val;
        rebuild(bel[l]);
        if(bel[l]==bel[r])return;
        for(int i=bel[l]+1;i<bel[r];i++)
            ad[i]+=val;
        for(int i=(bel[r]-1)*bsz+1;i<=r;i++)
            a[i]+=val;
        rebuild(bel[r]);
    }

    int get_min(int l,int r,ll val)
    {
        int res=0;
        for(int i=l;i<=min(r,bel[l]*bsz);i++)
            if(a[i]+ad[bel[i]]<val)res++;
        if(bel[l]==bel[r])return res;
        for(int i=bel[l]+1;i<bel[r];i++)
            res+=lower_bound(ord[i].begin(),ord[i].end(),val-ad[i])-ord[i].begin();
        for(int i=(bel[r]-1)*bsz+1;i<=r;i++)
            if(a[i]+ad[bel[i]]<val)res++;
        return res;
    }

    void clear(){memset(ad,0,sizeof(ad));}
}b;