题解：CF1070C Cloud Computing

题意

给定种云服务计划，每个计划可以在第到第天使用，每天可以提供个 CPU，每个 CPU 的价格是。现在每天需要个 CPU，求最小价格，如果某一天达不到个，那么就取最大的数量。

思路

首先，我们一定是优先选择价格小的 CPU 进行购买。如果我们将天数作为下标，用线段树维护，那么不难发现，这样做空间炸的一点不剩。所以我们需要换一个想法。

观察到，价格、个数在以内，所以我们可以优先考虑将价格或者个数作为下标维护信息。如果我们将个数作为下标，那么无法维护 CPU 的价格。

所以我们将 CPU 的价格作为下标，从小到大枚举天数，我们可以将价格相同的 CPU 视为一种，记录每种 CPU 的数量，每次跑一遍线段树上二分即可。如何解决区间问题？我们使用差分的思想，对区间左端点和右端点后一个的位置记录更改即可。

关于线段树上二分，设我们当前在一个线段树上的一段区间，此时我们的需求数量为，该区间中点为，那么因为我们需要最小化成本，所以我们优先考虑左区间，如果这个区间内的数量已经满足了我们当前的需求，直接返回左区间的所需代价即可；若左区间的答案不够，那么我们就需要跑右区间，返回左区间总代价和右区间的所需代价之和即可。这里使用了一种二分的思想，故名为线段树上二分。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 2e5 + 10, MAXV = 1e6 + 10;

int n, k, m, to[MAXN];
vector<pii> edit[MAXV];
// 差分修改的信息

struct Query {
  int l, r, c, p;
};

// 也可以不用离散化，10^6 也够开
struct Lsh {
  vector<int> v;
  void add(int x) {
    v.push_back(x);
  }
  void build() {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
  }
  int rnk(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
  }
  int len() { return v.size(); }
} L;

// 单点修改线段树
struct Node {
  // 记录代价、数量以及当前的实际价格（若不使用离散化则不用写这一项）
  ll sum, cnt, p;
};

struct SegTree {
  Node dat[MAXN << 2], E = {0};
  Node comb(const Node &dat1, const Node &dat2) {
    return {dat1.sum + dat2.sum, dat1.cnt + dat2.cnt};
  }
  void build(int root, int l, int r) {
    if (l == r) {
      dat[root] = {0, 0, to[l]};
      return;
    }
    int mid = l + r >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    dat[root] = comb(dat[root << 1], dat[root << 1 | 1]);
  }
  void modify(int root, int l, int r, int pos, int val) {
    if (l == r) {
      dat[root].cnt += val;
      dat[root].sum += val * dat[root].p;
      return;
    }
    int mid = l + r >> 1;
    if (pos <= mid) {
      modify(root << 1, l, mid, pos, val);
    } else {
      modify(root << 1 | 1, mid + 1, r, pos, val);
    }
    dat[root] = comb(dat[root << 1], dat[root << 1 | 1]);
  }
  ll query(int root, int l, int r, int k) {
    if (l == r) return {min(k * dat[root].p, dat[root].sum)};
    int mid = l + r >> 1;
    if (dat[root << 1].cnt >= k) {
      return query(root << 1, l, mid, k);
    } else {
      return dat[root << 1].sum + query(root << 1 | 1, mid + 1, r, k - dat[root << 1].cnt);
    }
  }
} T;

vector<Query> Q;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k >> m;
  for (int i = 1, l, r, c, p; i <= m; i++) {
    cin >> l >> r >> c >> p;
    Q.push_back({l, r, c, p});
    L.add(p);
  }
  L.build();
  int t = L.len();
  for (Query &i : Q) {
    to[L.rnk(i.p)] = i.p, i.p = L.rnk(i.p);
    // 记录差分修改信息
    edit[i.l].push_back({i.c, i.p});
    edit[i.r + 1].push_back({-i.c, i.p});
  }
  T.build(1, 1, t);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    // 将当前天数所需要修改的信息应用
    for (pii &j : edit[i]) {
      T.modify(1, 1, t, j.second, j.first);
    }
    // 求答案
    ans += T.query(1, 1, t, k);
  }
  cout << ans;
  return 0;
}