CF848C Goodbye Souvenir

CF848C Goodbye Souvenir

cdq分治求动态二维数点

先考虑答案，对于一种颜色 \(c\)，假设出现位置集合为 \(S\)，每个位置的前继记为 \(pre_i\)，那么可以写成：

如果不修改，可以看到题目求的就是矩形横坐标 \([1,R]\) 到纵坐标 \([L,n]\) 的矩形中 \((i,pre_i)\) 的点的权值和，每个点的权值形如 \(i-pre_i\)。可以用静态二维数点完成。

加了修改，我们只需要加入一维静态的时间戳，就可以将动态二维数点问题转化为三维偏序，那么可以用 cdq 分治完成。

但是这题我最想说的其实是预处理时查询前继后继问题。可以用 set 维护，用指针可以轻松查找位置，我不会。

复杂度 \(O(n\log^2n)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
/*

*/
const int N = 1e5 + 10;
i64 n, q, m, cnt;
std::set<int> S[N];
struct node {
	i64 x, y, op, f;
} a[N << 3];
bool cmp(node a, node b) {
	return a.x < b.x;
}
i64 c[N], ans[N], b[N];
int lowbit(int x) {return x & (-x);}
void add(int x, i64 y) {
	for(int i = x; i <= n; i += lowbit(i)) b[i] += y;
}
i64 qry(int x) {
	i64 ret = 0;
	for(int i = x; i; i -= lowbit(i)) ret += b[i];
	return ret;
} 
void cdq(int l, int r) {
	if(l == r) return;
	int mid = (l + r) >> 1;
	cdq(l, mid), cdq(mid + 1, r);
	std::sort(a + l, a + mid + 1, cmp), std::sort(a + mid + 1, a + r + 1, cmp);
	int ls = l;
	for(int i = mid + 1; i <= r; i++) {
		if(a[i].op) {
			while(ls <= mid && a[ls].x <= a[i].x) {
				if(!a[ls].op) add(a[ls].y, (a[ls].x - a[ls].y) * a[ls].f);
				ls++;
			}
			ans[a[i].op] += qry(n) - qry(a[i].y - 1);
		}
	}
	for(int i = l; i < ls; i++) {
		if(!a[i].op) add(a[i].y, -(a[i].x - a[i].y) * a[i].f);
	}
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n >> q;

	for(int i = 1; i <= n; i++) {
		std::cin >> c[i];
		if(S[c[i]].size()) {
			a[++m] = {i, *S[c[i]].rbegin(), 0, 1};
		}
		S[c[i]].insert(i);
	}

	for(int i = 1; i <= q; i++) {
		int op, l, r;
		std::cin >> op >> l >> r;
		if(op == 2) a[++m] = {r, l, ++cnt, 0};
		else {
			auto p = S[c[l]].find(l);
			int pre = 0, suf = 0;
			if(p != S[c[l]].begin()) {
				a[++m] = {l, pre = *--p, 0, -1}, ++p;
			}
			if(++p != S[c[l]].end()) {
				a[++m] = {suf = *p, l, 0, -1};
			}
			if(pre && suf) {
				a[++m] = {suf, pre, 0, 1};
			}
			S[c[l]].erase(l);

			S[c[l] = r].insert(l); 
			p = S[c[l]].find(l), pre = suf = 0;
			if(p != S[c[l]].begin()) {
				a[++m] = {l, pre = *--p, 0, 1}, ++p;
			}
			if(++p != S[c[l]].end()) {
				a[++m] = {suf = *p, l, 0, 1};
			}
			if(pre && suf) {
				a[++m] = {suf, pre, 0, -1};
			}
		}
	}

	cdq(1, m);

	for(int i = 1; i <= cnt; i++) std::cout << ans[i] << "\n";

	return 0;
}