Naked line segment tree , It's just that I remember a lot of things ...

The left end of each interval is the longest 0, Longest at right end 0, The longest in the middle 0, and tag It means whether it's all 0/1

Just update it directly , When inquiring, check the left son first , Then check the middle , Finally, check the right son ...

 /**************************************************************
Problem: 1593
User: rausen
Language: C++
Result: Accepted
Time:388 ms
Memory:4404 kb
****************************************************************/ #include <cstdio>
#include <algorithm> using namespace std; inline int read(); struct seg {
seg *ls, *rs;
int mxl, mxm, mxr, len, tag; #define Len (1 << 16)
void* operator new(size_t, int x) {
static seg *mempool, *c;
if (c == mempool)
mempool = (c = new seg[Len]) + Len;
c -> ls = c -> rs = NULL;
c -> mxl = c -> mxr = c -> mxm = c -> len = x, c -> tag = -;
return c++;
}
#undef Len #define mid (l + r >> 1)
#define Ls this -> ls
#define Rs this -> rs
inline void fill(int d) {
if (d) this -> mxl = this -> mxr = this -> mxm = ;
else this -> mxl = this -> mxr = this -> mxm = this -> len;
this -> tag = d;
} inline void push() {
if (~this -> tag) {
if (Ls) Ls -> fill(this -> tag);
if (Rs) Rs -> fill(this -> tag);
this -> tag = -;
}
}
inline void update() {
this -> mxl = Ls -> mxl + (Ls -> mxl == Ls -> len ? Rs -> mxl : );
this -> mxr = Rs -> mxr + (Rs -> mxr == Rs -> len ? Ls -> mxr : );
this -> mxm = max(max(Ls -> mxm, Rs -> mxm), Ls -> mxr + Rs -> mxl);
} void build(int l, int r) {
if (l == r) return;
Ls = new(mid - l + )seg, Ls -> build(l, mid);
Rs = new(r - mid)seg, Rs -> build(mid + , r);
} void modify(int l, int r, int L, int R, int d) {
if (L <= l && r <= R) {
this -> fill(d);
return;
}
this -> push();
if (L <= mid) Ls -> modify(l, mid, L, R, d);
if (mid < R) Rs -> modify(mid + , r, L, R, d);
this -> update();
} int query(int l, int r, int len) {
this -> push();
if (this -> mxm < len) return ;
if (Ls -> mxm >= len) return Ls -> query(l, mid, len);
if (Ls -> mxr + Rs -> mxl >= len) return mid - Ls -> mxr + ;
if (Rs -> mxm >= len) return Rs -> query(mid + , r, len);
}
#undef mid
#undef Ls
#undef Rs
} *segment; int n, m; int main() {
int i, oper, x, y;
n = read(), m = read();
segment = new(n)seg;
segment -> build(, n);
for (i = ; i <= m; ++i) {
oper = read();
if (oper == ) {
x = segment -> query(, n, y = read());
printf("%d\n", x);
if (x) segment -> modify(, n, x, x + y - , );
} else {
x = read(), y = read();
segment -> modify(, n, x, x + y - , );
}
}
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}

BZOJ1593 [Usaco2008 Feb]Hotel More articles about hotels

  1. bzoj1593 [Usaco2008 Feb]Hotel hotel ( Line segment tree )

    1593: [Usaco2008 Feb]Hotel hotel Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 758  Solved: 419[Submit ...

  2. Line segment tree ||BZOJ1593: [Usaco2008 Feb]Hotel hotel ||Luogu P2894 [USACO08FEB] The hotel Hotel

    Topic :P2894 [USACO08FEB] The hotel Hotel Answer key : It's not very different from the basic line tree operation , It is to maintain a legal precursor with the longest interval on the basis of the traditional line segment tree (h_), The longest legal afterdrive (t_), The longest legal interval in a period ...

  3. 【 The longest continuous zero Line segment tree 】bzoj1593: [Usaco2008 Feb]Hotel hotel

    The line segment tree solution of the longest continuous zero Description Cows' latest travel plans , It's by Lake Superior , Enjoy the scenery of the lakes and mountains , And the sunshine . As the planner and negative of the whole tourism blame others , Bessie chose to stay in a famous hotel by the lake . This is huge ...

  4. 【 Block 】bzoj1593 [Usaco2008 Feb]Hotel hotel

    Block , Record the length of the largest continuous white segment in each block including the left endpoint , The length of the largest continuous white segment in the whole block , And the length of the largest continuous white segment including the right endpoint . Because It's interval coloring , So mark it . As for how to work in O(sqrt(n)) Time for ...

  5. 1593: [Usaco2008 Feb]Hotel hotel

    1593: [Usaco2008 Feb]Hotel hotel Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 391  Solved: 228[Submit ...

  6. 【bzoj1593】[Usaco2008 Feb]Hotel hotel Segment tree interval merging

    Title Description Cows' latest travel plans , It's by Lake Superior , Enjoy the scenery of the lakes and mountains , And the sunshine . As the planner and director of the whole tourism , Bessie chose to stay in a famous hotel by the lake . This huge hotel has N (1 <= N & ...

  7. BZOJ 1593: [Usaco2008 Feb]Hotel hotel

    Description Cows' latest travel plans , It's by Lake Superior , Enjoy the scenery of the lakes and mountains , And the sunshine . As the planner and director of the whole tourism , Bessie chose to stay in a famous hotel by the lake . This huge hotel has N (1 &l ...

  8. BZOJ 1593: [Usaco2008 Feb]Hotel hotel [ Line segment tree ]

    Portal The question : operation 1: Looking for Chang Wei $len$ And fill in , No output $0$ operation 2: take $[l,r]$ Empty the interval between I'm so weak. I wrote this line segment tree for an hour and a half , In the middle, in order to check the error, we simulated it manually $30min$ Line segment tree operation , ...

  9. 【BZOJ】1593: [Usaco2008 Feb]Hotel hotel

    [ Algorithm ] Line segment tree ( Bisection in classical line tree ) [ The question ]n A room ,m A asked , Every time you order the first consecutive x An empty room of , Or unsubscribe from x Start y A room , Ask for the leftmost room number of each order . [ Answer key ] The key is to find continuity x An empty room , Classic dichotomy . Segment tree markers s ...

Random recommendation

  1. javascript operation excel Total strategy

    Do a project recently , Yes javascript manipulation excel To generate reports , Here's an example with detailed notes <html> <head><script language="ja ...

  2. JSP Error message prompt

    MessageResource.properties The configuration file : RegisterAction register : package com.caiduping.action; import javax.servlet ...

  3. Python The way ,Day13----- Nothing is being updated

    Python The way ,Day13----- Nothing is being updated

  4. MySQL Hardware--NUMA And MySQL

    MUMA framework In a single instance of MySQL Server , Pass the meeting for MySQL Of Buffer Pool Distribute 50% to 70% Even higher memory , Give Way MySQL Services take up as many system resources as possible . Based on NUMA In the system , Memory is allocated to each ...

  5. Tomcat 9.0 Configuration problem 403 Access Denied

    tomcat9.0 Management pages such as :http://10.10.10.10:8080/manager/html The following error occurred : 403 Access Denied 1. Need configuration : Tomcat/conf/to ...

  6. Kernel compilation vmlinuz vmlinux system.map initrd

    One .vmlinuz  vmlinuz It's steerable . Compressed kernel .“vm” representative “Virtual Memory”.Linux Support virtual memory , It's not like the old operating system, like DOS Yes 640KB Memory limit .Linux Able to use ...

  7. oracle The activation and cancellation of audit

    Audit audit The user sees what the user is doing , also oracle The audit trail results will be stored in os In a file or database Activate audit conn /as sysdba show parameter audit_sys_opera ...

  8. Java zxing What it takes to generate a QR code jar package

    Free of charge , No points needed . share 2 individual jar package , link : https://pan.baidu.com/s/1QJcEkRQOp1NdrNAgGC6LvQ password : 4524

  9. [leetcode]122. Best Time to Buy and Sell Stock II The second best time to speculate in stocks

    Say you have an array for which the ith element is the price of a given stock on day i. Design an al ...

  10. js Simple interview questions

    1,js What are the data types , Data type judgment function ? String,Number,Boolean,Null,Undefined,Object The judgment function has :typeof,instanceof,construct ...