社区讨论
再求玄学复杂度
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-三体(不忘初心)
回复
共 2 条回复,欢迎继续交流。
正在加载回复...