hdu 4417 Super Mario

题意：

有一个长度为  () 的区间，有  次询问 () ，每次询问三个数字L，R，H，询问区间 L - R 内有多少个数字小于等于H。

离线主席树裸题，把离线查询第K大的板子改改就行。但是，这个题目有点意思。

１、询问的　L，R　下标从０开始。所以每次询问先把　L，Ｒ　加１。

２、大部分主席树的题目的序列都是的排列，所以不需要离散化，但这题比较妙。

３、首先一定要离散化，然后考虑离散化的数字，长度为  的区间加上  个询问，一共  个数字，然后离散化，这题就做完了。

４、交上去，MLE，嗯，算一算，空间复杂度  ，，结构体开小一点？WA了？

５、所以我们只离散化长度为  的区间，然后针对每一次询问的  ，先找出比  大的数的位置，然后  ，然后就避免了MLE。

６、ＡＣ。

Code

#include <bits/stdc++.h>
#define imid int mid=(left+right)/2;
using namespace std;
struct node
{
	int l;
	int r;
	int sum;
	node() { sum = 0; }
}tree[100005 * 20];
int n, m, cnt, a[100005], t[100005], root[100005];
void init()
{
	root[0] = 0;
	tree[0].l = tree[0].r = tree[0].sum = 0;
	cnt = 1;
}
void build(int num, int &rot, int left, int right)
{
	tree[cnt] = tree[rot];
	rot = cnt++;
	tree[rot].sum++;
	if (left == right)
		return;
	imid;
	if (num <= mid)
		build(num, tree[rot].l, left, mid);
	else
		build(num, tree[rot].r, mid + 1, right);
}
int query(int pre, int nex, int num, int left, int right)
{
	int s = tree[tree[nex].l].sum - tree[tree[pre].l].sum;
	if (left == right)
		return s;
	imid;
	if (num < mid)
		return query(tree[pre].l, tree[nex].l, num, left, mid);
	else if (num > mid)
		return s + query(tree[pre].r, tree[nex].r, num, mid + 1, right);
	else
		return s;
}
int main()
{
	int tt, cas = 1;
	scanf("%d", &tt);
	while (tt--)
	{
		printf("Case %d:\n", cas++);
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			t[i] = a[i];
		}
		int ql, qr, k, cnts = n;
		sort(t + 1, t + 1 + cnts);
		cnts = unique(t + 1, t + 1 + cnts) - t - 1;
		for (int i = 1; i <= n; i++)
			a[i] = lower_bound(t + 1, t + 1 + cnts, a[i]) - t;
		init();
		for (int i = 1; i <= n; i++)
		{
			root[i] = root[i - 1];
			build(a[i], root[i], 1, n);
		}
		for (int i = 0; i < m; i++)
		{
			scanf("%d%d%d", &ql, &qr, &k);
			ql++;
			qr++;
			k = upper_bound(t + 1, t + 1 + cnts, k) - t;
			k--;
			int ans = query(root[ql - 1], root[qr], k, 1, n);
			printf("%d\n", ans);
		}
	}
}