开始以为是什么神仙数据结构题，不可做，一看题解发现完全可做。还是得坚持自己想啊。

题目简化一下就是

给定一个序列 $a$, 求

$\sum_{i=1}^n \sum_{j=i+1}^{a_i} \left[ a_j \ge i\right]$

然后一看又是一段区间的又是一段数的，就以为是树套树或者可持久化之类的玩意儿，然后发现最普通的树状数组就可以解决。

总结一下限制大概有三个：

1. $j \le a_i$
2. $i < j$
3. $i \le a_j$

那么我们可以用排序来解决掉其中的一维，直接按照顺序就可以去掉 $2$ 这一条限制。然后我们再把这个数组复制一份，给按照 $a_i$ 排个序，每次扫到一个 $i$ 的时候，就把小于 $i$ 的 $a_j$ 都给去掉，这样就解决了第三条限制，然后在用权值树状数组解决第一条限制就可以了。

可这题的数据范围是 $10^9$ 次的，权值树状数组能直接做吗？其实是可以的，因为大于 $n$ 的 $a_i$ 在后续的比较中永远是大的那个，所以直接当做 $n$ 来处理就可以了。

代码：

#include <cstdio>
#include <algorithm>
#define int long long
const int N = 200005;
int a[N], t[N], n, ans;
bool del[N];
struct twt {
	int x, a;
	bool operator < (twt b) const {
		return a < b.a;
	}
} p[N];
void add(int x, int f) {
	for(int i = x; i <= n; i += i&-i) t[i] += f;
}
int query(int x) {
	int an = 0;
	for(int i = x; i >= 1; i -= i&-i) an += t[i];
	return an;
}
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		a[i] = std::min(a[i], n);
		p[i].a = a[i], p[i].x = i;
		add(i, 1);
	}
	std::sort(p+1, p+1+n);
	int now = 1;
	for(int i = 1; i <= n; i++) {
		if(!del[i]) del[i] = 1, add(i, -1);
		while(now <= n && p[now].a < i) {
			if(!del[p[now].x]) add(p[now].x, -1), del[p[now].x] = 1;
			++ now;
		}
		ans += query(a[i]);
	}
	printf("%lld", ans);
	return 0;
}

很多看似复杂的问题也是可做的，一定要独立去做过啊！