noi2017 day2t2

设a[i]为当前方案中第 1..i 天变质的蔬菜有几个，b[i]为前i天至少能卖出几个，方案可行的条件是对任意i有a[i]<=b[i]，用线段树维护b[i]-a[i]。

从小到大枚举天数，枚举到第w天时，对所有u>=w，b[u]+=m，表示第w天从可以卖0个变为m个

选一个蔬菜，在第w天变质，则相当于对所有u>=w，a[u]+=1，因此必须保证w在b[i]-a[i]的最右一个零点的右侧

对每种蔬菜都贪心先取变质时间晚的，用另一颗线段树维护变质时间>=w的最大价值，每次贪心选可行的价值最大的一个更新答案

可以构造一个等价的费用流模型，从而证明贪心的正确性

#include<bits/stdc++.h>

const int N=1e5+;

typedef long long i64;

char ib[N*],*ip=ib,ob[N*],*op=ob;

int _(){

    int x=;

    while(*ip<)++ip;

    while(*ip>)x=x*+*ip++-;

    return x;

}

void pr(i64 x){

    int ss[],sp=;

    do ss[++sp]=x%+;while(x/=);

    while(sp)*op++=ss[sp--];

    *op++=;

}

int max(int a,int b){return a>b?a:b;}

int min(int a,int b){return a<b?a:b;}

int n,m,qp;

i64 as[N],ans=;

int qs[N],md=;

struct item{

    int a,s,c,x;

    void R(){

        a=_(),s=_(),c=_(),x=_();

        a+=s;

    }

    void ins();

    void dec(){

        ans+=a;

        --c;

        if(s)a-=s,s=;

    }

    int tm(){

        if(!x)return md;

        return min(md,(c+x-)/x);

    }

    bool operator<(const item&i)const{return a>i.a;}

}is[N];

std::multiset<item>st[N];

int tr[<<|],mx=;

void up(int x){

    tr[mx+x]=st[x].size()?st[x].begin()->a:;

    for(x=mx+x>>;x;x>>=)tr[x]=max(tr[x<<],tr[x<<^]);

}

void item::ins(){

    if(c<=)return;

    int x=tm();

    st[x].insert(*this);

    up(x);

}

void maxs(int&a,int b){if(a<b)a=b;}

void mins(int&a,int b){if(a>b)a=b;}

int _l,_a;

struct node{

    node*lc,*rc;

    int L,R,M;

    int v,a,p;

    void add(int x){

        v+=x,a+=x;

    }

    void add(){

        if(_l<=L)return add(_a);

        dn();

        if(_l<=M)lc->add();

        rc->add();

        up();

    }

    void dn(){

        if(a){

            lc->add(a);

            rc->add(a);

            a=;

        }

    }

    void up(){

        v=rc->v,p=rc->p;

        if(lc->v<v)v=lc->v,p=lc->p;

    }

}ns[N*],*np=ns,*rt;

node*build(int L,int R){

    node*w=np++;

    w->L=L,w->R=R;

    w->p=R;

    if(L<R){

        int M=w->M=L+R>>;

        w->lc=build(L,M);

        w->rc=build(M+,R);

    }

    return w;

}

bool chk(int pos){

    int mw=;

    for(int w=mx+pos-;w;w>>=)if((~w&)&&tr[w+]>tr[mw])mw=w+;

    if(!mw)return ;

    for(;mw<mx;mw<<=,mw+=(tr[mw]<tr[mw+]));

    mw-=mx;

    item i=*st[mw].begin();

    st[mw].erase(st[mw].begin());up(mw);

    i.dec();

    i.ins();

    _l=mw,_a=-,rt->add();

    return ;

}

int main(){

    fread(ib,,sizeof(ib),stdin);

    n=_();m=_();qp=_();

    for(int i=;i<n;++i)is[i].R();

    for(int i=;i<qp;++i)maxs(md,qs[i]=_());

    rt=build(,md);

    for(mx=;mx<=md+;mx<<=);

    for(int i=;i<n;++i)is[i].ins();

    for(int i=;i<=md;++i){

        _l=i,_a=m,rt->add();

        while(){

            int pos=rt->v?:rt->p+;

            if(pos>n||!chk(pos))break;

        }

        as[i]=ans;

    }

    for(int i=;i<qp;++i)pr(as[qs[i]]);

    fwrite(ob,,op-ob,stdout);

    return ;

}