CF961E Tufurama题解

SunnyYuan的博客 / 2023-05-14 / 原文

我们维护一个存储下标数据的树状数组，先将 \(1\sim n\) 插入树状数组。
用 \(a\) 表示原数组，\(b\) 表示按照 \(a_i\) 排序后的数组。
我们从 \(1\) 开始统计，直到 \(n\)，统计时：
- 将 \(i\) 删除，不能把自己算进去。
- 为了排除 \(a_j < i\) 的部分，可以从前往后扫描 \(b\)，一直删，直到 \(b_{\text{cur}} \geq i\)，
  
  因为 \(b\) 单调不下降，所以 \(i\) 都用不着了， \(i + 1\) 也用不着了。
- 调查 \(a_i \geq j\) 的部分，调用 \(\text{query}(a_i)\) 即可。
- 注意：排除的时候用 \(b\)，这样就不用遍历整个 \(a\) 数组来排除 \(a_j < i\) 的部分；
  
  而询问的时候要用 \(a\)，因为询问的是 \(a_i \geq j\) 的部分。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using i64 = long long;

const int N = 200010;

int tr[N];

void add(int x, int v) {
	for (; x < N; x += x & -x) tr[x] += v;
}

int ask(int x) {
	int res = 0;
	for (; x; x -= x & -x) res += tr[x];
	return res; 
}

int n;
int a[N];

struct Node {
	int id;
	int v;
}b[N];

bool del[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i].id = i;
		b[i].v = a[i];
	}
	for (int i = 1; i <= n; i++) add(i, 1);
	sort(b + 1, b + n + 1, [](const Node& a, const Node& b) { return a.v < b.v; });
	int cur = 1;
	i64 ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!del[i]) del[i] ^= 1, add(i, -1);
		while (b[cur].v < i && cur <= n) {
			if (!del[b[cur].id]) del[b[cur].id] ^= 1, add(b[cur].id, -1);
			cur++;
		}
		ans += ask(min(n, a[i]));
	}
	cout << ans << '\n';
	return 0;
}