Description

有 \(n\) 个球排在一起，每个球有颜色 \(a_i\)，若当前有 \(k\) 个球，则会将所有 \(a_i=k\) 的球删掉。有 \(m\) 次查询，每次将 \(a_x\) 修改为 \(y\) ，问至少更改几个球可以使得删完所有球。

\(n,m\le 2\times 10^5\)

Solution

写发题解加深印象。

有一个结论，因为我懒，所以搬一下小粉兔的：

然后你就可以直接维护了。

Code

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define MAXN 200005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,a[MAXN],C[MAXN],_S[MAXN << 1],*S = _S + MAXN;

signed main(){

	read (n,m);

	for (Int i = 1;i <= n;++ i) read (a[i]),C[a[i]] ++;

	for (Int i = 1;i <= n;++ i) S[i] ++,S[i - C[i]] --;int ans = 0;

	for (Int i = n;i >= -n;-- i) S[i] += S[i + 1],ans += i > 0 && S[i] == 0;

	while (m --> 0){

		int x,y;read (x,y);

		-- C[a[x]];

		if (!-- S[a[x] - C[a[x]]] && a[x] - C[a[x]] > 0) ans ++;

		if (!S[y - C[y]] ++ && y - C[y] > 0) ans --;

		++ C[y],a[x] = y,write (ans),putchar ('\n');

	}

	return 0;

}

巴特西

题解 [AGC017C] Snuke and Spells

Description

Solution

Code

最新文章

热门文章