codeforces 1017C - Cloud Computing 权值线段树 差分 贪心

https://codeforces.com/problemset/problem/1070/C

题意:

有很多活动,每个活动可以在天数为$[l,r]$时,提供$C$个价格为$P$的商品

现在从第一天起,每天恰好买$K$个,到第$N$天的花费为多少?

题解:

首先考虑维护区间,即第$i$天还需要多少个,然后尝试区间求和区间更新

但是稍加思考就知道,"需要的数量"并不满足区间加法

于是改变思考方向,

显然,一个暴力的$O(n^2)$算法就是每天保存能买的所有价格和对应的数量,

这样时间和空间都是$O(n^2)$

但是同时注意到,价格的区间的值域只是$10^6$

于是转换思维,离线化活动,使用权值线段树去不断的维护第$i$天时,对应的价格上可以买多少个

这显然是满足区间加法的

然后再用类似差分数组的方法,去打标记

然后按天数跑一边即可

#include <bits/stdc++.h>

#define endl '\n'

#define ll long long

#define fi first

#define se second

#define all(x) x.begin(),x.end()

#define pii pair<int,int>

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)

using namespace std;

const int maxn=1e6+7;

int casn,n,m,k;

#define show(x) cout<<#x<<"="<<x<<endl

#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl

#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl

#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl

#define show5(v,w,x,y,z) cout<<#v<<"="<<v<<" "<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl

#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl

class segtree{public:

#define nd  node[now]

#define ndl node[now<<1]

#define ndr node[now<<1|1]

    struct segnode {

        int l,r;ll cnt,sum;

        int mid(){return (r+l)>>1;}

        int len(){return r-l+1;}

        void update(ll x){cnt+=x;sum+=l*x;}

    };

    vector<segnode> node;

    int cnt;

    segtree(int n) {node.resize(n*4+10);maketree(1,n);}

    void pushup(int now){nd.cnt=ndl.cnt+ndr.cnt;nd.sum=ndl.sum+ndr.sum;}

    void pushdown(int now){}

    void maketree(int s,int t,int now=1){

        nd={s,t,0,0};

        if(s==t) return ;

        maketree(s,nd.mid(),now<<1);

        maketree(nd.mid()+1,t,now<<1|1);

        pushup(now);

    }

    void update(int pos,ll x,int now=1){

        if(pos>nd.r||pos<nd.l) return ;

        if(nd.len()==1){nd.update(x);return ;}

        pushdown(now);

        update(pos,x,now<<1); update(pos,x,now<<1|1);

        pushup(now);

    }

    ll query(ll cnt,int now=1){

        if(cnt<=0) return 0;

        if(cnt>=nd.cnt) return nd.sum;

        if(nd.len()==1) return nd.l*cnt;

        pushdown(now);

        return query(cnt,now<<1)+query(cnt-ndl.cnt,now<<1|1);

    }

};

int main() {

    IO;

    cin>>n>>k>>m;

    vector<vector<pii>> ww(n+2);

    register int a,b,c,d;

    while(m--){

        cin>>a>>b>>c>>d;

        ww[a].emplace_back(d,c);

        ww[b+1].emplace_back(d,-c);

    }

    segtree tree(maxn);

    ll ans=0;

    rep(i,1,n){

        for(auto &j:ww[i]) tree.update(j.fi,j.se);

        ans+=tree.query(k);

    }

    cout<<ans<<endl;

    return 0;

}