社区讨论

再求玄学复杂度

P3810【模板】三维偏序 / 陌上花开参与者 3已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@m57wl557
此快照首次捕获于
2024/12/28 16:11
去年
此快照最后确认于
2024/12/28 19:58
去年
查看原帖
CPP
#include <iostream>
#include <unordered_map>
using namespace std;
int n, k, a[100005], b[100005], c[100005], ans[100000];
unordered_map <int, unordered_map<int, unordered_map<int, int> > > tree;
int lowbit(int x)
{
	return x & -x;
}
void update(int nowx, int nowy, int nowz, int c)
{
	for (int nx = nowx;nx <= k;nx += lowbit(nx))
	{
		for (int ny = nowy;ny <= k;ny += lowbit(ny))
		{
			for (int nz = nowz;nz <= k;nz += lowbit(nz))
			{
				tree[nx][ny][nz] += c;
			}
		}
	}
	return;
}
int query(int nowx, int nowy, int nowz)
{
	int ans = 0;
	for (int nx = nowx;nx;nx -= lowbit(nx))
	{
		for (int ny = nowy;ny;ny -= lowbit(ny))
		{
			for (int nz = nowz;nz;nz -= lowbit(nz))
			{
				ans += tree[nx][ny][nz];
			}
		}
	}
	return ans;
}
int main()
{
	cin.tie(0)->ios::sync_with_stdio(false);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 1;i <= n;i++)
	{
		cin >> a[i] >> b[i] >> c[i];
		update(a[i], b[i], c[i], 1);
	}
	for (int i = 1;i <= n;i++)
	{
		ans[query(a[i], b[i], c[i]) - 1]++;
	}
	for (int i = 0;i < n;i++)
	{
		cout << ans[i] << "\n";
	}
	return 0;
}
换个地方继续当21-三体(不忘初心)
AC3+TLE7=30ptsAC_3+TLE_7=30pts

回复

2 条回复,欢迎继续交流。

正在加载回复...