[Codeforces 1053C] Putting Boxes Together

Link:

Codeforces 1053C 传送门

Solution:

先推出一个结论：

最后必有一个点不动且其为权值上最中间的一个点

证明用反证证出如果不在中间的点必有一段能用代价少的替代多的

这样问题转换为求出区间第一个大于权值和一半的点，并求结果

如果只考虑半边的结果为$sum_{i=1}^{mid} (pos[mid]-pos[i]-(mid-i))*w[i]$

将$pos[i]$修改为$pos[i]-i$之后维护$sum pos[i]*w[i]$的和即可

以上操作可以用两颗线段树来维护

注意：

1、维护$w[i]$时不能取模！

2、对于求权值中间点可以二分+树状数组也可以直接在线段树上二分

线段树上二分时注意如果已经在区间内查询值要不断更新

Code:

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define pb push_back
#define mid ((l+r)>>1)
#define lc k<<1,l,mid
#define rc k<<1|1,mid+1,r
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=5e5+10,INF=1<<28,MOD=1e9+7;

struct SGT
{
    ll seg[MAXN<<2]; 
    //分清何时要取模 
    void Update(int a,ll x,int f,int k,int l,int r)
    {
        if(l==r)
        {seg[k]+=x;if(f) seg[k]%=MOD;return;}
        if(a<=mid) Update(a,x,f,lc);
        else Update(a,x,f,rc);
        seg[k]=seg[k<<1]+seg[k<<1|1];
        if(f) seg[k]%=MOD;
    }
    ll Query(int a,int b,int f,int k,int l,int r)
    {
        if(a<=l&&r<=b) return seg[k];
        ll ret=0;
        if(a<=mid) ret+=Query(a,b,f,lc);
        if(b>mid) ret+=Query(a,b,f,rc);
        return f?ret%MOD:ret;
    }
    //注意线段树二分的处理及此处的引用 
    int Find(int a,int b,ll &x,int k,int l,int r)
    {
        if(a<=l&&r<=b)
        {
            if(seg[k]<x){x-=seg[k];return INF;}
            if(l==r) return l;
            if(x<=seg[k<<1]) return Find(a,b,x,lc);
            else{x-=seg[k<<1];return Find(a,b,x,rc);}
        }
        int ret=INF;
        if(a<=mid)
            ret=min(ret,Find(a,b,x,lc));
        if(b>mid&&ret==INF) 
            ret=min(ret,Find(a,b,x,rc));
        return ret;
    }
}sw,sm;
int n,q,x,y,pos[MAXN],w[MAXN];

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&pos[i]),pos[i]-=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        sw.Update(i,w[i],0,1,1,n);
        sm.Update(i,1ll*w[i]*pos[i],1,1,1,n);
    }
    
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(x<0)
        {
            x=-x;
            sw.Update(x,-w[x],0,1,1,n);
            sm.Update(x,-1ll*w[x]*pos[x],1,1,1,n);
            w[x]=y;
            sw.Update(x,w[x],0,1,1,n);
            sm.Update(x,1ll*w[x]*pos[x],1,1,1,n);
        }
        else
        {
            //此时不能取模 
            ll sum=(sw.Query(x,y,0,1,1,n)+1)/2;
            int p=sw.Find(x,y,sum,1,1,n);
            ll t1=(sw.Query(x,p,1,1,1,n)*pos[p]%MOD-sm.Query(x,p,1,1,1,n)+MOD)%MOD;
            ll t2=(-sw.Query(p+1,y,1,1,1,n)*pos[p]%MOD+sm.Query(p+1,y,1,1,1,n)+MOD)%MOD;
            printf("%lld
",(t1+t2)%MOD);
        }
    }
    return 0;
}