发布于 由itewqq

[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together

题目：http://codeforces.com/problemset/problem/1030/F

这个题最主要的是自己没有想出来怎么求出那个“不动的点”，因为其实整体的cost用k去表示出来是很困难的，求出来也无法发现其极值点。但是如果考虑差分就会比较好做，很容易发现当当前设的k点变成k+1时，cost变化了(S(l,k)-S(k+1,r))*(p[k+1]-p[k])，其中S(l,r)=Σw[i](l<=i<=r)。这样的话很明显当且仅当S(l,k)≤S(k+1,r)S(l,k)≤S(k+1,r)时k+1比k更优。所以我们只要找到最小的k使得S(l,k)>=S(l,r)/2就行了！

然后是对于一个[l,r]对求出k之后，如何快速的求出其cost。

对于i∈(l,k)i∈(l,k) 代价是∑(pk−pi−(k−i))∗wi（l<=i<=k)
对于i∈(k,r)i∈(k,r) 代价是∑(pi−pl−(i−k))∗wi（k<=i<=r)

把pi-i看成一个整体，记为ai，就可以得到cost=∑(ak−ai)∗wi(l<=i<=k)+∑(ai−al)∗wi(k<=i<=r)

展开整理就可以得到cost=ak*(S(l,k)-S(k,r))-(Σwi*ai(l<=i<=k)-Σwi*ai(k<=i<=r))。这样的话用一个BIT快速求S(l,r)，另一个BIT快速求Σwi*ai就可以了。

wa点的话，发现了一个以前没有注意到的bug，那就是我每次判断都是if(x>mod)x%=mod;但是忽然意识到在有减法的运算中，还有一种下越界的可能性，所以应该是if(x>mod||x<-mod)x%=mod; 

#include
#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long LL;
const int maxn=2e5+5;
const int mod=1e9+7;


int n,l,r;
LL S[maxn<<1],wp[maxn<<1],owp[maxn],os[maxn],ps[maxn];
LL add(LL a,LL b)
{
    if(a+b>mod)return a+b-mod;
    else return a+b;
}
int lowbit(int x){return x&(-x);}
void change1(int p,int x)
{
    while(p<=n)
    {
        S[p]+=x;
        p+=lowbit(p);
    }
}

void change2(int p,int x)
{
    while(p<=n)
    {
        wp[p]=add(x,wp[p]);
        p+=lowbit(p);
    }
}

LL ssum(int k)
{
    LL ans=0;
    while(k>0)
    {
        ans+=S[k];
        k-=lowbit(k);
    }
    //if(ans>mod)
        //return ans%mod;
    //else
        return ans;//error3
}

int wpsum(int k)//LL error3
{
    LL ans=0;
    while(k>0)
    {
        ans=add(ans,wp[k]);
        k-=lowbit(k);
    }
    if(ans>mod||ans<-mod)// !!!
        return ans%mod;
    else
        return ans;
}

LL ask(int l,int r,int op)
{
    if(op==1)
        return ssum(r)-ssum(l-1);//with error3
    else
        return wpsum(r)-wpsum(l-1);//with error4,LL
}

int findk(int l,int r)
{
    int L=l,R=r,mid;
    double al=1.0*(ask(l,r,1))/2;
    while(L>1;
        if(ask(l,mid,1)>=al)
            R=mid;
        else
            L=mid+1;
    }
    return L;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int q,a,b,pos;
    LL nw,n1,n2;
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++)
        scanf("%lld",&ps[i]);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&os[i]);
        owp[i]=(ps[i]-i)*os[i];
        if(owp[i]>mod)
            owp[i]%=mod;
        change1(i,os[i]);
        change2(i,owp[i]);
    }
    while(q--)
    {
        scanf("%d%d",&a,&b);
        if(a<0)
        {
            pos=-a,nw=b;
            n1=nw-os[pos],n2=(nw*(ps[pos]-pos)-owp[pos])%mod;
            os[pos]=b;
            owp[pos]=nw*(ps[pos]-pos);//error2
            change1(pos,n1);
            change2(pos,n2);
        }
        else
        {
            int k=findk(a,b);
            l=a,r=b;//error1
            LL ans=((ask(l,k,1)-ask(k,r,1))*(ps[k]-k)-(ask(l,k,2)-ask(k,r,2)))%mod;
            printf("%lld\n",(ans%mod+mod)%mod);
        }
    }
    return 0;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。