[Educational Codeforces Round 41] E Tufurama

        题目大意：给定序列\(\{a_n\}\)，求有多少对\(x < y\)满足\(a[x] \geq y\)且\(a[y] \geq x\)。\(1 \leq n \leq 2 \cdot 10^5 , 1 \leq a_i \leq 10^9\)。

        题解：可将题目转化为在区间\([1,min(i-1,a[i])]\)中找出满足\(a[x] \geq i\)的x的个数，求和，主席树无脑过。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,maxv=maxn*32,maxa=1e9;

struct President_Tree
{
	struct Node
	{
		int sl,sr;
		int sum;
	}P[maxv];
	int root[maxn];
	int Pcnt;

	#define mid ((l+r)>>1)

	void Update(int o)
	{
		P[o].sum=P[P[o].sl].sum+P[P[o].sr].sum;
	}

	void Insert(int l,int r,int pn,int &nn,int x)
	{
		nn=++Pcnt;
		P[nn]=P[pn];
		if (l==r)
		{
			++P[nn].sum;
			return;
		}
		if (x<=mid)
			Insert(l  ,mid,P[pn].sl,P[nn].sl,x);
		else
			Insert(mid+1,r,P[pn].sr,P[nn].sr,x);
		Update(nn);
	}

	void Insert(int n,int x)
	{
		Insert(1,maxa,root[n-1],root[n],x);
	}

	long long Query(int l,int r,int o,int a,int b)
	{
		if (a<=l && r<=b) return P[o].sum;
		long long res=0;
		if (a<=mid) res+=Query(l  ,mid,P[o].sl,a,b);
		if (b> mid) res+=Query(mid+1,r,P[o].sr,a,b);
		return res;
	}

	long long Query(int n,int x)
	{
		return Query(1,maxa,root[n],x,maxa);
	}
}T;

int a[maxn];
int n;
long long ans;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		ans+=T.Query(min(a[i],i-1),i);
		T.Insert(i,a[i]);
	}
	printf("%I64d\n",ans);
	return 0;
}

        另一种考虑是，先不管\(x<y\)这个条件，即找出所有的\(a[x] \geq y\)且\(a[y] \geq x\)，最后减去\(x \leq a[x]\)的数量，最后再除2。

        从1到n枚举x，可以发现满足\(a[y] \geq x\)的y是不断减少的，即只需找出满足\(y \leq a[x]\)的满足条件的y的数量即可。枚举x的过程中不断删去用不到的y即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

int lowbit(int x) {return x&-x;}

vector <int> v[maxn];
int a[maxn];
int f[maxn];
int n;
long long ans;

void Change(int x,int p)
{
	while (x<=n) f[x]+=p,x+=lowbit(x);
}

int Query(int x)
{
	int res=0;
	while (x) res+=f[x],x-=lowbit(x);
	return res;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
	{
		if (a[i]<=n) v[a[i]].push_back(i);
		Change(i,1);
	}
	for (int i=1;i<=n;i++)
	{
		ans+=Query(min(a[i],n));
		for (auto j:v[i]) Change(j,-1);
	}
	for (int i=1;i<=n;i++) if (i<=a[i]) ans--;
	printf("%I64d\n",ans/2);
	return 0;
}