LOJ #2402. 「THUPC 2017」天天愛射擊 / Shooting

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

using namespace std;
struct node {int l, r, w;}tree[A << 5];
int rt[A], cnt, n, m, ans[A];
void insert(int &k, int pre, int l, int r, int pos) {
  k = ++cnt;
  tree[k] = tree[pre]; tree[k].w++;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid) insert(tree[k].l, tree[pre].l, l, mid, pos);
  else insert(tree[k].r, tree[pre].r, mid + 1, r, pos);
}
int ask(int pos, int l, int r, int vl, int vr) {
  if (l == r) return l;
  int mid = (l + r) >> 1, sum = tree[tree[vr].l].w - tree[tree[vl].l].w;
  if (pos <= sum) return ask(pos, l, mid, tree[vl].l, tree[vr].l);
  else return ask(pos - sum, mid + 1, r, tree[vl].r, tree[vr].r);
}
struct Plank {int l, r, s;}p[A];
struct Bullet {
  int x, pos;
  friend bool operator < (const Bullet a, const Bullet b) {return a.x < b.x;}
}b[A];

int main(int argc, char const *argv[]) {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d%d%d", &p[i].l, &p[i].r, &p[i].s);
  for (int i = 1; i <= m; i++) scanf("%d", &b[i].x), b[i].pos = i;
  sort(b + 1, b + m + 1);
  for (int i = 1; i <= m; i++) insert(rt[i], rt[i - 1], 1, m, b[i].pos);
  for (int i = 1; i <= n; i++) {
    int vl = 1, vr = m, l = 0, r = 0;
    while (vl <= vr) {
      int mid = (vl + vr) >> 1;
      if (b[mid].x >= p[i].l) l = mid, vr = mid - 1;
      else vl = mid + 1;
    }
    r = upper_bound(b + 1, b + m + 1, p[i].r, [](int a, Bullet c) {return a < c.x;}) - b - 1;
    if (r - l + 1 < p[i].s) continue;
    ans[ask(p[i].s, 1, m, rt[l - 1], rt[r])]++;
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}