HDU4553 线段树维护最长连续区间

//题意：（略了）
//思路：这里很明显是要维护区间最大连续子段，按照以下优先级查找
//      A1.左边区间的连续子段是否满足
//      A2.左右两个区间中间合并起来的子段是否满足
//      A3.右边区间的连续子段是否满足
//
//      第一次做这种题，遇到的问题在于不知道怎么返回满足条件的子段的起始位置，而实际上我们可以把查找起始位置归类到三种
//      情况上去
//      1.满足条件的子段长度为1，这样起始就是类似于单点查询而已，边界条件是（l==r）
//      2.满足条件的子段长度大于1，这样一来我们总可以将这个子段放到A2的情况上去，从而算出起始点（具体在代码中讲解）
#include<bits/stdc++.h>
using namespace std;
#define lson id<<1,l,mid
#define rson id<<1|1,mid+1,r 
const int N = 1e5 + 50;
struct edge {
	int ls;//左端点开始的连续
	int rs;//右端点开始的连续
	int ms;//区间内的最大连续
	//感觉不适合打标记，因为我的ls和rs需要下层的信息反馈，所以我们干脆一次性向下更新完（其实并不是，这里没标记的原因只是我可以通过值来判断情况而已）
}ds[4 * N], ns[4 * N];
int T, t, n;
void push_down(int id, int l, int r) {
	int mid = (l + r) >> 1;
	if (ds[id].ms == r - l + 1) {//通过上层信息可以推断出下层信息
		ds[id << 1].ms = ds[id << 1].ls = ds[id << 1].rs = mid - l + 1;
		ds[id << 1 | 1].ms = ds[id << 1 | 1].ls = ds[id << 1 | 1].rs = r - mid;
	}
	else if (ds[id].ms == 0) {
		ds[id << 1].ms = ds[id << 1].ls = ds[id << 1].rs = 0;
		ds[id << 1 | 1].ms = ds[id << 1 | 1].ls = ds[id << 1 | 1].rs = 0;
	}

	if (ns[id].ms == r - l + 1) {//通过上层信息可以推断出下层信息
		ns[id << 1].ms = ns[id << 1].ls = ns[id << 1].rs = mid - l + 1;
		ns[id << 1 | 1].ms = ns[id << 1 | 1].ls = ns[id << 1 | 1].rs = r - mid;
	}
	else if (ns[id].ms == 0) {
		ns[id << 1].ms = ns[id << 1].ls = ns[id << 1].rs = 0;
		ns[id << 1 | 1].ms = ns[id << 1 | 1].ls = ns[id << 1 | 1].rs = 0;
	}
}
void update(int id, int l, int r) {
	int mid = (l + r) >> 1;
	ds[id].ls = ds[id << 1].ls;
	ds[id].rs = ds[id << 1 | 1].rs;
	ds[id].ms = max(max(ds[id << 1].ms, ds[id << 1 | 1].ms), ds[id << 1].rs + ds[id << 1 | 1].ls);
	if (ds[id << 1].ms == mid - l + 1) ds[id].ls += ds[id << 1 | 1].ls;
	if (ds[id << 1 | 1].ms == r - mid) ds[id].rs += ds[id << 1].rs;

	ns[id].ls = ns[id << 1].ls;
	ns[id].rs = ns[id << 1 | 1].rs;
	ns[id].ms = max(max(ns[id << 1].ms, ns[id << 1 | 1].ms), ns[id << 1].rs + ns[id << 1 | 1].ls);
	if (ns[id << 1].ms == mid - l + 1) ns[id].ls += ns[id << 1 | 1].ls;
	if (ns[id << 1 | 1].ms == r - mid) ns[id].rs += ns[id << 1].rs;//这几种更新情况要 注意一下
}
void build(int id, int l, int r) {
	ds[id].ls = ns[id].ls = r - l + 1;
	ds[id].rs = ns[id].rs = r - l + 1;
	ds[id].ms = ns[id].ms = r - l + 1;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(2 * id, l, mid);
	build(2 * id + 1, mid + 1, r);
	update(id, l, r);
}
void change(int id, int l, int r, int ql, int qr, int op) {
	if (l == ql && r == qr) {
		if (op == 1) {
			ds[id].ls = ds[id].rs = ds[id].ms = 0;
		}
		if (op == 2) {
			ds[id].ls = ds[id].rs = ds[id].ms = 0;
			ns[id].ls = ns[id].rs = ns[id].ms = 0;
		}
		if (op == 3) {
			ds[id].ls = ds[id].rs = ds[id].ms = r - l + 1;
			ns[id].ls = ns[id].rs = ns[id].ms = r - l + 1;
		}
		return;
	}
	int mid = (l + r) >> 1;
	push_down(id, l, r);//这里push_down的原因是对这个区间修改后还需要把区间的所有值更新一遍
	if (ql <= mid) change(lson, ql, mid, op);
	if (qr > mid) change(rson, mid + 1, qr, op);
	update(id, l, r);
}
int query(int id, int l, int r, int ans, int op) {
	if (l == r) return 1;
	push_down(id, l, r);
	int mid = (l + r) / 2;
	if (op == 1) {
		if (ds[id << 1].ms >= ans) {		//在左区间 
			return query(lson, ans, op);
		}
		else if (ds[id << 1].rs + ds[id << 1 | 1].ls >= ans) {		//跨越左右，必须先写这个在写查询右边的
			return mid - ds[id << 1].rs + 1;
		}
		else {			//在右区间
			return query(rson, ans, op);
		}
	}
	if (op == 2) {
		if (ns[id << 1].ms >= ans) {		//在左区间 
			return query(lson, ans, op);
		}
		else if (ns[id << 1].rs + ns[id << 1 | 1].ls >= ans) {		//跨越左右，必须先写这个在写查询右边的
			return mid - ns[id << 1].rs + 1;
		}
		else {		//右区间
			return query(rson, ans, op);
		}
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &t, &n);
		build(1, 1, t);
		for (int i = 1; i <= n; i++) {
			string s; int a, b, l, r;
			scanf("%s", &s);
			if (s == "DS") {
				scanf("%d", &a);
				cout << ds[1].ms << endl;
				if (ds[1].ms >= a) {
					l = query(1, 1, t, a, 1);
					r = l + a - 1;
					change(1, 1, t, l, r, 1);
					printf("%d,let's fly\n", l);
				}
				else
					printf("fly with yourself\n");
			}
			else if (s == "NS") {
				scanf("%d", &a);
				if (ds[1].ms >= a) {
					l = query(1, 1, t, a, 1);
					r = l + a - 1;
					printf("%d,don't put my gezi\n", l);
					change(1, 1, t, l, r, 2);
				}
				else if (ns[1].ms >= a) {
					l = query(1, 1, t, a, 2);
					r = l + a - 1;
					printf("%d,don't put my gezi\n", l);
					change(1, 1, t, l, r, 2);
				}
				else
					printf("wait for me\n");
			}
			else {
				scanf("%d%d", &a, &b);
				change(1, 1, t, a, b, 3);
				printf("I am the hope of chinese chengxuyuan!!\n");
			}
		}
	}
	return 0;
}