【CF1030F】Putting Boxes Together（线段树维护动态区间带权中位数）

这道题的模数把我调的快死亡了，不过这确实是一道不错的题，让我们来回顾一下。

原问题我们可以转换为所有数走到一个点上，再分散开来，因为他们相对位置是一定的。接着我们发现，着很显然是一个区间动态带权中位数问题。

没错博主看到这儿的时候也懵逼了，因为他没做过带权中位数的题

于是博主去学习了下带权中位数，让我们来看看简略的介绍吧

相信你一定没有看懂吧。不妨举个例子，我们有很经典的货仓选址的模型，就是在直线上有n个点，每一个点i有一个位置pos[i]，重量w[i]，每一个点有一个货物。定义运输货物的代价是移动的距离*w[i]。现在要在直线上选择一个点建立货仓，要把所有的货物都运到这个点，要求使使代价最小，求这个最小代价。

事实上带权中位数为满足【CF1030F】Putting Boxes Together（线段树维护动态区间带权中位数）最小的k

让我们来口胡一下证明吧

假设当前所有数要从k移到k+1，左边的数会多走【CF1030F】Putting Boxes Together（线段树维护动态区间带权中位数），右边同理，总得权值变化量为，那显然，若，有更优解，只有时草才没有更优解，又因为这玩意儿是从左边移过来的，所以左边的都比他劣。那么它一定是最优的。

那让我们看看代码吧，找带权中位数使用二分的方式，考虑找到断点p后，(在这里只考虑左边，右边同理，留给您自行思考并解决)

【CF1030F】Putting Boxes Together（线段树维护动态区间带权中位数）

用线段树维护w[i]，w[i]*(a[i]-i)，就能解决了

注意，注意，注意，维护w[i]不能取模，否则二分的check会出事

#include<bits/stdc++.h>
#define re register
#define ll long long
const int N=2e5+5;
const int mod=1000000007;
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0; int f=1;
    static char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
}
inline void write(ll x)
{
    if(x<0) {x=-x; putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0'); 
}
int n,Q;
ll a[N],w[N],b[N];
struct Tree
{
    int l,r;
    ll sum,s;
}tree[4*N];
inline void pushup(int now)
{
    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    tree[now].s=(tree[now<<1].s+tree[now<<1|1].s)%mod;
}
inline void build(int now,int l,int r)
{
    tree[now].l=l,tree[now].r=r;
    if(l==r)
    {
        tree[now].sum=w[l];
        tree[now].s=b[l]*w[l]%mod;
        return;
    }
    int m=(l+r)>>1;
    build(now<<1,l,m);
    build(now<<1|1,m+1,r);
    pushup(now);
}
inline ll query(int now,int l,int r)
{
    if(l<=tree[now].l&&tree[now].r<=r) return tree[now].sum;
    int m=(tree[now].l+tree[now].r)>>1; ll ans=0;
    if(l<=m) ans+=query(now<<1,l,r);
    if(r>m) ans+=query(now<<1|1,l,r);
    return ans;
}
inline void update(int now,int pos,int x)
{
    if(tree[now].l==tree[now].r)
    {
        tree[now].sum=x;
        tree[now].s=b[pos]*x%mod;
        return;
    }
    int m=(tree[now].l+tree[now].r)>>1;
    if(pos<=m) update(now<<1,pos,x);
    else update(now<<1|1,pos,x);
    pushup(now);
}
inline ll ask(int now,int l,int r)
{
    if(l<=tree[now].l&&tree[now].r<=r)	return tree[now].s;
    int m=(tree[now].l+tree[now].r)>>1; ll ans=0;
    if(l<=m) ans=(ans+ask(now<<1,l,r))%mod;
    if(r>m) ans=(ans+ask(now<<1|1,l,r))%mod;
    return ans;	
}
inline void Solve(int l,int r)
{
    int L=l,R=r,ans=l;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        ll QL=query(1,l,mid),QR=query(1,mid+1,r);
        if(QL>=QR) ans=mid,R=mid-1;
        else L=mid+1;
    }
    ll t1=(query(1,l,ans-1)%mod*(a[ans]-ans)%mod-ask(1,l,ans-1)+mod)%mod;
    ll t2=(query(1,ans+1,r)%mod*(ans-a[ans]+mod)%mod+ask(1,ans+1,r)%mod)%mod;
	write((t1+t2)%mod);
	putchar('\n');
} 
int main()
{
    read(n),read(Q);
    for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i]-i;
    for(int i=1;i<=n;i++) read(w[i]);
    build(1,1,n);
    int l,r;
    while(Q--)
    {
        read(l),read(r);
        if(l<0) update(1,-l,r);
        if(l>0)	Solve(l,r);
    }
    return 0;
}

【CF1030F】Putting Boxes Together（线段树维护动态区间带权中位数）

相关推荐