区间查询 单点更新

题面

𝑅𝑒𝑘𝑖在课余会接受一些民间的鹰眼类委托，即远距离的狙击监视防卫。
𝑅𝑒𝑘𝑖一共接到了𝑚份委托，这些委托与𝑛个直线排布的监视点相关。
第𝑖份委托的内容为：对于区间[𝑙𝑖, 𝑟𝑖]中的监视点，至少要防卫其中的𝑘𝑖个。
𝑅𝑒𝑘𝑖必须完成全部委托，并且希望选取尽量少的监视点来防卫。

分析

将每一段排序，终点从小到大，起点从小到大，权值从大到小。
先获得每一段区间内的监视点数量，如果少了，则从后面贪心往前设置监视点，如果够了则继续下一段。

线段树、树状数组
区间查询，单点更新（先判断该点是否是监视点，如果是，则判断下一个，不是，则设置，不可以区间更新）

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int n, m;
int tree[maxn * 4];
int vis[maxn];
struct node {
  int u, v, w;
  friend bool operator<(node a, node b) {
    if (a.v != b.v) return a.v < b.v;

    if (a.u != b.u) return a.u < b.u;

    return a.w > b.w;
  }
} e[maxn];
int lowbit(int x) {
  return x & (-x);
}

void change(int x, int v) {
  for (; x <= n; x += lowbit(x)) {
    tree[x] += v;
  }
}

int getsum(int x) {
  int sum = 0;

  for (; x > 0; x -= lowbit(x)) {
    sum += tree[x];
  }
  return sum;
}

int main() {
  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    cin >> e[i].u >> e[i].v >> e[i].w;
  }
  sort(e, e + m);

  for (int i = 0; i < m; i++) {
    int u = e[i].u, v = e[i].v, w = e[i].w;
    int sum = getsum(v) - getsum(u - 1);

    if (sum >= w) continue;

    for (int j = v; j >= u; j--) {
      if (!vis[j]) {
        vis[j] = 1;
        change(j, 1);
        sum++;

        if (sum == w) break;
      }
    }
  }
  cout << getsum(n) << endl;
  return 0;
}