题:https://codeforces.com/contest/1284/problem/D

题意:给定n个1对的时间断,我是这么理解的,甲去参加a时间段的讲座,乙去参加b时间段的讲座,然后若这n对中若能挑出这样一个子集段:甲能参加第 i 个时间段的讲座而乙不能。就输出“NO”(注意,甲乙参加讲座的时间段是给定的a时间段,和b时间段,并不是同一个时间段)

分析:枚举a时间段的时间交,然后讲对应的b时间段的时间交加到线段数上,俩者的时间交数一定要相同,因为这些b区间中两两之间也必须在某点交。

   可以理解为“要么都可以去,要么都不可以去”。

#include<bits/stdc++.h>
using namespace std;
const int M=4e5+;
typedef long long ll;
#define pb push_back
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
struct tree{
int val,lazy;
}tr[M<<];
vector<int>l[M],r[M],lisan;
struct node{
int l,r,id;
}a[M],b[M];
int n;
void build(int root,int l,int r){
if(l==r){
tr[root].val=tr[root].lazy=;
return ;
}
int midd=(l+r)>>;
build(lson);
build(rson);
tr[root].val=tr[root].lazy=;
}
void pushdown(int root){
int x=tr[root].lazy;
tr[root<<].val+=x;
tr[root<<|].val+=x;
tr[root<<].lazy+=x;
tr[root<<|].lazy+=x;
tr[root].lazy=;
}
void up(int root){
tr[root].val=max(tr[root<<].val,tr[root<<|].val);
}
void update(int L,int R,int val,int root,int l,int r){
if(L<=l&&r<=R){
tr[root].val+=val;
tr[root].lazy+=val;
return ;
}
if(tr[root].lazy!=)
pushdown(root);
int midd=(l+r)>>;
if(L<=midd)
update(L,R,val,lson);
if(R>midd)
update(L,R,val,rson);
up(root);
}
int query(int L,int R,int root,int l,int r){
if(L<=l&&r<=R)
return tr[root].val;
if(tr[root].lazy!=)
pushdown(root);
int maxx=,midd=(l+r)>>;
if(L<=midd)
maxx=max(maxx,query(L,R,lson));
if(R>midd)
maxx=max(maxx,query(L,R,rson));
up(root);
return maxx;
}
bool solve(node *a,node *b){
int len=lisan.size();
build(,,len);
for(int i=;i<=len;i++)
l[i].clear(),r[i].clear();
for(int i=;i<=n;i++){
l[a[i].l].pb(i);
r[a[i].r].pb(i);
}
int countt=;
for(int i=;i<=len;i++){
for(int j=;j<l[i].size();j++){
int id=l[i][j];
int L=b[id].l,R=b[id].r;
///把所有b加上,数量要和与b匹配的a在这个区间上相交的数目countt相同
int mx=query(L,R,,,len);
if(mx!=countt)
return false;
update(L,R,,,,len);
countt++;
}
///和上面部分合起来是处理区间交的过程
for(int j=;j<r[i].size();j++){
int id=r[i][j];
int L=b[id].l,R=b[id].r;
update(L,R,-,,,len);
countt--;
}
}
return true;
}
int main(){
scanf("%d",&n);
for(int x1,x2,y1,y2,i=;i<=n;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
lisan.pb(x1),lisan.pb(y1),lisan.pb(x2),lisan.pb(y2);
a[i].l=x1,a[i].r=y1,a[i].id=i;
b[i].l=x2,b[i].r=y2,b[i].id=i;
}
sort(lisan.begin(),lisan.end());
lisan.erase(unique(lisan.begin(),lisan.end()),lisan.end());
for(int i=;i<=n;i++){
a[i].l=lower_bound(lisan.begin(),lisan.end(),a[i].l)-lisan.begin()+;
a[i].r=lower_bound(lisan.begin(),lisan.end(),a[i].r)-lisan.begin()+;
b[i].l=lower_bound(lisan.begin(),lisan.end(),b[i].l)-lisan.begin()+;
b[i].r=lower_bound(lisan.begin(),lisan.end(),b[i].r)-lisan.begin()+;
}
if(solve(a,b)&&solve(b,a))
puts("YES");
else
puts("NO");
return ;
}

最新文章

  1. [LeetCode] Ugly Number II 丑陋数之二
  2. innerHTML属性
  3. 2 Servlet基础
  4. 网页html结构右侧栏固定,左侧自适应大小。
  5. BZOJ 3439 Kpm的MC密码
  6. 解决在 MVC  局部视图中加载 ueditor 编辑器时, 编辑器加载不出的 bug
  7. JQuery焦点Table
  8. POJ 1861 Network
  9. k8s 集群基本概念
  10. 常用的meta标签
  11. 『个人の笔记』百度ife
  12. mybatis查询语句的背后
  13. Python+Selenium+Pycharm
  14. 为什么vue支持IE9以上的IE浏览器?
  15. ELK 处理 Percona 审计日志(填坑)
  16. linux 一种小的性能优化手段
  17. Unity3D研究院之将UI的点击事件渗透下去(转)
  18. 进程队列(Queue),Pipe(管道), Manager 进行进程之间的数据传递和传输
  19. jdbc连接获取表名称
  20. 笔记之分布式文件系统(DFS)

热门文章

  1. Arduino - Nano针脚分配时需要注意的事项
  2. pppd调试心得.md
  3. DAO三层架构及工厂模式
  4. iOS 保存图片(视频)到相册
  5. io流对数据的读写
  6. 科学 multi port
  7. consul集群配置
  8. localStorage中使用json
  9. python刷LeetCode:20. 有效的括号
  10. 第21章—websocket