CodeForces 961E. Tufurama(主席树)

题意:给定一个长度为n(1 <= n <= 3e5)的数组a[i](1 <= a[i] <= 1e9)。求有多少对下标(l, r)(1 <= l < r <= n)是合法的。我们认为一对下标是合法的，当且仅当l < r, a[l] >= r, a[r] >= l三者同时成立。n, a[i]都是整数。

分析:典型的主席树问题，从题意我们可以发现，a[i]的范围很大，有(1e9)，但是点的个数不多，因为主席树是动态开点的，如果运气不好，每个点的修改都产生一条链，那么也只有3e5 * log(1e9)个点会被开，(log(1e9) approx 30)，那么就最多有(3e5 * 30)个点，大概要开(9e6)的数组，完全是够的。然后我们就套上经典的主席树模板，对于这个问题，(x < y, 且a[x] >= y, 并且a[y] >= x的元组个数)，我们按顺序预处理好每个读进来的(a[i])，产生了n棵线段树，每棵线段树维护的是同样的值域([1, 1e9])。然后我们循环遍历每棵线段树，表示当前版本的线段树，前面的点都已经插入，(x < y并且x <= a[y]，并且a[x] >= y)的点的个数，当前我们遍历到第i棵线段树，(x < i, x <= a[i])，我们可以比较一下i和a[i]的大小，取小的值，然后查询[i, mx]间的点个数，表示(a[x] >= i)的点个数。

ps.这道题还有(CDQ分治)的做法，等会会写上的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
using LL = long long;
const int N = 200005;
int a[N];

struct Node
{
	//左右儿子的编号
	int l, r;
	int cnt;
}tr[N * 33];

//每棵线段树的版本
int root[N], idx;

int build(int l, int r)
{
	int p = ++idx;
	if (l == r) return p;
	int mid = l + r >> 1;
	tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
	return p;
}

//在x中插入一个点，参数中的p是上一个版本的线段树
int insert(int p, int l, int r, int x)
{
	int q = ++idx;
	tr[q] = tr[p];
	if (l == r)
	{
		++tr[q].cnt;
		return q;
	}
	int mid = l + r >> 1;
	if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
	else tr[q].r = insert(tr[p].r, mid + 1, r, x);
	tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
	return q;
}

LL query(int u, int L, int R, int l, int r)
{
	if (l <= L && r >= R)
	{
		return tr[u].cnt;
	}
	int mid = L + R >> 1;
	LL cnt = 0;
	if (l <= mid) cnt += query(tr[u].l, L, mid, l, r);
	if (r > mid) cnt += query(tr[u].r, mid + 1, R, l, r);
	return cnt;
}

int main()
{
	int n;
	scanf("%d", &n);

	int mx = 0;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		a[i] = min(a[i], n);
		mx = max(mx, a[i]);
	}

	root[0] = build(1, mx);
	for (int i = 1; i <= n; ++i)
	{
		root[i] = insert(root[i - 1], 1, mx, a[i]);
	}

	LL sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (i == a[i]) sum += query(root[i - 1], 1, mx, i, mx);
		else if (a[i] < i) sum += query(root[a[i]], 1, mx, i, mx);
		else sum += query(root[i - 1], 1, mx, i, mx);
	}

	printf("%lld
", sum);

	return 0;
}