函数式线段树（区间数出现次数）

函数式线段树主要功能有区间 k 大值之类。

其核心思想为：在一个线段树上面利用原有的信息，每次只增加 log 级别的节点，就可以完成复制信息的任务。

这有什么用呢？假设你需要求区间 k 大值，你可以考虑对于每一个节点 i 建一颗线段树，所储存的为每个数在前 i 位上出现的次数，这样就可以在 log n 的时间内统计出一段数字在前 i 为上出现的次数。然后利用区间减法，就可以在 log n 时间内求出区间内数的出现次数前缀和为 k 的那一位，最后确定答案。

这是一道叫 lyp的题，其所求为区间内数的出现次数。代码是动态实现的：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
 
#define swap(a, b, t) ({t _ = (a); (a) = (b); (b) = _;})
#define max(a, b) ({int _ = (a), __ = (b); _ > __ ? _ : __;})
#define min(a, b) ({int _ = (a), __ = (b); _ < __ ? _ : __;})
 
#define maxv 2000005
#define maxn 100005
 
int n, m, tot, k, ll, rr, ans, R = 100000;
int a[maxn];
struct da{int s; da * l, * r;} ve[maxv], * root[maxn];
 
void build(da * & p, int l, int r)
{
	p = ve + (++ tot);
	if (l < r) build(p->l, l, l + r >> 1), build(p->r, (l + r >> 1) + 1, r);
}
 
void revise(da * & p, da * q, int l, int r)
{
	p = ve + (++ tot), * (p) = * (q), ++ p->s;
	if (l == r) return;
	if (k <= l + r >> 1) revise(p->l, q->l, l, l + r >> 1);
	else revise(p->r, q->r, (l + r >> 1) + 1, r);
}
 
int query(da * p, da * q, int l, int r)
{
	if (ll <= l && r <= rr) return q->s - p->s;
	int ans = 0, m = l + r >> 1;
	if (ll <= m) ans += query(p->l, q->l, l, m);
	if (rr > m) ans += query(p->r, q->r, m + 1, r);
	return ans;
}
 
int main()
{
	freopen("lyp.in", "r", stdin);
	freopen("lyp.out", "w", stdout);
	
	scanf("%d%d", & n, & m);
	build(root[0], 0, rr = R);
	for (int i = 1; i <= n; ++ i)
	{
		scanf("%d", a + i);
		k = a[i], revise(root[i], root[i - 1], 0, R);
		ll = k + 1, ans += query(root[0], root[i], 0, R);
	}
	printf("%d\n", ans);
	for (int p, q, l; m --; )
	{
		scanf("%d%d", & p, & q);
		if (l = ans, a[p] < q)
		{
			ll = a[p] + 1, rr = q, l -= query(root[0], root[p - 1], 0, R);
			ll = a[p], rr = q - 1, l += query(root[p], root[n], 0, R);
		}
		else if (q < a[p])
		{
			ll = q + 1, rr = a[p], l += query(root[0], root[p - 1], 0, R);
			ll = q, rr = a[p] - 1, l -= query(root[p], root[n], 0, R);
		}
		printf("%d\n", l);
	}
	
	return 0;
}