2018 NEERC South-sub C-Cloud Computing(CF-1070 C)(セグメントツリー)

2362 ワード

タイトルリンク
1〜n日毎日k個のcpuが必要であり、cpuにはm種のスキームがあり、各スキームは使用可能な期限、数、価格を与えている.1-n日の最小総費用はいくらですか.
これには線分の木が必要だと思いがちです.ただし、セグメントツリーのノードは価格であり、現在の状況では、価格区間内の総数目と価格区間内の総費用が格納されます.
1からnまでの遍歴時間は、各時刻において、セグメントツリーに現在使用可能なスキーマのみが存在する.この操作は,左端点と右端点をそれぞれソートすることによってmlogTの時間内に完了する.次に、クエリーの操作について、クエリーの数kについて、左の息子の数がk以上であれば、左の息子でクエリーします.そうしないと、左の息子の総代価に右の息子のクエリーが加算されます.全体的な複雑度はO((n+m)logT)であり,ここでTは各スキームの代価の最大値である.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;

const int maxn = 1000050;

int n, q, m;
struct node
{
    int l, r;
    int c, p;
}a[maxn], b[maxn];
ll sum[maxn << 2], num[maxn << 2];
bool cmp1(node a, node b)
{
    return a.l < b.l;
}
bool cmp2(node a, node b)
{
    return a.r < b.r;
}

void update(int root, int l, int r, int c, int aim)
{
    if(l == r)
    {
        num[root] += c;
        sum[root] += 1LL*c*l;
        return;
    }
    int mid = (l + r) >> 1;
    if(aim <= mid) update(root*2, l, mid, c, aim);
    else update(root*2 + 1, mid + 1, r, c, aim);
    num[root] = num[root*2] + num[root*2 + 1];
    sum[root] = sum[root*2] + sum[root*2 + 1];
}

ll query(int root, int l, int r, int aim)
{
    if(l == r)
    {
        if(num[root] >= aim) return 1LL*aim*l;
        return sum[root];
    }
    int mid = (l + r) >> 1;
    if(num[root*2] >= aim) return query(root*2, l, mid, aim);
    return query(root*2 + 1, mid + 1, r, aim - num[root*2]) + sum[root*2];
}

int main()
{
    scanf("%d%d%d", &n, &q, &m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d%d%d", &a[i].l, &a[i].r, &a[i].c, &a[i].p);
        b[i] = a[i];
    }
    int maxx = 0;
    for(int i = 1;i <= m;i++) maxx = max(maxx, a[i].p);
    sort(a+1, a+m+1, cmp1);
    sort(b+1, b+m+1, cmp2);
    ll ans = 0;
    for(int i = 1, j = 1, k = 1;i <= n;i++)
    {
        while(j <= m && a[j].l == i)
            update(1, 1, maxx, a[j].c, a[j].p), j++;
        ans += query(1, 1, maxx, q);
        while(k <= m && b[k].r == i)
            update(1, 1, maxx, -b[k].c, b[k].p), k++;
    }
    printf("%I64d
", ans);
    return 0;
}

controller を間違えて生成してしまったら

【Railsチュートリアル】第１章にあるGitのこと