博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[洛谷P2161][SHOI2009]会场预约
阅读量:6786 次
发布时间:2019-06-26

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

题目大意:有两种操作:

  1. $A\;l\;r:$表示加入区间$[l,r]$,并把与之冲突的区间删除,输出删除的区间的个数,区间$A$于区间$B$冲突当且仅当$A\cap B\not=\varnothing$
  2. $B:$输出现在有几个区间

题解:用$STL$的$set$,定义区间$A<B$为$A.r<B.l$,这样寻找冲突的区间只需要在$set$中$find$即可,注意删除后$set$指针不可用,需要重新找

卡点:

 

C++ Code:

#include 
#include
int n;struct Interval { int l, r; inline Interval() {} inline Interval(int __l, int __r) : l(__l), r(__r) {} inline friend bool operator < (const Interval &lhs, const Interval &rhs) { return lhs.r < rhs.l; }} ;std::set
S;int main() { scanf("%d", &n); while (n --> 0) { char op; scanf("%1s", &op); if (op == 'A') { int a, b, res = 0; scanf("%d%d", &a, &b); Interval now(a, b); std::set
::iterator it = S.find(now); while (it != S.end()) { S.erase(it); res++; it = S.find(now); } S.insert(now); printf("%d\n", res); } else printf("%llu\n", S.size()); } return 0;}

  

转载于:https://www.cnblogs.com/Memory-of-winter/p/10172567.html

你可能感兴趣的文章
HTML5与CSS3基础教程第八版学习笔记11~15章
查看>>
Redis -- 过期时间 和 缓存 例子
查看>>
babel7-按需加载polyfill
查看>>
Android 权限设置大全1
查看>>
Android eclipse中程序调试
查看>>
博客园博客兼容手机浏览
查看>>
第7题——买苹果
查看>>
disruptor架构四 多生产者多消费者执行
查看>>
C# - 什么是事件绑定?
查看>>
HDU-Fish买电脑 二分查找
查看>>
Rzagovori 贪心
查看>>
LTE第一章 介绍
查看>>
Scala基础篇-04 try表达式
查看>>
java日期格式(年月日时分秒毫秒)
查看>>
linux nohup后台运行命令
查看>>
[SDOI2017]天才黑客
查看>>
怎样控制竞价点击价格
查看>>
hbase 学习(十六)系统架构图
查看>>
sqlserver数据存储
查看>>
进行app性能和安全性测试的重要性
查看>>