最新要闻
- 全球今热点:功耗只有65W!14核心i5-13500偷跑:解锁到154W太生猛了
- 【环球热闻】实拍日本多地暴雪:1.6米高积雪掩埋车辆、14人死亡
- Redmi Buds 4青春版耳机亮相:单耳轻至3.9g 活力4色
- 环球快资讯:《阿凡达2》中的“海怪”:原来真的存在于地球!
- 天天快消息!男生考研分到高中母校被班主任监考:网友一句话扎心
- 天天信息:山东小伙用1个月微缩30倍农村老屋:惟妙惟肖
- 每日播报!2022年优化最差游戏榜单出炉:《巫师3》次世代版上榜
- 世界通讯!能跑虚幻5特效!Centerpiece机械键盘自带CPU+GPU
- 环球滚动:康辉被调侃为“天选打工人”:连上六天班、领带惹眼
- 世界百事通!Redmi K60首款素皮机身揭秘:参照跑车内饰 拟真缝线工艺
- 上海今起对快递外卖每人每天补贴60元 元旦春节补贴150元
- 全球观焦点:15.5小时!阿里云史上最长大规模中断:官方公告四大问题
- 不吃饭光吃补充剂 真的可以避免营养缺乏吗?
- 历时9个月 时速350高铁成功“穿海入城”
- 别再说RTX 4090功耗比A卡高了:4K 120帧仅需150W
- 简讯:权威结果出炉:今年画质最好的游戏有答案了
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
环球快资讯丨Codeforces 983 D Arkady and Rectangles 题解
(资料图片)
题目链接
挺有意思的数据结构题,题面看着像个板子,其实还是有不少学问的。
平面上一堆矩形的题目常见套路就是对\(x\)轴扫描线,\(y\)轴线段树维护,这题也不例外。我们先对坐标离散化。题目中输入的是坐标系中的顶点的坐标,为了方便维护,我们需要转换成"格子"的坐标。注意,是先离散化再转换,如果先转换再离散化会出现下面的错误:
然后从左到右扫描线,对于每一列,我们想找出这一列中所有最后仍存在、且没有被标记过的颜色,把它们计入答案,并把这些颜色都做上标记,以后不再统计。那么我们需要同时维护两堆东西:当前存在的所有颜色和当前存在的所有没标记过的颜色。一个没标记过的颜色应该被统计,当且仅当当前列存在一个位置被这个颜色覆盖,且覆盖这个位置的所有颜色中没有编号比这个颜色大的。假设现在往扫描线中加入一个颜色,它覆盖的纵坐标区间是[l,r]。我们平时做线段树区间修改[l,r]的时候会访问\(logn\)个不相交的区间,且它们的并为[l,r]。这题里我们对线段树上的每个区间维护一个set(f集合),加入一个覆盖[l,r]的颜色时就把这个颜色加入所有访问到的\(logn\)个区间的set里。再对每个区间维护一个set表示所有没标记的颜色(g集合),加入元素的时候和上一个set一样,如果标记了一个颜色就把这个set中的对应颜色都删了就行。
对于线段树上的某一个节点k,它的\(g\)集合里只有最大的一个元素可能计入答案。设这个元素为x,它能计入答案的充要条件是:从k到线段树根的所有节点的f集合的所有元素都\(\le x\);且\(k\)子树中存在一个叶子\(p\)使得从\(p\)到\(k\)路径上所有节点的f集合中的所有元素都\(\le x\)。
然后对线段树中的每个点k维护\(mx_k\)表示它的子树中到现在为止满足上面说的所有条件的最大的可能被计入答案的值(在往上pushup的时候还要经受上方节点f集合中元素的考验);\(mnlim_k\)表示子树中最优的叶子\(p\)(也就是p到k的路径上所有点f集合元素的最大值最小)。如果搞清楚了以上定义,如何pushup已经显然了。具体见代码。
时间复杂度\(O(nlog^2n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_back#define x1 x114#define y1 y114#define x2 x514#define y2 y514void fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;void chmax(int &x,int y){if(x > op[200010];vector dscx,dscy;namespace st{ int n2=1,mx[800010],mnlim[800010]; set all[800010],cand[800010]; void pushUp(int k,bool isLeaf) { if(isLeaf) { if(cand[k].empty()) mx[k]=-1; else mx[k]=(*cand[k].rbegin()==*all[k].rbegin() ? *cand[k].rbegin():-1); if(all[k].empty()) mnlim[k]=-1;else mnlim[k]=*all[k].rbegin(); } else { int curlim=(all[k].empty() ? -1:*all[k].rbegin()); mnlim[k]=min(mnlim[k+k+1],mnlim[k+k+2]);chmax(mnlim[k],curlim); mx[k]=-1; if(mx[k+k+1]>=curlim) chmax(mx[k],mx[k+k+1]);if(mx[k+k+2]>=curlim) chmax(mx[k],mx[k+k+2]); if(!cand[k].empty()&&*cand[k].rbegin()>=mnlim[k]) chmax(mx[k],*cand[k].rbegin()); } } void upd(int k,int lb,int ub,int tlb,int tub,int w,int val) { if(ub>n; rep(i,n) { scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]); dscx.pb(x1[i]);dscx.pb(x2[i]);dscy.pb(y1[i]);dscy.pb(y2[i]); } sort(dscx.begin(),dscx.end());dscx.erase(unique(dscx.begin(),dscx.end()),dscx.end()); sort(dscy.begin(),dscy.end());dscy.erase(unique(dscy.begin(),dscy.end()),dscy.end()); rep(i,n) { x1[i]=lower_bound(dscx.begin(),dscx.end(),x1[i])-dscx.begin();x2[i]=lower_bound(dscx.begin(),dscx.end(),x2[i])-dscx.begin(); y1[i]=lower_bound(dscy.begin(),dscy.end(),y1[i])-dscy.begin();y2[i]=lower_bound(dscy.begin(),dscy.end(),y2[i])-dscy.begin(); --x2[i];--y2[i]; op[x1[i]].pb(mpr(mpr(y1[i],y2[i]),mpr(1,i))); op[x2[i]+1].pb(mpr(mpr(y1[i],y2[i]),mpr(-1,i))); } while(st::n2-1) { ++ans; int val=st::mx[0]; st::del(0,0,st::n2-1,y1[val],y2[val],val); } } cout<
-
环球快资讯丨Codeforces 983 D Arkady and Rectangles 题解
题目链接挺有意思的数据结构题,题面看着像个板子,其实还是有不少学问的。平面上一堆矩形的题目常见套...
来源: -
【新视野】PHP Composer 虚拟依赖包 - 实现按需载入钉钉对应功能模块的 php sdk
难得钉钉官方提供了完整的apisdk,各种语言的版本的都有,而且api覆盖面非常完整。但是,composer安装下...
来源: 环球快资讯丨Codeforces 983 D Arkady and Rectangles 题解
全球今热点:功耗只有65W!14核心i5-13500偷跑:解锁到154W太生猛了
全球视点!教你用JavaScript实现调皮的字母
【新视野】PHP Composer 虚拟依赖包 - 实现按需载入钉钉对应功能模块的 php sdk
全球新动态:Safari浏览器对SVG中的
标签支持不友好,渲染容易错位 【环球热闻】实拍日本多地暴雪:1.6米高积雪掩埋车辆、14人死亡
Redmi Buds 4青春版耳机亮相:单耳轻至3.9g 活力4色
环球快资讯:《阿凡达2》中的“海怪”:原来真的存在于地球!
AcWing241. 楼兰图腾
天天速递!CentOS7配置静态IP
天天快消息!男生考研分到高中母校被班主任监考:网友一句话扎心
天天信息:山东小伙用1个月微缩30倍农村老屋:惟妙惟肖
MAUI新生6.1-Shell导航视觉层次结构
每日播报!2022年优化最差游戏榜单出炉:《巫师3》次世代版上榜
世界通讯!能跑虚幻5特效!Centerpiece机械键盘自带CPU+GPU
环球滚动:康辉被调侃为“天选打工人”:连上六天班、领带惹眼
世界百事通!Redmi K60首款素皮机身揭秘:参照跑车内饰 拟真缝线工艺
上海今起对快递外卖每人每天补贴60元 元旦春节补贴150元
全球观焦点:15.5小时!阿里云史上最长大规模中断:官方公告四大问题
不吃饭光吃补充剂 真的可以避免营养缺乏吗?
历时9个月 时速350高铁成功“穿海入城”
别再说RTX 4090功耗比A卡高了:4K 120帧仅需150W
简讯:权威结果出炉:今年画质最好的游戏有答案了
炉石关服前夕:网易同类卡牌游戏《秘境对决》宣布恢复运营
今日最新!洛谷 P5721 【入门3】循环结构
【pygame游戏】用Python实现一个蔡徐坤大战篮球的小游戏,可还行?【附源码】
环球热议:大货车雪地滑坡 山东小伙神操作“拔草相助”!后续令网友感动
超长寿命TLC闪存 金邦2TB PCIe 4.0硬盘679元:5GB/s速度
热门:再不努力就要归零 2nm工艺成日本半导体最后的机会
教你用JavaScript实现搜索展开
天天新资讯:李斌:创业的没有几个真的是骗子 要多鼓励
AMD 8年真身接连被破 Intel 13代酷睿“开挂“:超频无敌了
【焦点热闻】索尼被质疑虚假宣传:上市两年后 PS5仍不支持8K
中国千年酒文化传承 酒祖杜康白酒大促:礼盒装110两瓶
今日聚焦!李斌再回应蔚来数据泄露:会承担所有责任 哪怕破产也不妥协
环球微动态丨「杂题乱写」AtCoderDP26 题
(二)elasticsearch 源码目录
【新视野】碳纤维纹理后盖!Redmi K60回归硬核设计:刀锋战士理念
速看:无惧严寒!网易严选牛奶绒床品四件套:159元起
新的全国铁路列车运行图实行:石家庄至北京将实现一小时通达
新版以太坊Ethereum库ethersV5.0配合后端Golang1.18实时链接区块链钱包(Metamask/Okc)以及验签操作
环球关注:高速上飞来钢管插进驾驶室:差点害死驾驶员
热消息:联想:小红点会在ThinkPad笔记本上永远存在
天天头条:正式发布前 盒装RTX 4070 Ti线下偷跑:售价感人
天天热资讯!保时捷为Taycan推出全新充电器:充电速度提升一倍 改装费用上万
环球通讯!Epic喜加一!免费送大作《地铁》:下款将是《死亡搁浅》
每日头条!2023考研报告发布:“逆向考研”成亮点!附报告源文
世界快播:锐龙7000系列三款非X型号曝光:价格感受下
囧!日本老师暴打初二男生 因学“左手定则”时比中指
老人故意推倒摩托车损坏被抓:车主回应希望判决不手软 惯犯了
焦点速递!Sentinel的规则
天天热议:一加11下周官宣:安卓性能天花板
MAUI新生5.3-Layout布局类控件难点
国产OS统信UOS家庭版22.0明年1月发布:免费用1年 可与Windows共存
全靠移民硬撑?美国人口增长率仍贴近历史低位
视点!18岁女生因焦虑2个月减25斤:最终瘦成95斤
天天消息!男子无聊送外卖发现2小时挣150:开豪车也干
天天精选!Kubernetes监控手册03-宿主监控实操
今日观点!一路用到安卓17?OPPO将提供4年ColorOS重大更新
环球即时看!同价位罕见!雷军:Redmi K60系列这三款全都上2K直屏
微资讯!“联盟号”发生泄漏:俄罗斯或派遣救援飞船接回机组人员
世界播报:cmake-4
Redmi可穿戴新品公布:手表、耳机全都有
行业最快!红魔8 Pro系列搭载520Hz游戏体感肩键:毫秒级触控响应
《阿凡达2:水之道》国内票房突破6亿:卡梅隆光环褪色 回本太难
每日焦点!终结起火、爆炸困扰!红旗全固态电芯试制完成:10Ah级大容量
27款笔记软件的介绍
全球视点!ts10_使用webpack打包ts文件3
环球今日报丨C#封装GRPC类库及调用简单实例
百事通!Spring IOC官方文档学习笔记(四)之依赖项(下)
【天天报资讯】Web 标准 & W3C 规范
今日热闻!研究人员在柬埔寨发现超级蚊子:对杀虫剂免疫
焦点关注:C++基础3
焦点滚动:惧怕《阿凡达2》 输不起?郭帆回应《流浪地球2》撤档 春节见
播报:Redmi K60全系标配2K柔性屏 专家:国产技术已破局超越
环球即时看!以小博大外小内大,Db数据库SQL优化之小数据驱动大数据
全球快资讯丨最高799元 迪士尼再发布涨价公告:开业以来已涨4次
质感一绝!一加11证件照公布:双曲面屏、流动天阶设计
速递!共计100小时:全球首架C919自12月26日起验证飞行
ts09_使用webpack打包ts文件2
环球热头条丨2022贺岁档票房破10亿!《阿凡达:水之道》5.9亿元能拯救院线吗
曾因“双标”遭网友痛批:好丽友旗舰店发布闭店公告
全球热头条丨AcWing1134/洛谷P1144 最短路计数
WPF开发之Prism详解【内附源码】
不愧是宝马 因机油渗漏:近500台S1000系列摩托车被召回
最新快讯!Codeforces 1097 G Vladislav and a Great Legend 题解 (DP)
焦点日报:肾脏衰竭 球王贝利病情继续恶化:家人开始筹备葬礼
02.关于线程你必须知道的8个问题(上)
当前头条:喜提安卓13!小米平板5/Pro 12.4推送MIUI 14开发版:支持光子引擎
每日热文:SSD/内存白菜价难持续:国产厂商被制裁 三星等大厂减产提价
天天热点!我的2022年个人总结
环球焦点!FreeSWITCH学习笔记:EventSocket
AMD RX7900被吐槽空气卡 溢价千元普遍:国内用户持币等 买它还是4080?
【世界播资讯】小米又一爆款诞生!小米净水器销量破500万台
热推荐:新冠后丧失嗅觉的关键原因找到了 科学家:长期失灵也能恢复
环球通讯!3199元起 爱奇艺奇遇MIX VR一体机发布:4K级3000吋巨幕 支持Steam串流
焦点快播:趁早加满!下轮国内油价上调几成定局
影驰发布全球第三款8GHz DDR5内存:如此"光污染" 绝了
焦点速讯:电解质水到底有没有用?我来告诉你
美国人预期寿命降至25年来最低:三大因素导致一半的死亡