题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4417
题目分析
核心思想为主席树（可持久化线段树），我对于主席树的理解是，多个线段树，但是不是每次建树都是建一个完全新的线段树，不像我们写一般的线段树的题目一样。
主席树中，每次插入一个数的时候，只更新和这个数有关系的区间，其余的全部来自上一个线段树。
这个题相较于最简单的主席树需要多进行一个操作，因为我们需要小于指定高度h的数，那么我们就可以转化为找恰好小于h的数，这个数是所以数中第k大的数，那么k+1就是我们要求的答案了。
代码区
#include <cstdio>
#include <cmath>
#include<cstring>
#include<iostream>
#include <algorithm>
using namespace std;
const int Max = 1e5 + 7;
typedef struct Node {
int val;
int lc, rc;
void init()
{
val = lc = rc = 0;
}
}Node;
Node node[Max<<5];
int tot;//记录结点
int raw[Max], work[Max];//原数组和离散化数组
int rootTree[Max]; //每一个线段树的根结点
//建立第一棵线段树
int build(int l, int r)
{
int now = ++tot;
node[now].init();
if (l == r)return now;
int mid = (l + r) >> 1;
node[now].lc = build(l, mid);
node[now].rc = build(mid + 1, r);
return now;
}
int upData(int last, int l, int r, int k)
{
int now = ++tot; //这个点被访问，那么这个结点就是一个新的
node[now] = node[last];//先完全继承过来
node[now].val++; //数个个数加一
if (l == r)return now;
int mid = (l + r) >> 1;
if (k <= mid) node[now].lc = upData(node[last].lc, l, mid, k);
else node[now].rc = upData(node[last].rc, mid + 1, r, k);
return now;
}
int query(int st, int ed, int fl, int fr, int nl, int nr)
{
if (fl <= nl && nr <= fr) return node[ed].val - node[st].val;
int mid = (nl + nr) >> 1;
int ans = 0;
if (fl <= mid)
ans += query(node[st].lc, node[ed].lc, fl, fr, nl, mid);
if (fr > mid)
ans += query(node[st].rc, node[ed].rc, fl, fr, mid + 1, nr);
return ans;
}
int main()
{
int t;
scanf("%d", &t);
for (int kCase = 1; kCase <= t; kCase++)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d", raw + i);
work[i] = raw[i];
}
sort(work + 1, work + 1 + n);
int k = unique(work + 1, work + 1 + n) - work - 1;
for(int i = 1 ; i <= n ; i++)
{
raw[i] = lower_bound(work + 1, work + 1 + k, raw[i]) - work;
}
tot = 0;
rootTree[0] = build(1, k);
for(int i = 1 ; i <= n ; i++)
{
rootTree[i] = upData(rootTree[i - 1], 1, k, raw[i]);
}
printf("Case %d:\n", kCase);
while(m--)
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
l++, r++;
int h = upper_bound(work + 1, work + 1 + k, x) - work - 1;
if(h == 0)
{
printf("0\n");
}
else
{
printf("%d\n", query(rootTree[l - 1], rootTree[r], 1, h, 1, k));
}
}
}
return 0;
}
