http://acm.hdu.edu.cn/showproblem.php?pid=4417
题意是：给出n个数和q个询问，每个询问有一个l，r，h，问在[l,r]这个区间里面有多少个数是小于等于h的。
思路：比较裸的主席树，注意题意给的区间是从[0,n-1]，一开始看错导致想错了很多东西。询问的时候如果m < h，那么左子树全部都是小于 h 的，就加上左子树的 sum，继续查右子树，否则就查左子树。最后 l == r 的时候要判下 h >= l，因为这个也错了几次。从师兄那里学习到了如果找一个数，如果找不到就返回一个比它小的数，那么可以用 upper_bound() 找到的下标 -1。就不用 lower_bound() 找到后判断等不等于，不等于的话下标 -1 这么麻烦了。（upper_bound()返回的是大于查的数的下标，所以 -1就可以等于或者小于了。）
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 100010
struct node
{
int l, r, sum;
}tree[N*];
int root[N], tot, a[N], b[N], cnt; void update(int pre, int &now, int id, int l, int r)
{
now = ++tot; tree[now] = tree[pre];
tree[now].sum++;
if(l == r) return ;
int m = (l + r) >> ;
if(id <= m) update(tree[pre].l, tree[now].l, id, l, m);
else update(tree[pre].r, tree[now].r, id, m + , r);
} int query(int L, int R, int h, int l, int r)
{
int ans = ;
int m = (l + r) >> ;
if(l == r) {
if(h >= l) ans += tree[R].sum - tree[L].sum; // 注意要判下这个
/*
如果区间查询和更新的区间是(0, cnt)的话,那么就可以不用判定这个
因为如果查的区间是(3, 5, 5) 查 2 的话，那么会查到下标 0,
l > h，这个时候就错了
*/
return ans;
}
if(m < h) {
ans += tree[tree[R].l].sum - tree[tree[L].l].sum; // 如果 h > m 的话,左子树全部都小于h,全部都加上
ans += query(tree[L].r, tree[R].r, h, m + , r);
} else {
ans += query(tree[L].l, tree[R].l, h, l, m);
}
return ans;
} void debug(int rt, int l, int r)
{
if(l == r) {
printf("%d : %d\n", l, tree[rt].sum);
return ;
}
int m = (l + r) >> ;
debug(tree[rt].l, l, m);
debug(tree[rt].r, m+, r);
} int main()
{
int t, cas = ;
scanf("%d", &t);
while(t--) {
int n, q;
scanf("%d%d", &n, &q); tot = ; for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + , b + + n);
cnt = unique(b + , b + + n) - b - ;
for(int i = ; i <= n; i++) {
a[i] = lower_bound(b + , b + + cnt, a[i]) - b;
update(root[i-], root[i], a[i], , cnt);
}
debug(root[n], , cnt);
printf("Case %d:\n", cas++);
for(int i = ; i <= q; i++) {
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
l++, r++;
int tmp = upper_bound(b + , b + + cnt, c) - b - ;
// int tmp = lower_bound(b + 1, b + 1 + cnt, c) - b;
// if(b[tmp] != c) tmp--;
// int tmp = lb(c);
printf("%d\n", query(root[l-], root[r], tmp, , cnt));
}
}
return ;
}