题解：AT_abc467_g [ABC467G] Many Sweets Problem

· · 题解

第一次 2400 perf！

题目说人话就是：每次操作进行一次单点修改，然后指定一个区间，找到最小的 t 使得区间前 t 大之和大于等于 k。

等会等会这不是树套树板子吗？上树状数组套线段树即可。

具体地，线段树上维护值域区间有多少个数，以及区间内所有数的和。每次查询时线段树上二分：

注意特判 -1，因为我懒所以又写了个常规树状数组特判。当然在树套树里整也是可以的。

复杂度 O(N \log N \log V)，其中 V 是值域。可能会稍微有点卡空间。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define vct basic_string
const int N=1e5+10,mod=998244353;
const int inf=1e9;
struct tree
{
    signed lc,rc,sum;
    int ss;
}tr[N<<9];
signed tot,rt[N];
int a[N];
int n,q;
struct bit
{
    int c[N];
    void add(int x,int v)
    {
        for(;x<=n;x+=lowbit(x)) c[x]+=v;
    }
    int _sum(int x)
    {
        int s=0;
        for(;x;x-=lowbit(x)) s+=c[x];
        return s;
    }
    int sum(int l,int r)
    {
        return _sum(r)-_sum(l-1);
    }
}bit;
void pushup(int u)
{
    tr[u].sum=tr[tr[u].lc].sum+tr[tr[u].rc].sum;
    tr[u].ss=tr[tr[u].lc].ss+tr[tr[u].rc].ss;
}
void _add(signed& u,int l,int r,int x,int k)
{
    if(!u) u=++tot;
    if(l==r)
    {
        tr[u].sum+=k;
        tr[u].ss+=l*k;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) _add(tr[u].lc,l,mid,x,k);
    else _add(tr[u].rc,mid+1,r,x,k); 
    pushup(u);
}
void add(int x,int v,int k)
{
    for(;x<=n;x+=lowbit(x)) _add(rt[x],0,inf,v,k);
}
int c0,c1,q0[N],q1[N];
void push(int l,int r)
{
    c0=c1=0;
    l--;
    for(;r;r-=lowbit(r)) q0[++c0]=rt[r];
    for(;l;l-=lowbit(l)) q1[++c1]=rt[l];
}
int _sum()
{
    int s=0;
    for(int i=1;i<=c0;i++) s+=tr[tr[q0[i]].rc].sum;
    for(int i=1;i<=c1;i++) s-=tr[tr[q1[i]].rc].sum;
    return s;
}
int _ss()
{
    int s=0;
    for(int i=1;i<=c0;i++) s+=tr[tr[q0[i]].rc].ss;
    for(int i=1;i<=c1;i++) s-=tr[tr[q1[i]].rc].ss;
    return s;
}
void fl()
{
    for(int i=1;i<=c0;i++) q0[i]=tr[q0[i]].lc;
    for(int i=1;i<=c1;i++) q1[i]=tr[q1[i]].lc;
}
void fr()
{
    for(int i=1;i<=c0;i++) q0[i]=tr[q0[i]].rc;
    for(int i=1;i<=c1;i++) q1[i]=tr[q1[i]].rc;
}
int kth(int l,int r,int k)
{
    if(l==r) return (k+l-1)/l;
    int mid=l+r>>1;
    int s=_sum(),t=_ss();
    if(k<=t)
    {
        fr();
        return kth(mid+1,r,k);
    }
    else
    {
        fl();
        return s+kth(l,mid,k-t);
    }
}
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],add(i,a[i],1),bit.add(i,a[i]);
    while(q--)
    {
        int c,x,l,r,k;
        cin>>c>>x>>l>>r>>k;
        bit.add(c,x-a[c]);
        add(c,a[c],-1);
        a[c]=x;
        add(c,x,1);
        if(bit.sum(l,r)<k)
        {
            cout<<-1<<'\n';
            continue;
        }
        push(l,r);
        cout<<kth(0,inf,k)<<'\n';
    }
    return 0;
}

:::