本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-28 20:40:56

题意

给你一个数组，求 $i,j$ 满足：

• $1 \le x < y \le n$
• $y \le a_x$
• $x \le a_y$

题解思路

读入的时候，因为 $j \le n$ 所以当 $a_i > n$ 时，我们把 $a_i$ 变成 $n$ 就可以了。

然后我们可以用一个 vector 来维护 $(1)$ 和 $(3)$ 的最大可能值。

那么我们设 $v_i$ 表示最大可能为 $i$ 的数的下标是多少。

那么最大可能值就是 $i - 1$ 与 $a_i$ 取个最小值就行了。

因为 $x \le a_y$ 所以一种最大的可能就是 $x=a_y$，另一种就是 $i - 1$，因为 $x < y$ 所以 $x$ 的最大值就是 $y - 1$。

然后就枚举 $i$，然后对于每个 $i$ 枚举对应的 $v_i$，然后答案就加上 $i - \sum_{a_i < v_j}$。

AC CODE:

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int &read(int &r){\/\/快读
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
int n;
int a[N];
vector<int> v[N];\/\/表示i最大的x是多少
template<class T>
struct BIT {\/\/树状数组模板
	T c[N];
	void modify(int x, T d) {
		if (x <= 0) return;
		for (; x <= n; x += (x & -x))
			c[x] += d;
	}
	T query(int x) {
		T res = 0;
		for (; x; x -= (x & -x))
			res += c[x];
		return res;
	}
};
BIT<ll> c;
int main() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
		a[i] = min(a[i], n);
		v[min(i - 1, a[i])].push_back(i);
		\/\/因为要满足i>j那么i最大就是j-1,且i<=a[j]，所以还要与a[j]取个最小值
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		c.modify(a[i], 1);
		for (auto t : v[i]) {
			ans += i - c.query(t - 1);\/\/答案加上总数- x<a[x]的数的个数
		}
	}
	printf("%lld\n", ans);
	return 0;
}