CF641E 题解

前言

题目传送门！

更好的阅读体验？

非常套路的 cdq 分治。

思路

把所有操作统一存下来。将 \(x\) 离散化。

\(i\) 能被 \(j\) 统计，前提是 \(a_i\) 的操作时间早于 \(a_j\)。

然后分操作即可。具体参照代码。

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct Data {int op, time, val, id;} a[N], t[N];
int cnt[N], ans[N];
void MergeSort(int l, int r)
{
	if (l >= r) return;
	int mid = (l + r) >> 1;
	MergeSort(l, mid), MergeSort(mid + 1, r);
	int i = l, j = mid + 1, cur = 0;
	while (i <= mid && j <= r)
		if (a[i].time <= a[j].time)
		{
			if (a[i].op == 1) cnt[a[i].val]++;
			if (a[i].op == 2) cnt[a[i].val]--;
			t[++cur] = a[i], i++;
		}
		else
		{
			if (a[j].op == 3) ans[a[j].id] += cnt[a[j].val];
			t[++cur] = a[j], j++;
		}
	while (i <= mid)
	{
		if (a[i].op == 1) cnt[a[i].val]++;
		if (a[i].op == 2) cnt[a[i].val]--;
		t[++cur] = a[i], i++;
	}
	while (j <= r)
	{
		if (a[j].op == 3) ans[a[j].id] += cnt[a[j].val];
		t[++cur] = a[j], j++;
	}
	for (int i = l; i <= mid; i++) cnt[a[i].val] = 0;
	for (int i = l, j = 1; j <= cur; i++, j++) a[i] = t[j];
}
int unq[N]; //离散化 
int main()
{
	int n, q = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d%d", &a[i].op, &a[i].time, &a[i].val);
		unq[i] = a[i].val, a[i].id = (a[i].op == 3 ? ++q : 0);
	}
	sort(unq + 1, unq + n + 1); //离散化ing 
	int m = unique(unq + 1, unq + n + 1) - unq + 1;
	for (int i = 1; i <= n; i++) a[i].val = lower_bound(unq + 1, unq + m + 1, a[i].val) - unq;
	MergeSort(1, n);
	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;
}

希望能帮助到大家！