博客
关于我
P1502 窗口的星星
阅读量:553 次
发布时间:2019-03-09

本文共 1743 字,大约阅读时间需要 5 分钟。

题目链接

代码

#include
#include
#include
#include
using namespace std;typedef pair
PII;const int N = 10010;vector
row;struct Line { int x, y1, y2, v; bool operator < (const Line& l) const { return x == l.x ? v > l.v : x < l.x; }}line[N << 1];struct Node { int l, r, v, lz;}tr[N << 3];inline void eval(Node& t, int k) { t.v += k; t.lz += k;}inline void push_down(int u) { eval(tr[u << 1], tr[u].lz); eval(tr[u << 1 | 1], tr[u].lz); tr[u].lz = 0;}void build(int u, int l, int r) { tr[u] = { l , r , 0, 0}; if (l != r) { int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); }}void modify(int u, int l, int r, int k) { if (l <= tr[u].l && r >= tr[u].r) eval(tr[u], k); else { push_down(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, k); if (r > mid) modify(u << 1 | 1, l, r, k); tr[u].v = tr[u << 1].v > tr[u << 1 | 1].v ? tr[u << 1].v : tr[u << 1 | 1].v; }}int find(int k) { int l = 0, r = row.size() - 1; while (l < r) { int mid = l + r >> 1; if (k <= row[mid]) r = mid; else l = mid + 1; } return l + 1;}int main() { int t; scanf("%d", &t); while (t--) { int n, w, h, ans = 0; scanf("%d%d%d", &n, &w, &h); for (int i = 0; i < n; ++i) { int x, y, v; scanf("%d%d%d", &x, &y, &v); line[i << 1] = { x, y, y + h - 1, v }; line[i << 1 | 1] = { x + w - 1, y, y + h - 1, -v }; row.push_back(y); row.push_back(y + h - 1); } sort(line, line + 2 * n); sort(row.begin(), row.end()); row.erase(unique(row.begin(), row.end()), row.end()); build(1, 1, row.size()); for (int i = 0; i < 2 * n; ++i) { modify(1, find(line[i].y1), find(line[i].y2), line[i].v); ans = ans < tr[1].v ? tr[1].v : ans; } row.clear(); printf("%d\n", ans); } return 0;}

转载地址:http://nmzpz.baihongyu.com/

你可能感兴趣的文章
MySQL 备份 Xtrabackup
查看>>
mYSQL 外键约束
查看>>
mysql 多个表关联查询查询时间长的问题
查看>>
mySQL 多个表求多个count
查看>>
mysql 多字段删除重复数据,保留最小id数据
查看>>
MySQL 多表联合查询:UNION 和 JOIN 分析
查看>>
MySQL 大数据量快速插入方法和语句优化
查看>>
mysql 如何给SQL添加索引
查看>>
mysql 字段区分大小写
查看>>
mysql 字段合并问题(group_concat)
查看>>
mysql 字段类型类型
查看>>
MySQL 字符串截取函数,字段截取,字符串截取
查看>>
MySQL 存储引擎
查看>>
mysql 存储过程 注入_mysql 视图 事务 存储过程 SQL注入
查看>>
MySQL 存储过程参数:in、out、inout
查看>>
mysql 存储过程每隔一段时间执行一次
查看>>
mysql 存在update不存在insert
查看>>
Mysql 学习总结(86)—— Mysql 的 JSON 数据类型正确使用姿势
查看>>
Mysql 学习总结(87)—— Mysql 执行计划(Explain)再总结
查看>>
Mysql 学习总结(88)—— Mysql 官方为什么不推荐用雪花 id 和 uuid 做 MySQL 主键
查看>>