正题

题目链接:https://ac.nowcoder.com/acm/contest/11161/E

题目大意

给出\(n\)个数字的一个序列，\(m\)个操作。

给出\(l,r,k\)，求一个最大的\(x\)使得\(\sum_{i=l}^rmax\{a_i-x,0\}\geq k\)
单点修改

解题思路

带修的比较麻烦，用带修莫队的话需要平衡一下时间复杂度，可以用分块来做。

这样修改是\(O(1)\)的，但是询问的话朴素的想法是二分然后统计，这个\(O(m\sqrt n\log n)\)显然是过不了的。

但是如果改为一个个块从后往前跳确定答案在哪个块，然后在块里枚举就好了。

时间复杂度\(O(mn^{\frac{2}{3}}+m\sqrt n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const ll N=1e5+10;

struct node{

    ll l,r,k,id,t;

}q[N];

ll n,m,T,Q,a[N],L[N],R[N],pos[N],p[N],c[N];

ll qnt,mnt,s[N],cnt[N],v[N],ans[N];

bool cmp(node x,node y){

    if(x.l/T!=y.l/T)return x.l<y.l;

    if(x.r/T!=y.r/T)return x.r<y.r;

    return x.t<y.t;

}

void Add(ll x,ll f){

    s[pos[x]]+=x*f;

    cnt[pos[x]]+=f;

    v[x]+=f;return;

}

ll Query(ll k){

    if(!k)return 100000;

    ll pt,sum=0,ct=0;

    for(pt=Q;pt>=1;pt--){

        sum+=s[pt];ct+=cnt[pt];

        if(sum-ct*R[pt-1]>=k)

        {sum-=s[pt];ct-=cnt[pt];break;}

    }

    if(!pt)return -1;

    for(ll i=R[pt];i>=L[pt];i--){

        sum+=v[i]*i;ct+=v[i];

        if(sum-ct*(i-1)>=k)

            return i-1;

    }

    return -1;

}

signed main()

{

    scanf("%lld%lld",&n,&m);

    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);

    T=pow(n*m,1.0/3.0);Q=316;

    for(ll i=1;i<=Q;i++)

        L[i]=R[i-1]+1,R[i]=i*Q;

    ++Q;L[Q]=R[Q-1]+1;R[Q]=1e5;

    for(ll i=1;i<=Q;i++)

        for(ll j=L[i];j<=R[i];j++)pos[j]=i;

    for(ll i=1;i<=m;i++){

        ll op;scanf("%lld",&op);

        if(op==0){

            ++qnt;q[qnt].id=qnt;q[qnt].t=mnt;

            scanf("%lld%lld%lld",&q[qnt].l,&q[qnt].r,&q[qnt].k);

        }

        else ++mnt,scanf("%lld%lld",&p[mnt],&c[mnt]);

    }

    sort(q+1,q+1+qnt,cmp);

    ll l=1,r=0,t=0;

    for(ll i=1;i<=qnt;i++){

        while(l<q[i].l)Add(a[l],-1),l++;

        while(l>q[i].l)l--,Add(a[l],1);

        while(r<q[i].r)r++,Add(a[r],1);

        while(r>q[i].r)Add(a[r],-1),r--;

        while(t<q[i].t){

            t++;

            if(l<=p[t]&&p[t]<=r)

                Add(a[p[t]],-1),Add(c[t],1);

            swap(a[p[t]],c[t]);

        }

        while(t>q[i].t){

            swap(a[p[t]],c[t]);

            if(l<=p[t]&&p[t]<=r)

                Add(a[p[t]],1),Add(c[t],-1);

            t--;

        }

        ans[q[i].id]=Query(q[i].k);

    }

    for(ll i=1;i<=qnt;i++)

        printf("%lld\n",ans[i]);

    return 0;

}

巴特西

牛客挑战赛48E-速度即转发【带修莫队,分块】

正题

题目大意

解题思路

code

最新文章

热门文章