求一个区间内小于某个数的数量-HDU-4417

HDU-4417：http://acm.hdu.edu.cn/showproblem.php?pid=4417
主席树裸题

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N], cnt, root[N], n, m, x, y, k;
struct node{int l, r, sum; }T[N*20];
vector<int>v;
int getid(int x) {return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;}
void update(int l,int r, int &x, int y, int pos) {
  T[++cnt] = T[y], T[cnt].sum++; x = cnt;
  if(l == r) return;
  int mid = (l + r) / 2;
  if(mid >= pos) update(l, mid, T[x].l, T[y].l, pos);
  else update(mid+1, r , T[x].r, T[y].r, pos);
}
int query(int l, int r, int x, int y, int k) {
  if(r <= k) return T[y].sum - T[x].sum;
  int mid = (l +  r) / 2;
  if(k <= mid) return query(l, mid, T[x].l, T[y].l, k);
  else return T[T[y].l].sum - T[T[x].l].sum + query(mid + 1, r, T[x].r, T[y].r, k);
}
void solve() {
  v.clear();cnt = 0;memset(T, 0, sizeof(T));
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    v.push_back(a[i]);
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for(int i = 1; i <= n; i++) update(1, n , root[i], root[i-1], getid(a[i]));
  for(int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &k);
    x++;y++;
    k = upper_bound(v.begin(), v.end(), k) - v.begin();
    if(k)
      printf("%d\n", query(1, n, root[x-1], root[y], k));
    else printf("0\n");
  }
}
int main() {
  int t;
  scanf("%d", &t);
  for(int i = 1; i <= t; i++) {
    printf("Case %d:\n", i);
    solve();
  }
}