HDU-4417-Super Mario

题目传送门

sol1：离线处理询问，对所有询问按高度排序，然后按高度顺序把每个点的坐标存入树状数组或线段树。

• 树状数组

  #include "bits/stdc++.h"
  using namespace std;
  typedef pair<int, int> PII;
  const int MAXN = 1e5 + 5;
  struct Action {
      int l, r, h;
      int index;
  } q[MAXN];
  int c[MAXN], ans[MAXN];
  PII h[MAXN];
  bool cmp(Action a, Action b) {
      return a.h < b.h;
  }
  int lowbit(int x) {
      return x & -x;
  }
  void add(int x) {
      while (x < MAXN) {
          c[x]++;
          x += lowbit(x);
      }
  }
  int sum(int x) {
      int ans = 0;
      while (x > 0) {
          ans += c[x];
          x -= lowbit(x);
      }
      return ans;
  } 
  int main() {
      int t, n, m;
      scanf("%d", &t);
      for (int ca = 1; ca <= t; ca++) {
          scanf("%d%d", &n, &m);
          memset(c, 0, sizeof(c));
          for (int i = 1; i <= n; i++) {
              scanf("%d", &h[i].first);
              h[i].second = i;
          }
          sort(h + 1, h + 1 + n);
          for (int i = 1; i <= m; i++) {
              scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].h);
              q[i].l++, q[i].r++; q[i].index = i;
          }
          sort(q + 1, q + 1 + m, cmp);
          int k = 1;
          for (int i = 1; i <= m; i++) {
              while (k <= n && h[k].first <= q[i].h) add(h[k++].second);
              ans[q[i].index] = sum(q[i].r) - sum(q[i].l - 1);
          }
          printf("Case %d:
  ", ca);
          for (int i = 1; i <= m; i++) printf("%d
  ", ans[i]);
      }
      return 0;
  }

sol2：如果知道主席树，这题很简单，主席树可以在线处理，而且改一改可以解决坐标[l, r]内大小在[a, b]之间的个数这种询问。

• 主席树

  #include "bits/stdc++.h"
  using namespace std;
  const int MAXN = 1e5 + 5;
  struct Node {
      int lson, rson;
      int cnt;
  } tree[MAXN * 20];
  int root[MAXN], tot;
  int a[MAXN], b[MAXN];
  int build(int l, int r) {
      int i = tot++;
      tree[i].cnt = 0;
      if (l != r) {
          int mid = l + r >> 1;
          tree[i].lson = build(l, mid);
          tree[i].rson = build(mid + 1, r);
      }
      return i;
  }
  int add(int pre, int l, int r, int index) {
      int i = tot++;
      tree[i] = tree[pre];
      tree[i].cnt++;
      if (l != r) {
          int mid = l + r >> 1;
          if (index <= mid) tree[i].lson = add(tree[pre].lson, l, mid, index);
          else tree[i].rson = add(tree[pre].rson, mid + 1, r, index);
      }
      return i;
  }
  int sum(int i, int l, int r, int index) {
      if (r <= index) return tree[i].cnt;
      int mid = l + r >> 1;
      int ans = sum(tree[i].lson, l, mid, index);
      if (index > mid) ans += sum(tree[i].rson, mid + 1, r, index);
      return ans;
  }
  int main() {
      int t; scanf("%d", &t);
      for (int ca = 1; ca <= t; ca++) {
          int n, m, q; tot = 0;
          scanf("%d%d", &n, &q);
          for (int i = 1; i <= n; i++) {
              scanf("%d", &a[i]);
              b[i] = a[i];
          }
          sort(b + 1, b + 1 + n);
          m = unique(b + 1, b + 1 + n) - b - 1;
          root[0] = build(1, m);
          for (int i = 1; i <= n; i++) {
              int index = lower_bound(b + 1, b + 1 + m, a[i]) - b;
              root[i] = add(root[i - 1], 1, m, index);
          }
          printf("Case %d:
  ", ca);
          int l, r, x;
          while (q--) {
              scanf("%d%d%d", &l, &r, &x);
              l++, r++;
              int index = upper_bound(b + 1, b + 1 + m, x) - b - 1;
              if (index < 1) puts("0");
              else printf("%d
  ", sum(root[r], 1, m, index) - sum(root[l - 1], 1, m, index));
          }
      }
      return 0;
  }