LOJ #2274. 「JXOI2017」加法

题目链接：​​传送门​​

最小值最大化，首先是很明显的二分
其次是很明显的贪心，因为我们要选择一定数量的区间进行操作
二分最后的这个最大值
在check函数中把数组中值小于 二分的最大值 的位置记下来
之后遍历这些位置，把左端点小于这些位置的也就是可能覆盖到这个位置的区间的右端点放进堆中
这个堆是个大根堆，因为右端点越靠右越优
然后不断操作
k次机会用完或者没有区间可以加了就return false
我们需要支持区间修改和单点查询，怎么做都可以
我选择了可爱好写的线段树~~

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct Sect {int l, r;}e[A];
struct node {int l, r, w, f;}tree[A << 2];
void build(int k, int l, int r) {
  tree[k].l = l; tree[k].r = r; tree[k].w = tree[k].f = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r);
}
void down(int k) {
  tree[k << 1].f += tree[k].f; tree[k << 1 | 1].f += tree[k].f;
  tree[k << 1].w += (tree[k << 1].r - tree[k << 1].l + 1) * tree[k].f;
  tree[k << 1 | 1].w += (tree[k << 1 | 1].r - tree[k << 1 | 1].l + 1) * tree[k].f;
  tree[k].f = 0;
}
int ask(int k, int pos) {
  if (tree[k].l == tree[k].r) return tree[k].w;
  if (tree[k].f) down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (pos <= mid) return ask(k << 1, pos);
  else return ask(k << 1 | 1, pos);
}
void add(int k, int l, int r, int val) {
  if (tree[k].l >= l and tree[k].r <= r) {
    tree[k].w += (tree[k].r - tree[k].l + 1) * val;
    tree[k].f += val; return;
  }
  if (tree[k].f) down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (l <= mid) add(k << 1, l, r, val);
  if (r > mid) add(k << 1 | 1, l, r, val);
  tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;
}
int T, n, m, k, a, seq[A], sta[A];
bool check(int mid) {
  build(1, 1, n); int top = 0;
  for (int i = 1; i <= n; i++) if (seq[i] < mid) sta[++top] = i;
  priority_queue<int> q; int now = 1, tmp = k;
  for (int i = 1; i <= top; i++) {
    while (now <= m and e[now].l <= sta[i]) q.push(e[now++].r);
    while (seq[sta[i]] + ask(1, sta[i]) < mid) {
      if (--tmp < 0 or q.empty()) return false;
      add(1, sta[i], q.top(), a); q.pop();
    }
  }
  return true;
}

int main(int argc, char const *argv[]) {
  cin >> T;
  while (T --> 0) {
    scanf("%d%d%d%d", &n, &m, &k, &a);
    for (int i = 1; i <= n; i++) scanf("%d", &seq[i]);
    for (int i = 1; i <= m; i++) scanf("%d%d", &e[i].l, &e[i].r);
    sort(e + 1, e + m + 1, [](Sect a, Sect b) {return a.l != b.l ? a.l < b.l : a.r < b.r;});
    int l = 1, r = 1000000000, ans = 0;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid)) ans = mid, l = mid + 1;
      else r = mid - 1;
    }
    printf("%d\n", ans);
  }
  return 0;
}