CF1070C Cloud Computing 题解【扫描线】【线段树】【模拟】

点击量：357

    这个题依然是Mayfly（tql）的idea，感觉思路也比较奇特。

目录

Description

Buber is a Berland technology company that specializes in waste of investor’s money. Recently Buber decided to transfer its infrastructure to a cloud. The company decided to rent CPU cores in the cloud for \(n\) consecutive days, which are numbered from \(1\) to \(n\). Buber requires \(k\)CPU cores each day.

The cloud provider offers \(m\) tariff plans, the \(i\)-th tariff plan is characterized by the following parameters:

• \(l_i\) and \(r_i\) — the \(i\)-th tariff plan is available only on days from \(l_i\) to \(r_i\), inclusive,
• \(c_i\) — the number of cores per day available for rent on the \(i\)-th tariff plan,
• \(p_i\) — the price of renting one core per day on the \(i\)-th tariff plan.

Buber can arbitrarily share its computing core needs between the tariff plans. Every day Buber can rent an arbitrary number of cores (from \(0\) to \(c_i\)) on each of the available plans. The number of rented cores on a tariff plan can vary arbitrarily from day to day.

Find the minimum amount of money that Buber will pay for its work for \(n\) days from \(1\) to \(n\). If on a day the total number of cores for all available tariff plans is strictly less than \(k\), then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly \(k\) cores this day.

Input

The first line of the input contains three integers \(n\), \(k\) and \(m (1\le n,k\le 10^6,\ 1\le m\le 2\cdot 10^5\) — the number of days to analyze, the desired daily number of cores, the number of tariff plans.

The following mm lines contain descriptions of tariff plans, one description per line. Each line contains four integers \(l_i,\ r_i,\ c_i,\ p_i\ (1\le l_i\le r_i\le n,\ 1\le c_i,p_i\le 10^6)\), where \(l_i\) and \(r_i\) are starting and finishing days of the \(i\)-th tariff plan, \(c_i\) — number of cores, \(p_i\) — price of a single core for daily rent on the \(i\)-th tariff plan.

Output

Print a single integer number — the minimal amount of money that Buber will pay.

Examples

input

5 7 3
1 4 5 3
1 3 5 2
2 5 10 1

output

44

input

7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8

output

462

input

4 100 3
3 3 2 5
1 1 3 2
2 4 4 4

output

64

题意：

    有\(m\)个供应计划，每个计划会在一段时间\([l_i,r_i]\)内提供\(c_i\)个\(\tt CPU\)，每一个价格为\(p_i\)。现在\(\tt Buber\)每天需要\(k\)个\(\tt CPU\)，如果这天没有提供够\(k\)个，他会把这些\(\tt CPU\)全买下来。问在这\(n\)天中他能花最少的钱数是多少。

题解：

    这是一道扫描线经典题。

    我们可以对每个计划拆成开始和结束两个部分做贡献。枚举每一天，当发现有计划开始时，就加上这么多数量的\(\tt CPU\)，存下权值，每个时刻贪心选最便宜的\(k\)个。这个可以用堆来完成，但是一种\(\tt CPU\)会同时有好几个，堆不是很方便，复杂度理论上也不正确。既然是扫描线，自然而然地联想到线段树。

    我们开一棵值域为代价的权值线段树，当计划开始时将对应的代价加上提供的\(\tt CPU\)数量，在每个节点维护子树总代价，每次在权值线段树上找最小的\(k\)个位置统计代价和即可。

    可以说是一道数据结构优化模拟的题。扫描线一类，尤其是较为简单的一维扫描线我做的较少，因此要多向这方面联想。时间复杂度\(O(n\log \max p_i)\)。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1)
#define Mid ((t[k].l+t[k].r)>>1)
using std::sort;
struct node
{
    int l,r;
    long long v,x;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=0;
        x=0;
    }
    node(){}
}t[4001000];
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void change(int k,int p,int x)
{
    if(t[k].l==t[k].r)
    {
        t[k].v+=x;
        t[k].x=(long long)t[k].v*t[k].l;
        return;
    }
    if(p<=Mid)
        change(ls,p,x);
    else
        change(rs,p,x);
    t[k].v=t[ls].v+t[rs].v;
    t[k].x=t[ls].x+t[rs].x;
}
long long ask(int k,int p)//查前p个要用多少钱
{
    if(t[k].l==t[k].r)
        return (long long)p*t[k].l;
    if(p<=t[ls].v)
        return ask(ls,p);
    else
        return t[ls].x+ask(rs,p-t[ls].v);
}
struct st
{
    int t,num,v;//时间 个数 钱
    friend bool operator <(st a,st b)
    {
        return a.t<b.t;
    }
}a[200100],b[200100];
int main()
{
    int n,k,m,l,r,u,v;
    scanf("%d%d%d",&n,&k,&m);
    build(1,1,1000000);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&l,&r,&u,&v);
        a[i].t=l;
        a[i].num=u;
        a[i].v=v;
        b[i].t=r+1;//注意结束时间是r+1
        b[i].num=u;
        b[i].v=v;
    }
    sort(a+1,a+1+m);
    sort(b+1,b+1+m);
    int ta=1,tb=1;
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        while(ta<=m&&a[ta].t<=i)
        {
            change(1,a[ta].v,a[ta].num);
            ++ta;
        }
        while(tb<=m&&b[tb].t<=i)
        {
            change(1,b[tb].v,-b[tb].num);
            ++tb;
        }
        ans+=ask(1,std::min((long long)k,t[1].v));
    }
    printf("%I64d\n",ans);
    return 0;
}