当前位置:网站首页>【集训DAY4】矩形【线段树】
【集训DAY4】矩形【线段树】
2022-08-09 22:35:00 【VL——MOESR】

思路:
我们以x轴为加入时间,y轴为坐标轴建立线段树
在x处加a[i],然后在x+w处减去a[i]。
c o d e code code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, w, h;
int s[100010], tot, cnt;
struct node {
int x, y1, y2, w;
}q[100010];
struct abc {
int maxx, l, r, flag;
}tree[400010];
bool cmp(node x, node y) {
return (x.x < y.x) || (x.x == y.x && y.w < 0);
}
void build(int k, int l, int r) {
tree[k].l = s[l], tree[k].r = s[r];
if(r - l == 1) return;
int mid = l + r >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid, r);
tree[k].maxx = max(tree[k << 1].maxx, tree[k << 1 | 1].maxx);
}
void update(int k, int x, int y, int w) {
if(x <= tree[k].l && tree[k].r <= y) {
tree[k].flag += w;
tree[k].maxx += w;
return ;
}
if(x < tree[k << 1].r) update(k << 1, x, min(y, tree[k << 1].r), w);
if(y > tree[k << 1 | 1].l) update(k << 1 | 1, max(x, tree[k << 1 | 1].l), y, w);
tree[k].maxx = max(tree[k << 1].maxx, tree[k << 1 | 1].maxx) + tree[k].flag;
}
int main() {
scanf("%d%d%d", &n, &w, &h);
for(int i = 1; i <= n; i ++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
q[++ tot].x = x, q[tot].y1 = y, q[tot].y2 = y + h, q[tot].w = z;
q[++ tot].x = x + w, q[tot].y1 = y, q[tot].y2 = y + h, q[tot].w = -z;
s[++ cnt] = y, s[++ cnt] = y + h;
}
sort(s + 1, s + 1 + cnt);
cnt = unique(s + 1, s + cnt) - s - 1;
sort(q + 1, q + 1 + tot, cmp);
build(1, 1, cnt);
int ans = 0;
for(int i = 1; i <= tot; i ++) {
update(1, q[i].y1, q[i].y2, q[i].w);
ans = max(ans, tree[1].maxx);
}
printf("%d", ans);
return 0;
}
边栏推荐
- kubesphere
- 你的手机曾经被监控过吗?
- ElasticSearcch集群
- The latest "Grain Academy Development Tutorial" in 2022: 10 - Front-end payment module
- 力扣:474.一和零
- 2022-08-09 mysql/stonedb-subquery performance improvement-introduction
- 【JZOF】82二叉树中和为某一值的路径(一)
- Interfering with BGP routing---community attributes
- tiup cluster template
- YGG 经理人杯总决赛已圆满结束,来看看这份文字版总结!
猜你喜欢

YGG 经理人杯总决赛已圆满结束,来看看这份文字版总结!

complete knapsack theory

2022年最新《谷粒学院开发教程》:10 - 前台支付模块

Comprehensive analysis of FPGA basics

你的手机曾经被监控过吗?

【Burning】It's time to show your true strength!Understand the technical highlights of the 2022 Huawei Developer Competition in one article

2020年度SaaS TOP100企业名单

外包的水有多深?腾讯15k的外包测试岗能去吗?

32 JZOF 】 【 print down on binary tree

Gartner全球集成系统市场数据追踪,超融合市场增速第一
随机推荐
Pytorch分布式训练/多卡训练DDP——模型初始化(torch.distribute 与 DDP的区别)
[Interface Test] Decoding the request body string of the requests library
Technology feast!Huayun Data brings six topics to OpenInfra Days China
How to match garbled characters regularly?
JS基础笔记-关于对象
《GB5084-2021》PDF下载
集合运算样例
完全背包理论
干货!迈向鲁棒的测试时间适应
SRv6性能测量
Gumbel distribution of discrete choice model
直播平台怎么搭建,原生js实现编辑器撤消/恢复功能
68. qt quick-qml multi-level folding drop-down navigation menu supports dynamic add/unload, support qml/widget loading, etc.
Snap: 322. Change of Change
你的手机曾经被监控过吗?
关于服务治理
Sqlserver restricts the ip under which accounts can access the database
力扣:322. 零钱兑换
多商户商城系统功能拆解25讲-平台端分销申请
Filament - Material basic graphics drawing