[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+,INF=<<,MOD=1e9+;

struct SGT

{

    ll seg[MAXN<<];

    //分清何时要取模

    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<<]+seg[k<<|];

        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=;

        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<<]) return Find(a,b,x,lc);

            else{x-=seg[k<<];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=;i<=n;i++)

        scanf("%d",&pos[i]),pos[i]-=i;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&w[i]);

        sw.Update(i,w[i],,,,n);

        sm.Update(i,1ll*w[i]*pos[i],,,,n);

    }

    while(q--)

    {

        scanf("%d%d",&x,&y);

        if(x<)

        {

            x=-x;

            sw.Update(x,-w[x],,,,n);

            sm.Update(x,-1ll*w[x]*pos[x],,,,n);

            w[x]=y;

            sw.Update(x,w[x],,,,n);

            sm.Update(x,1ll*w[x]*pos[x],,,,n);

        }

        else

        {

            //此时不能取模

            ll sum=(sw.Query(x,y,,,,n)+)/;

            int p=sw.Find(x,y,sum,,,n);

            ll t1=(sw.Query(x,p,,,,n)*pos[p]%MOD-sm.Query(x,p,,,,n)+MOD)%MOD;

            ll t2=(-sw.Query(p+,y,,,,n)*pos[p]%MOD+sm.Query(p+,y,,,,n)+MOD)%MOD;

            printf("%lld\n",(t1+t2)%MOD);

        }

    }

    return ;

}

巴特西

[Codeforces 1053C] Putting Boxes Together

Link:

Solution:

Code:

最新文章

热门文章