题解：AT_abc467_g [ABC467G] Many Sweets Problem

· · 题解

题目大意

对一个长度为 n 的序列 A 进行 q 次操作。每次操作将 a_c 的值改为 x，然后问在区间 [l,r] 内选若干个数，使其和为 k，最少选几个数？若没有这样的方案则输出 -1。

思路

修改操作的格式十分类似于线段树或树状数组，由于这里只包含单点修改，所以使用树状数组。既然使用树状数组进行修改操作，那么我们就要想办法把查询操作使用树状数组解决。

贪心思想没有证明过，赛时交上去是对的，AC link。

这里因为求的最少选的数，所以按照贪心的思想，可以将 [l,r] 这个区间的数从大到小排序，选取，所以问题就可以转化为在 [l,r] 这个区间内找一个最小的 c，使前 c 大的数和大于等于 k。

这里选用整体二分法，可以少些很多毒瘤的数据结构，仅需树状数组。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int N=1e5+10,M=4e5+10;
int n,q,m,v,A[N],ans[N],bsum[N],bcnt[N];
vector<int> val;
struct Event{
    int type,pos,r,val,id,sum,cnt;
    bool f;
}ev[M],tmp[M];
void upd1(int p,int d){
    for(;p<=n;p+=p&-p)
        bcnt[p]+=d;
}
void upd2(int p,int d){
    for(;p<=n;p+=p&-p)
        bsum[p]+=d;
}
int query1(int p){
    int res=0;
    for(;p>0;p-=p&-p)
        res+=bcnt[p];
    return res;
}
int query2(int p){
    int res=0;
    for(;p>0;p-=p&-p)
        res+=bsum[p];
    return res;
}
void apply(Event &e){
    upd1(e.pos,e.type);
    upd2(e.pos,e.type*e.val);
}
void revert(Event &e){
    upd1(e.pos,-e.type);
    upd2(e.pos,-e.type*e.val);
}
void solve(int lv,int rv,int L,int R);
void init();
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>A[i];
        val.push_back(A[i]);
    }
    m=0;
    for(int i=1;i<=n;i++)
        ev[m++]={1,i,0,A[i],0,0,0,0};
    for(int i=1;i<=q;i++){
        int c,l,r,x,k;
        cin>>c>>x>>l>>r>>k;
        val.push_back(x);
        ev[m++]={-1,c,0,A[c],0,0,0,0};
        ev[m++]={1,c,0,x,0,0,0,0};
        A[c]=x;
        ev[m++]={0,l,r,k,i,0,0,0};
    }
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    v=val.size();
    val.insert(val.begin(),0);
    solve(1,v,0,m-1);
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}
void solve(int lv,int rv,int L,int R){
    if(L>R)
        return ;
    if(lv==rv){
        int v=val[lv];
        vector<int> applied;
        for(int i=L;i<=R;i++){
            if(ev[i].type!=0){
                apply(ev[i]);
                applied.push_back(i);
            }else{
                if(ev[i].val<=0){
                    ans[ev[i].id]=ev[i].cnt;
                }else{
                    int s=query2(ev[i].r)-query2(ev[i].pos-1);
                    int c=query1(ev[i].r)-query1(ev[i].pos-1);
                    if(s<ev[i].val){
                        ans[ev[i].id]=-1;
                    }else{
                        int extra=(ev[i].val+v-1)/v;
                        ans[ev[i].id]=ev[i].cnt+extra;
                    }
                }
            }
        }
        for(int idx:applied)
            revert(ev[idx]);
        return ;
    }
    int mid=(lv+rv)/2;
    int midv=val[mid];
    vector<int> applied;
    for(int i=L;i<=R;i++){
        if(ev[i].type!=0){
            if(ev[i].val>midv){
                apply(ev[i]);
                applied.push_back(i);
                ev[i].f=1;
            }else{
                ev[i].f=0;
            }
        }else{
            int s=query2(ev[i].r)-query2(ev[i].pos-1);
            int c=query1(ev[i].r)-query1(ev[i].pos-1);
            if(s>=ev[i].val){
                ev[i].f=1;
            }else{
                ev[i].sum+=s;
                ev[i].cnt+=c;
                ev[i].val-=s;
                ev[i].f=0;
            }
        }
    }
    for(int idx:applied)
        revert(ev[idx]);
    int p=L;
    for(int i=L;i<=R;i++){
        if(!ev[i].f)
            tmp[p++]=ev[i];
    }
    int mididx=p-1;
    for(int i=L;i<=R;i++){
        if(ev[i].f)
            tmp[p++]=ev[i];
    }
    for(int i=L;i<=R;i++)
        ev[i]=tmp[i];
    solve(mid+1,rv,mididx+1,R);
    solve(lv,mid,L,mididx);
}
void init(){
    return ;
}