社区讨论

求调

LLouis_lxy
灌水区参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lxzykong
此快照首次捕获于
2024/06/29 18:07
2 年前
此快照最后确认于
2024/06/29 21:02
2 年前
查看原帖
今天的比赛T2求调或证明思路错误
我的思路是这样的，题目易得是求所有大于它的数减掉它的和，因此考虑维护所有大于它的数的和。然后用权值树状数组求出有多少大于它的数。用和减去数量乘它的积。得到的就是结果，但是subtesk1错了4个，其他都错1个，导致爆0，好奇是思路错误还是代码细节问题。
CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 1;
int n, q, sum, c[N];
int s[N], cnt[N];

void update1(int u, int k) { for (; u <= n; u += u & -u) s[u] += k; }

void update2(int u, int k) { for (; u <= n; u += u & -u) cnt[u] += k; }

int getsum1(int u)
{
	int sum = 0;
	for (; u; u -= u & -u) sum += s[u];
	return sum;
}

int getsum2(int u)
{
	int s = 0;
	for (; u; u -= u & -u) s += cnt[u];
	return s;
}

int main()
{
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; ++i) { int a; scanf("%d", &a); ++c[a]; }
	for (int i = 0; i <= n; ++i) if (c[i]) update1(c[i], c[i]), update2(c[i], 1), ++sum;
	while (q--)
	{
		int op, x;
		scanf("%d %d", &op, &x);
		if (op == 1 && c[x] == 0) ++c[x], update1(c[x], c[x]), update2(c[x], 1), ++sum;
		else if (op == 2 && c[x] == 1) update1(c[x], -c[x]), update2(c[x], -1), --c[x], --sum;
		else if (op == 1) ++c[x], update1(c[x], c[x]), update1(c[x] - 1, -(c[x] - 1)), update2(c[x], 1), update2(c[x] - 1, -1);
		else if (op == 2) update1(c[x], -c[x]), update1(c[x] - 1, c[x] - 1), update2(c[x], -1), update2(c[x] - 1, 1), --c[x];
		else printf("%d\n", max(getsum1(n) - getsum1(x) - (sum - getsum2(x)) * x, 0));
	}
}

回复

共 6 条回复，欢迎继续交流。

正在加载回复...