当前位置:网站首页>729. My schedule I (set or dynamic open point segment tree)
729. My schedule I (set or dynamic open point segment tree)
2022-07-06 04:16:00 【Harris-H】
729. My schedule I(set or Dynamic open point line segment tree )
Interval coverage , Interval query . Therefore, the value range is large , Small number of queries , So open it dynamically .
The tree building method is similar to the ordinary segment tree , Namely pushdown It is decided whether the left and right sons are empty , Then all functions can use pointers .
Time complexity : 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, Practice every time lower_bound l>=ed Of Location p p p.
And then determine ( − − p ) → r ≤ s t < e d ≤ l (--p)\rightarrow r\le st<ed\le l (−−p)→r≤st<ed≤l
Time complexity : 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;
}
};
边栏推荐
- Thread sleep, thread sleep application scenarios
- 查询mysql数据库中各表记录数大小
- Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
- Unity中几个重要类
- Chinese brand hybrid technology: there is no best technical route, only better products
- Slow SQL fetching and analysis of MySQL database
- TCP/IP协议里面的网关地址和ip地址有什么区别?
- DM8 backup set deletion
- asp. Core is compatible with both JWT authentication and cookies authentication
- Fedora/rehl installation semanage
猜你喜欢
Database, relational database and NoSQL non relational database
综合能力测评系统
Recommendation system (IX) PNN model (product based neural networks)
Comprehensive ability evaluation system
【按鍵消抖】基於FPGA的按鍵消抖模塊開發
Execution order of scripts bound to game objects
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
IDEA编译JSP页面生成的class文件路径
Overturn your cognition? The nature of get and post requests
Class A, B, C networks and subnet masks in IPv4
随机推荐
How to solve the problem of slow downloading from foreign NPM official servers—— Teach you two ways to switch to Taobao NPM image server
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
P3500 [POI2010]TES-Intelligence Test(二分&离线)
VNCTF2022 WriteUp
Leetcode32 longest valid bracket (dynamic programming difficult problem)
Cross domain and jsonp details
Proof of Stirling formula
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
Brief tutorial for soft exam system architecture designer | general catalog
1291_ Add timestamp function in xshell log
[Zhao Yuqiang] deploy kubernetes cluster with binary package
P2648 make money
Explain in simple terms node template parsing error escape is not a function
2/13 review Backpack + monotonic queue variant
Interface idempotency
2/12 didn't learn anything
Crawler notes: improve data collection efficiency! Use of proxy pool and thread pool
C. The Third Problem(找规律)
综合能力测评系统
Basic use of MySQL (it is recommended to read and recite the content)