题意：一个hotel，有n间连续的房间，现在有m组操作：
type 1: '1, a, b': 第a个房间起的b个房间有旅客入住。
type 2: '2, a, b': 第a个房间起的b个房间的旅客离开。 type 3: '3': 问最长的连续空房间有多少间。
思路：线段树。这道题很好的利用线段树递归的性质，加深了对线段树递归的理解。复习了一下延迟的操作，学会了与延迟操作相反的操作，即利用递归，在递归回来的时候，由于左右子结点性质的改变，即时对父结点信息进行相应的更改，这个要注意。
源代码：(944K 3282MS)
#include<iostream>
using namespace std;const int Max = 16005;
struct{
int l, r; int lma, ma, rma; // lma为这个区间左边的最长连续空房间的数量。 int cover; //‘1’表示这个区间的房间全住人，‘-1’表示全空，‘0’表示有空用住。}node[3*Max];
int max(int a, int b){
return a > b ? a : b;}
void BuildTree(int left, int right, int u){ // 建树。
node[u].l = left; node[u].r = right; if(left == right) return; int mid = (left + right)>>1; BuildTree(left, mid, u<<1); BuildTree(mid+1, right, (u<<1)+1);}
void getdown(int u, int op){ // 延迟的操作。
node[u].cover = 0; node[u<<1].cover = op; node[(u<<1)+1].cover = op; if(op == 1){ node[u<<1].lma = 0; node[u<<1].ma = 0; node[u<<1].rma = 0; node[(u<<1)+1].lma = 0; node[(u<<1)+1].ma = 0; node[(u<<1)+1].rma = 0; } else{ int len; len = node[u<<1].r - node[u<<1].l + 1; node[u<<1].lma = len; node[u<<1].ma = len; node[u<<1].rma = len; len = node[(u<<1)+1].r - node[(u<<1)+1].l + 1; node[(u<<1)+1].lma = len; node[(u<<1)+1].ma = len; node[(u<<1)+1].rma = len; }}
void updata(int left, int right, int op, int u){ // 修改。
if(left <= node[u].l && right >= node[u].r){ node[u].cover = op; if(op == 1) node[u].lma = node[u].ma = node[u].rma = 0; else{ int len = node[u].r - node[u].l + 1; node[u].lma = node[u].ma = node[u].rma = len; } return; } if(node[u].cover == op) return; if(node[u].cover == -op) getdown(u, -op); if(right <= node[u<<1].r) updata(left, right, op, u<<1); else if(left >= node[(u<<1)+1].l) updata(left, right, op, (u<<1)+1); else{ updata(left, right, op, u<<1); updata(left, right, op, (u<<1)+1); }
// *很好运用递归，由左右子结点的信息，对父结点的三个连续区间最大值进行相应的更改。
if(node[u<<1].cover == -1) // 求父结点的lma。
node[u].lma = node[u<<1].ma + node[(u<<1)+1].lma; else node[u].lma = node[u<<1].lma; if(node[(u<<1)+1].cover == -1) // 求父结点的rma。 node[u].rma = node[(u<<1)+1].ma + node[u<<1].rma; else node[u].rma = node[(u<<1)+1].rma; int a = node[u<<1].rma + node[(u<<1)+1].lma; // 求父结点的ma。 int b = max(node[u<<1].ma, node[(u<<1)+1].ma); int c = max(node[u].lma, node[u].rma); node[u].ma = max(max(a, b), c);
// *递归回来的时候，由于左右子结点性质的改变，必须对父结点信息进行相应的更改，WA在了这里。
if(node[u<<1].cover == node[(u<<1)+1].cover)
node[u].cover = node[u<<1].cover;}
int main(){
int n, m; scanf("%d%d", &n, &m); BuildTree(1, n, 1); node[1].cover = -1; node[1].ma = n; while(m --){ int op, a, b; scanf("%d", &op); if(op == 1){ scanf("%d%d", &a, &b); updata(a, a+b-1, 1, 1); // 为a+b-1，不能算成a+b。 } else if(op == 2){ scanf("%d%d", &a, &b); updata(a, a+b-1, -1, 1); } else printf("%d\n", node[1].ma); } return 0;}