CF1491A K-th Largest Value 题解

Content

你有一个长度为 \(n\)，并且仅包含 \(0/1\) 的数组 \(a\)。现在对这个序列做以下两种操作之一共 \(q\) 次：

\(1\) \(x\)：将 \(a_x\) 修改为 \(1-a_x\)。
\(2\) \(k\)：查询这个数组的第 \(k\) 大数。

对于每次操作 \(2\)，输出答案。

数据范围：\(1\leqslant n,q\leqslant 10^5\)。

Solution

乍一看需要什么数据结构，其实不需要。

由于这个数组仅有 \(0\) 或 \(1\)。因此我们很容易想到查询第 \(k\) 大数的判断：如果当前数组里面 \(1\) 的个数 \(\geqslant k\)，那么这个序列的第 \(k\) 大数是 \(1\)，否则就是 \(0\)。理由很容易想清楚，这里不再多解释。至于修改操作直接模拟就好了。

同时，我们开两个计数器用来统计当前数组的 \(0\) 和 \(1\) 的个数，初始化为输入的数组中 \(0\) 和 \(1\) 的个数，随每次修改操作改变。具体来说，如果要修改的是 \(1\)，那么 \(1\) 的个数减 \(1\)，\(0\) 的个数加 \(1\)；修改的是 \(0\)，就把 \(0\) 的个数减 \(1\)，\(1\) 的个数加 \(1\)。总之就是一句话：修改谁，就把谁的个数减 \(1\)，另外一个数的个数加 \(1\)。

若还有不懂的地方可以参考一下下面给出的代码实现。

Code

int n, m, a[100007], num0, num1;

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	n = Rint, m = Rint;

	F(i, 1, n) {

		a[i] = Rint;

		num0 += (a[i] == 0), num1 += (a[i] == 1);

	}

	while(m--) {

		int op = Rint, x = Rint;

		if(op == 1) {

			if(a[x]) num1--, num0++;

			else num0--, num1++;

			a[x] = 1 - a[x];

		} else printf("%d\n", x <= num1 ? 1 : 0);

	}

	return 0;

}

巴特西

CF1491A K-th Largest Value 题解

Content

Solution

Code

最新文章

热门文章