「luogu3810」陌上花开
2024-10-08 12:26:51
「luogu3810」陌上花开
传送门
三维偏序, \(\text{CDQ}\) 分治板子题。
判重的地方注意一下,别的就都是板子了。
参考代码:
#include <algorithm>
#include <cstdio>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template < class T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while ('0' > c || c > '9') f |= c == '-', c = getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}
const int _ = 1e5 + 5, __ = 2e5 + 5;
int n, k, tr[__], ans[_];
inline int lb(int x) { return x & -x; }
inline void update(int x, int v)
{ for (rg int i = x; i <= k; i += lb(i)) tr[i] += v; }
inline int query(int x)
{ int res = 0; for (rg int i = x; i >= 1; i -= lb(i)) res += tr[i]; return res; }
struct node { int a, b, c, f, w; } t[_], tt[_];
inline bool cmp(const node& x, const node& y)
{ return x.a != y.a ? x.a < y.a : (x.b != y.b ? x.b < y.b : x.c < y.c); }
inline void CDQ(int l, int r) {
if (l == r) return ;
int mid = (l + r) >> 1;
CDQ(l, mid), CDQ(mid + 1, r);
int i = l, j = mid + 1, p = l;
while (i <= mid && j <= r) {
if (t[i].b <= t[j].b)
update(t[i].c, t[i].w), tt[p++] = t[i++];
else
t[j].f += query(t[j].c), tt[p++] = t[j++];
}
while (i <= mid) update(t[i].c, t[i].w), tt[p++] = t[i++];
while (j <= r) t[j].f += query(t[j].c), tt[p++] = t[j++];
for (rg int i = l; i <= mid; ++i) update(t[i].c, -t[i].w);
for (rg int i = l; i <= r; ++i) t[i] = tt[i];
}
int main() {
read(n), read(k);
for (rg int i = 1; i <= n; ++i)
read(t[i].a), read(t[i].b), read(t[i].c), t[i].w = 1;
sort(t + 1, t + n + 1, cmp);
int cnt = 1;
for (rg int i = 2; i <= n; ++i) {
if (t[i].a == t[cnt].a && t[i].b == t[cnt].b && t[i].c == t[cnt].c) ++t[cnt].w;
else t[++cnt] = t[i];
}
CDQ(1, cnt);
for (rg int i = 1; i <= cnt; ++i) ans[t[i].f + t[i].w - 1] += t[i].w;
for (rg int d = 0; d < n; ++d) printf("%d\n", ans[d]);
return 0;
}
最新文章
- [2014.01.27]wfGifAnimator 动画GIF组件 3.0
- UVALive 5058 Counting BST --组合数
- python 定义实例方法
- unity下载文件三(http异步下载)
- 关于一道简单的Java 基础面试题的剖析: short s1=1;s1 = s1 +1会报错吗?
- linux内核驱动模型
- Objective-c 字典对象
- 阿里云-对象储存OSS
- Carthage - 一个简单、去集中化的Cocoa依赖管理器
- RocketMQ(二):RPC通讯
- OpenGL实例:几何变换
- 安装tomcat9
- LCT维护删除时间最晚生成树
- NOIP2011Mayan游戏(模拟)
- huawei
- 当有多个form表单请求时如何处理?
- html5 canvas arcTo()
- excel文字格式设置
- php编写TCP服务端和客户端程序
- 【javascript】数据结构-链表