HDU 5997 rausen loves cakes（启发式合并 + 树状数组统计答案）

题目链接 rausen loves cakes

题意给出一个序列和若干次修改和查询。修改为把序列中所有颜色为$x$的修改为$y$，

查询为询问当前$[x, y]$对应的区间中有多少连续颜色段。

　　序列长度为$n$，总操作数为$q$，满足$1 <= n <= 10^{5}, 1 <= q <= 10^{5}$

初始化的时候若当前颜色和前一个位置的颜色不相等的时候则在这个位置的树状数组中打标记。

修改的时候，颜色权值数小的往大的合并，这样满足总合并复杂度为$O(nlogn)$，

若当前位置经过修改之后和前一个位置颜色相等则取消当前位置的标记，

若当前位置经过修改之后和后一个位置颜色相等则取消当前位置的后一个位置的标记，

注意最后统计答案的时候第要对第一个位置特判。

因为用到了set，所以总时间复杂度$O(nlog^{2}n)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const int N = 1e5 + 10;

const int M = 1e6 + 10;

int T;

int ans;

int n, m;

int a[N], f[M];

int c[N];

set <int> s[M];

void update(int x, int val){

	for (; x <= n; x += x & -x) c[x] += val;

}

int query(int x){

	if (x < 1) return 0;

	int ret = 0;

	for (; x; x -= x & -x) ret += c[x];

	return ret;

}

void solve(int x, int y){

	for (auto u : s[x]){

		if (a[u - 1] == y) update(u, -1);

		if (a[u + 1] == y) update(u + 1, -1);

		s[y].insert(u);

	}

	for (auto u : s[x]) a[u] = y;

	s[x].clear();

}

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d%d", &n, &m);

		rep(i, 1, n) scanf("%d", a + i);

		memset(f, 0, sizeof f);

		memset(c, 0, sizeof c);

		rep(i, 0, 1e6 + 1) s[i].clear();

		rep(i, 1, n){

			f[a[i]] = a[i];

			if (a[i] ^ a[i - 1]) update(i, 1);

			s[a[i]].insert(i);

		}

		rep(i, 1, m){

			int op, x, y;

			scanf("%d", &op);

			if (op == 1){

				int x, y;

				scanf("%d%d", &x, &y);

				if (x == y) continue;

				if (s[f[x]].size() > s[f[y]].size()) swap(f[x], f[y]);

				x = f[x], y = f[y];

				solve(x, y);

			}

			else{

				int x, y;

				scanf("%d%d", &x, &y);

				printf("%d\n", query(y) - query(x - 1) + (a[x] == a[x - 1]));

			}

		}

	}

	return 0;

}

巴特西

HDU 5997 rausen loves cakes（启发式合并 + 树状数组统计答案）

最新文章

热门文章