P10196 [USACO24FEB] Lazy Cow P

chrhaa · 2024-02-27 09:29:35 · 题解

数据结构题

考虑到 b 的数据范围极大，先离散化。

因为贡献是 3^{a-1}，所以一定测试用例越平均越好（感性理解）。发现约束条件是针对前缀的，那么有一个显然的贪心，即在平均分布的情况下，测试用例多的日子尽量靠前。

定每天准备 a_i 个测试用例，那么有 a_i \geq a_{i+1}，画成条状图，就是一个向左上延伸的台阶。对于第 i 个要求，若当前状态尚未满足，则一定要增加 m_i 前的 a_i 值，由于特殊的贡献方式，更新a_i值时一定要先增加较小的 a_i ，形象一点说，就是往这个台阶里倒水。而增加了前面的 a_i，后面就可以去掉若干，同理是把台阶从上至下切掉一部分。

区间赋值，区间和查询，最长值相等区间长度，即可用线段树维护，以下是一份丑陋的代码。

#include<stdio.h>
const int N=200005;
const int M=4000005;
const int K=1000000;

#define ll long long
const ll P=1000000007;

inline ll Q(ll x,ll y=P-2,ll z=1){
    for(;y;y>>=1,x=x*x%P)
    (y&1)&&(z=z*x%P);return z;
}

bool t[M];
int lb[M],rb[M];
ll lf[M],rf[M];
ll sm[M],lz[M];

#define ls (x<<1)
#define rs (x<<1|1)

inline void tag(int x,int l,int r,ll v){
    sm[x]=(r-l+1)*v;
    lb[x]=rb[x]=r-l+1;
    lf[x]=rf[x]=v;
    lz[x]=v;
}

inline void pushdown(int x,int l,int r){
    if(lz[x]>=0){
        int mid=(l+r)>>1;
        tag(ls,l,mid,lz[x]);
        tag(rs,mid+1,r,lz[x]);
        lz[x]=-1;
    }
}

inline void pushup(int x,int l,int r){
    sm[x]=sm[ls]+sm[rs];
    lf[x]=lf[ls];
    rf[x]=rf[rs];
    lb[x]=(t[ls]&&rf[ls]==lf[rs])?(lb[ls]+lb[rs]):lb[ls];
    rb[x]=(t[rs]&&rf[ls]==lf[rs])?(rb[rs]+rb[ls]):rb[rs];
    t[x]=(lb[x]==r-l+1);
}

void build(int x,int l,int r){
    sm[x]=0;
    lz[x]=-1;
    lb[x]=rb[x]=r-l+1;
    lf[x]=rf[x]=0;
    t[x]=1;

    if(l<r){
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
    }
}

void update(int x,int l,int r,int L,int R,ll v){
    if(L>R||r<L||l>R) return ;
    if(L<=l&&r<=R){
        tag(x,l,r,v);
        return ;
    }

    int mid=(l+r)>>1;
    pushdown(x,l,r);
    update(ls,l,mid,L,R,v);
    update(rs,mid+1,r,L,R,v);
    pushup(x,l,r);
}

ll query(int x,int l,int r,int L,int R){
    if(L>R||r<L||l>R) return 0;
    if(L<=l&&r<=R) return sm[x];

    int mid=(l+r)>>1;
    pushdown(x,l,r);
    return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R); 
}

int queryl(int x,int l,int r,int p){
    if(l==r)
    return 1;

    int mid=(l+r)>>1;
    pushdown(x,l,r);

    if(p<=mid) return queryl(ls,l,mid,p);
    else{
        int res=queryl(rs,mid+1,r,p);

        if(res==p-mid&&rf[ls]==lf[rs])
        return res+rb[ls];
        else return res;
    }
}

int queryr(int x,int l,int r,int p){
    if(l==r)
    return 1;

    int mid=(l+r)>>1;
    pushdown(x,l,r);

    if(p<=mid){
        int res=queryr(ls,l,mid,p);

        if(res==mid-p+1&&rf[ls]==lf[rs])
        return res+lb[rs];
        else return res;
    }else return queryr(rs,mid+1,r,p);
}

int n,m;
ll ans,a,b,c,tmp;

void calc(int x,ll y,ll f)
{(y>0)&&(ans=(ans+P+Q(3,y-1)*f*(ll)x%P)%P);}

signed main(){
    int i,x,p,y;
    scanf("%d",&n);
    build(1,1,K);

    for(i=1;i<=n;i++){
        scanf("%d%lld",&m,&b);
        a=query(1,1,K,m,m);
        b-=query(1,1,K,1,m);
        p=m;

        if(b<=0)
        goto END;

        tmp=b;

        while(b>0&&p>0){
            x=queryl(1,1,K,p);
            p-=x;
            x=m-p;
            calc(x,a,-1);
            y=int(b%(ll)x);

            if(p>0){
                c=query(1,1,K,p,p);

                if((c-a)*(ll)x<b){
                    b-=(c-a)*(ll)x;
                    calc(x,c,1);
                    a=c;
                }else{
                    a+=b/(ll)x;
                    calc(y,a+1,1);
                    update(1,1,K,p+1,p+y,a+1);
                    calc(x-y,a,1);
                    update(1,1,K,p+y+1,p+x,a);
                    b=0;
                }
            }else{
                a+=b/(ll)x;
                calc(y,a+1,1);
                update(1,1,K,1,y,a+1);
                calc(x-y,a,1);
                update(1,1,K,y+1,x,a);
            }
        }

        b=tmp;
        p=m+1;

        if(p<=K)
        a=query(1,1,K,p,p);

        while(b>0&&p<=K){
            x=queryr(1,1,K,p);
            p+=x;
            x=p-m-1;
            calc(x,a,-1);
            y=int(b%(ll)x);

            if(p<=K){
                c=query(1,1,K,p,p);

                if((a-c)*(ll)x<b){
                    b-=(a-c)*(ll)x;
                    calc(x,c,1);
                    a=c;
                }else{
                    a-=b/(ll)x;
                    calc(y,a-1,1);
                    update(1,1,K,p-y,p-1,a-1);
                    calc(x-y,a,1);
                    update(1,1,K,p-x,p-y-1,a);
                    b=0;
                }
            }else if(a*(ll)x>=b){
                a-=b/(ll)x;
                calc(y,a-1,1);
                update(1,1,K,p-y,p-1,a-1);
                calc(x-y,a,1);
                update(1,1,K,p-x,p-y-1,a);
            }else update(1,1,K,m+1,K,0);
        }

        END:;
        printf("%lld\n",ans);
    }return 0;
}