Description
Write a program that should efficiently respond to these 3 types of instructions:
type 1: the arrival of a new group of tourists
A group of M tourists wants to occupy M free consecutive rooms. The program will receive the number i which represents the start room of the sequence of the rooms that the group wants to occupy and the number M representing the number of members of the group. It is guaranteed that all the rooms i,i+1,..,i+M-1 are free at that moment.
type 2: the departure of a group of tourists
The tourists leave in groups (not necessarilly those groups in which they came). A group with M members leaves M occupied and consecutive rooms. The program will receive the number i representing the start room of the sequence of the released rooms and the number M representing the number of members of the group. It is guaranteed that all the rooms i,i+1,..,i+M-1 are occupied.
type 3: the owner's question
The owner of the hotel may ask from time to time which is the maximal length of a sequence of free consecutive rooms. He needs this number to know which is the maximal number of tourists that could arrive to the hotel. You can assume that each room may be occupied by no more than one tourist.
Input
The next P lines will contain the number c representing the type of the instruction:
- if c is 1 then it will be followed (on the same line) by 2 other numbers, i and M, representing the number of the first room distributed to the group and the number of the members
- if c is 2 then it will be followed (on the same line) by 2 other numbers, i and M, representing the number of the first room that will be released and the number of the members of the group that is leaving
- if c is 3 then it will not be followed by any number on that line, but the program should output in the output file the maximal length of a sequence of free and consecutive rooms
Output
Sample Input
12 10
3
1 2 3
1 9 4
3
2 2 1
3
2 9 2
3
2 3 2
3
Sample Output
12
4
4
6
10
Source
/*
唐代许浑
《咸阳城东楼 / 咸阳城西楼晚眺 / 西门》 一上高城万里愁，蒹葭杨柳似汀洲。
溪云初起日沉阁，山雨欲来风满楼。
鸟下绿芜秦苑夕，蝉鸣黄叶汉宫秋。
行人莫问当年事，故国东来渭水流。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#define LOCAL
const int MAXN = + ;
const int MAXM = + ;
const int INF = ;
const int SIZE = ;
const int maxnode = 0x7fffffff + ;
using namespace std;
int i;
struct SEGTREE{
struct Node{
int l, r;
int rmax, mmax, lmax;//分别代表从左边开始的最长，从右边开始的最长和中间的最长
int delta; /*void Count(){
rmax = lmax = mmax = 0;
for (int i = l; i <= r; i++) if (data[i] == 0){lmax = i - l;break;}
for (int i = r; i >= l; i--) if (data[i] == 0){rmax = r - i;break;}
int t = 0;
for (int i = l; i <= r; i++){ }
}*/
}tree[MAXN * ]; void pushdown(int t){
if (tree[t].delta != -){
if (tree[t].delta == ) {//全1
tree[(t<<)].lmax = tree[(t<<)].rmax = tree[(t<<)].mmax = tree[(t<<)].r - tree[(t<<)].l + ;tree[(t<<)].delta = ;
tree[(t<<) | ].lmax = tree[(t<<) | ].rmax = tree[(t<<) | ].mmax = tree[(t<<) | ].r - tree[(t<<) | ].l + ;tree[(t<<) | ].delta = ;
tree[t].delta = -;
}else{
tree[(t<<)].lmax = tree[(t<<)].rmax = tree[(t<<)].mmax = ;tree[(t<<)].delta = ;
tree[(t<<) | ].lmax = tree[(t<<) | ].rmax = tree[(t<<) | ].mmax = ;tree[(t<<) | ].delta = ;
tree[t].delta = -;
}
}
}
//更新
void update(int t){
tree[t].mmax = max(tree[t<<].mmax, max(tree[(t<<)|].mmax, tree[t<<].rmax + tree[(t<<)|].lmax));
//更新tree[t]的lmax
if (tree[t<<].lmax == tree[t<<].r - tree[t<<].l + ) tree[t].lmax = tree[t<<].lmax + tree[(t<<)|].lmax;
else tree[t].lmax = tree[t<<].lmax; //同理
if (tree[(t<<)|].rmax == tree[(t<<)|].r - tree[(t<<)|].l + ) tree[t].rmax = tree[t<<].rmax + tree[(t<<)|].rmax;
else tree[t].rmax = tree[(t<<)|].rmax;
}
void build(int t, int l, int r){
tree[t].l = l;
tree[t].r = r;
tree[t].lmax = tree[t].mmax = tree[t].rmax = tree[t].r - tree[t].l + ;
tree[t].delta = -;
if (l == r) return;
int mid = (l + r) >> ;
build(t << , l, mid);
build((t << )|, mid + , r);
}
void insert(int t, int l, int r, int val){//t为节点编号，val为权值
pushdown(t);
if (l <= tree[t].l && tree[t].r <= r){
if (val == ) {tree[t].rmax = tree[t].lmax = tree[t].mmax = tree[t].r - tree[t].l + ;tree[t].delta = ;}
else {tree[t].rmax = tree[t].lmax = tree[t].mmax = ;tree[t].delta = ;}
return;
}
int mid = (tree[t].l + tree[t].r)>>;
//if (i == 3 && tree[t].l == 10 && tree[t].r == 11)
//printf("");
if (l <= mid) insert(t << , l, r , val);
if (r > mid) insert((t << ) | , l, r, val); update(t);
}
}A;
int n, p; void init(){
scanf("%d%d", &n, &p);
A.build(, , n);
}
void work(){
for (i = ; i <= p; i++){
int t;
scanf("%d", &t);
if (t == ) printf("%d\n", A.tree[].mmax);
else if (t == ){
int l, r;
scanf("%d%d", &l, &r);
A.insert(, l, l + r - , );
}else if (t == ){
int l, r;
scanf("%d%d", &l, &r);
A.insert(, l, l + r - , );
}
}
} int main(){ init();
work();
return ;
}