线段树的静态区间查询

• 区间里大于x的最左边的位置：

　　　　看左区间的最大值是否大于x，决定是否往左区间找

• 区间最大连续和：

　　　　维护区间左连续最大和，右连续最大和，最大连续和

• 求整个区间中大于k的数之和：

　　　　权值线段树，然后求区间和

• 在排好序的数组里查询区间众数的个数：

　　　　维护区间左连续相同数的个数，区间右连续相同数的个数，区间连续相同数的个数

 

有序区间的区间众数个数代码：

struct NODE {
	int l, r, mid;
	int lc, rc, mc;
}tree[MAXN*4];
void build(int pos, int l, int r) {
	tree[pos].l = l; tree[pos].r = r; tree[pos].mid = l + r >> 1;
	if (l == r) {
		tree[pos].lc = tree[pos].rc = tree[pos].mc = 1;
		return;
	}
	int mid = l + r >> 1;
	build(pos << 1, l, mid);
	build(pos << 1 | 1, mid + 1, r);
	if (a[l] == a[mid + 1]) tree[pos].lc = tree[pos << 1].lc + tree[pos << 1 | 1].lc;
	else tree[pos].lc = tree[pos << 1].lc;
	if (a[mid] == a[r]) tree[pos].rc = tree[pos << 1 | 1].rc + tree[pos << 1].rc;
	else tree[pos].rc = tree[pos << 1 | 1].rc;
	tree[pos].mc = max(tree[pos << 1].mc, tree[pos << 1 | 1].mc);
	if (a[mid] == a[mid + 1]) tree[pos].mc = max(tree[pos].mc, tree[pos << 1].rc + tree[pos << 1 | 1].lc);
}
int Q_l(int pos, int l, int r) {
	if (tree[pos].l == l && tree[pos].r == r) return tree[pos].lc;
	int mid = tree[pos].mid;
	if (r <= mid) return Q_l(pos << 1, l, r);
	else if (l > mid) return Q_l(pos << 1 | 1, l, r);
	else {
		if (a[l] == a[mid + 1]) return Q_l(pos << 1, l, mid) + Q_l(pos << 1 | 1, mid + 1, r);
		else return Q_l(pos << 1, l, mid);
	}
}
int Q_r(int pos, int l, int r) {
	if (tree[pos].l == l && tree[pos].r == r) return tree[pos].rc;
	int mid = tree[pos].mid;
	if (r <= mid) return Q_r(pos << 1, l, r);
	else if (l > mid) return Q_r(pos << 1 | 1, l, r);
	else {
		if (a[mid] == a[r]) return Q_r(pos << 1, l, mid) + Q_r(pos << 1 | 1, mid + 1, r);
		else return Q_r(pos<<1|1,mid+1,r);
	}
}
int Q(int pos, int l, int r) {
	if (tree[pos].l == l && tree[pos].r == r) return tree[pos].mc;
	int mid = tree[pos].mid;
	if (r <= mid) return Q(pos << 1, l, r);
	else if (l > mid) return Q(pos << 1 | 1, l, r);
	else {
		int res = max(Q(pos << 1, l, mid), Q(pos << 1 | 1, mid + 1, r));
		if (a[mid] == a[mid + 1]) res = max(res, Q_r(pos << 1, l, mid) + Q_l(pos << 1 | 1, mid + 1, r));
		return res;
	}
}

　　

线段树的区间修改和懒标记

• 扫描线模板题中维护区间里非0数的个数：

　　　　记录区间被矩形完全覆盖的矩形个数，查询时，如果区间被某个矩形完全覆盖，非0数=区间长度，否则非0数=左区间非0数+右区间非0数

　　　　因为查询都是查询[1,n]区间的非0数，所以不需要懒标记

• 以函数映射为懒标记的线段树：

　　　　和一般懒标记一样，写码时要小心，lazy_tag别忘了处理

• 宾馆住户题，找到宾馆里最靠左的有连续x个空房的房间并入住，宾馆区间[x,y]退房：

　　　　维护区间左连续空房数，右连续空房数，最大连续空房数，还有区间修改需要的懒标记

 

　　宾馆住户题代码：

　　

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 1e5 + 7;
struct NODE {
	int l, r, mid, len;
	int lazy, lc, rc, mc;
}tree[MAXN * 4];
void build(int pos, int l, int r) {
	tree[pos].l = l; tree[pos].r = r; tree[pos].mid = l + r >> 1; tree[pos].len = r - l + 1;
	tree[pos].lazy = 2;
	tree[pos].lc = tree[pos].rc = tree[pos].mc = tree[pos].len;
	if (l == r) return;
	int mid = l + r >> 1;
	build(pos << 1, l, mid);
	build(pos << 1 | 1, mid + 1, r);
}
void pd(int pos) {
	int lazy = tree[pos].lazy;
	tree[pos << 1].lazy = tree[pos << 1 | 1].lazy = lazy;
	if (lazy == 1) {
		tree[pos << 1].lc = tree[pos << 1].rc = tree[pos << 1].mc = 0;
		tree[pos << 1 | 1].lc = tree[pos << 1 | 1].rc = tree[pos << 1 | 1].mc = 0;
	}
	else {
		tree[pos << 1].lc = tree[pos << 1].rc = tree[pos << 1].mc = tree[pos << 1].len;
		tree[pos << 1 | 1].lc = tree[pos << 1 | 1].rc = tree[pos << 1 | 1].mc = tree[pos << 1 | 1].len;
	}
	tree[pos].lazy = 2;
}
void update(int pos) {
	if (tree[pos << 1].lc == tree[pos<<1].len) tree[pos].lc = tree[pos << 1].len + tree[pos << 1 | 1].lc;
	else tree[pos].lc = tree[pos << 1].lc;
	if (tree[pos << 1 | 1].rc == tree[pos << 1 | 1].len) tree[pos].rc = tree[pos << 1 | 1].len + tree[pos << 1].rc;
	else tree[pos].rc = tree[pos << 1 | 1].rc;
	tree[pos].mc = max(tree[pos << 1].mc, tree[pos << 1 | 1].mc);
	tree[pos].mc = max(tree[pos].mc, tree[pos << 1].rc + tree[pos << 1 | 1].lc);
}
void CHANGE(int pos, int l, int r, int k) {
	if (tree[pos].l == l && tree[pos].r == r) {
		tree[pos].lazy = k;
		if (k) {
			tree[pos].lc = tree[pos].rc = tree[pos].mc = 0;
		}
		else {
			tree[pos].lc = tree[pos].rc = tree[pos].mc = tree[pos].len;
		}
		return;
	}
	if (tree[pos].lazy != 2) pd(pos);
	int mid = tree[pos].mid;
	if (r <= mid) CHANGE(pos << 1, l, r, k);
	else if (l > mid) CHANGE(pos << 1 | 1, l, r, k);
	else {
		CHANGE(pos << 1, l, mid, k);
		CHANGE(pos << 1 | 1, mid + 1, r, k);
	}
	update(pos);
}
int Q(int pos, int x) {
	if (tree[pos].mc < x) return 0;
	if (tree[pos].lazy != 2) pd(pos);
	if (tree[pos << 1].mc >= x) return Q(pos << 1, x);
	if (tree[pos << 1].rc + tree[pos << 1 | 1].lc >= x) return tree[pos << 1].r - tree[pos << 1].rc + 1;
	else return Q(pos << 1|1, x);
}
int main()
{
	int n, m, op, x, y;
	cin >> n >> m;
	build(1, 1, n);
	while (m--) {
		scanf("%d%d", &op, &x);
		if (op == 2) {
			scanf("%d", &y);
			CHANGE(1, x, x + y - 1, 0);
		}
		else {
			int pp = Q(1, x);
			printf("%d\n", pp);
			if (pp) CHANGE(1, pp, pp + x - 1, 1);
		}
	}
	return 0;
}