当前位置:网站首页>729. 我的日程安排表 I(set or 动态开点线段树)
729. 我的日程安排表 I(set or 动态开点线段树)
2022-07-06 04:11:00 【Harris-H】
729. 我的日程安排表 I(set or 动态开点线段树)
区间覆盖,区间查询。因此值域大,查询次数小,所以动态开点。
建树方法与普通线段树类似,就是pushdown的时候特判下左右儿子是否位空,然后所有函数都用指针即可。
时间复杂度: O ( n l o g C ) O(nlogC) O(nlogC)
class MyCalendar {
public:
struct node{
node *l,*r;
int s,lz;
};
node * rt = new node();
const int NN = 1e9;
MyCalendar() {
}
void re(node* a){
a->s=a->l->s|a->r->s;
}
void pd(node* a){
if(a->l==NULL) a->l= new node();
if(a->r==NULL) a->r= new node();
if(!a->lz) return;
a->l->s=a->lz;
a->r->s=a->lz;
a->l->lz=a->r->lz=a->lz;
a->lz=0;
}
void upd(node *a,int l,int r,int L,int R,int v){
if(l>=L&&r<=R){
a->s=v;
a->lz=v;return;
}
pd(a);
int m = l+r>>1;
if(L<=m) upd(a->l,l,m,L,R,v);
if(R>m) upd(a->r,m+1,r,L,R,v);
re(a);
}
bool que(node *a,int l,int r,int L,int R){
if(l>=L&&r<=R) return a->s;
int m = l+r>>1;
pd(a);
int ok=0;
if(L<=m) ok|=que(a->l,l,m,L,R);
if(R>m) ok|=que(a->r,m+1,r,L,R);
return ok;
}
bool book(int st, int ed) {
if(que(rt,0,NN,st,ed-1)) return false;
upd(rt,0,NN,st,ed-1,1);
return true;
}
};
set,做法每次就lower_bound l>=ed的 位置 p p p。
然后判断 ( − − p ) → r ≤ s t < e d ≤ l (--p)\rightarrow r\le st<ed\le l (−−p)→r≤st<ed≤l
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
class MyCalendar {
set<pair<int, int>> booked;
public:
bool book(int start, int end) {
auto it = booked.lower_bound({
end, 0});
if (it == booked.begin() || (--it)->second <= start) {
booked.emplace(start, end);
return true;
}
return false;
}
};
边栏推荐
- 关于进程、线程、协程、同步、异步、阻塞、非阻塞、并发、并行、串行的理解
- 【FPGA教程案例11】基于vivado核的除法器设计与实现
- What is the difference between gateway address and IP address in tcp/ip protocol?
- Python book learning notes - Chapter 09 section 01 create and use classes
- Execution order of scripts bound to game objects
- Stack and queue
- Security xxE vulnerability recurrence (XXe Lab)
- Network security - Security Service Engineer - detailed summary of skill manual (it is recommended to learn and collect)
- Python book learning notes - Chapter 09 section 01 create and use classes
- In depth MySQL transactions, stored procedures and triggers
猜你喜欢
【PSO】基于PSO粒子群优化的物料点货物运输成本最低值计算matlab仿真,包括运输费用、代理人转换费用、运输方式转化费用和时间惩罚费用
Cross domain and jsonp details
Slow SQL fetching and analysis of MySQL database
One question per day (Mathematics)
Ks003 mall system based on JSP and Servlet
Lombok原理和同时使⽤@Data和@Builder 的坑
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
MySQL master-slave replication
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
图应用详解
随机推荐
Fundamentals of SQL database operation
DM8 backup set deletion
Facebook等大廠超十億用戶數據遭泄露,早該關注DID了
20、 EEPROM memory (AT24C02) (similar to AD)
2/12 didn't learn anything
[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)
Ks003 mall system based on JSP and Servlet
Global and Chinese markets for patent hole oval devices 2022-2028: Research Report on technology, participants, trends, market size and share
Python book learning notes - Chapter 09 section 01 create and use classes
pd. to_ numeric
Practical development of member management applet 06 introduction to life cycle function and user-defined method
Global and Chinese markets for MRI safe implants 2022-2028: technology, participants, trends, market size and share Research Report
关于进程、线程、协程、同步、异步、阻塞、非阻塞、并发、并行、串行的理解
Path of class file generated by idea compiling JSP page
51nod 1130 n factorial length V2 (Stirling approximation)
Use js to complete an LRU cache
Global and Chinese markets for endoscopic drying storage cabinets 2022-2028: Research Report on technology, participants, trends, market size and share
Comprehensive ability evaluation system
【leetcode】1189. Maximum number of "balloons"
Chinese brand hybrid technology: there is no best technical route, only better products