线段统计 - 线段树懒标记

Problem

题目描述
在数轴上进行一系列操作。每次操作有两种类型，一种是在线段[a,b]上涂上颜色，另一种将[a,b]上的颜色擦去。问经过一系列的操作后，有多少条单位线段[k,k+1]被涂上了颜色。

输入格式
第1行：2个整数n（0<=n<=60000）和m（1<=m<=60000）分别表示数轴长度和进行操作的次数。
接下来m行，每行3个整数i，a，b， 0 <=a<=b<=60000，若i=1表示给线段[a,b]上涂上颜色，若i=2表示将[a,b]上的颜色擦去。

输出格式
文件输出仅有一行为1个整数，表示有多少条单位线段[k,k+1]被涂上了颜色。

样例输入
10 5
1 2 8
2 3 6
1 1 10
2 4 7
1 1 5

样例输出
7

分析

最为经典的一道区间修改区间查询加懒标记的题了
懒标记的实质：推迟信息更新，避免无用操作
如果不加懒标记，线段树连暴力都不如。
对于每个非完全包含的区间，在修改和查询到的时候都要向下传标记。
比如此题，如果标记为全部有色，传下去儿子结点全部有色，全部无色亦然。
传完标记后需要将标记置为0表示儿子中有的有颜色有的无颜色。
因为建树方式不同，线段映射到点右端点需-1

Source

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#define MAXN 1000005
using namespace std;
struct Segt
{
	int l, r, colored, lazy;
	//lazy=1表示该区间内全部染了色 
};
class SegmentTree
{
public:
	Segt Tree[MAXN * 4];
	int sum;
	void Build(int ind, int l, int r)
	{
		Tree[ind].l = l, Tree[ind].r = r;
		Tree[ind].colored = 0, Tree[ind].lazy = 0;
		if (l >= r) return;
		int mid = (l + r) >> 1;
		Build(ind << 1, l, mid);
		Build(ind << 1 | 1, mid + 1, r);
	}
	void PD(int ind)
	{
		if (Tree[ind].lazy == -1)
		{
			Tree[ind << 1].lazy = Tree[ind << 1 | 1].lazy = -1;
			Tree[ind << 1].colored = Tree[ind << 1 | 1].colored = 0;
			Tree[ind].lazy = 0;
			return;
		}
		if (Tree[ind].lazy == 1)
		{
			Tree[ind << 1].lazy = Tree[ind << 1 | 1].lazy = 1;
			Tree[ind << 1].colored = Tree[ind << 1].r - Tree[ind << 1].l + 1;
			Tree[ind << 1 | 1].colored = Tree[ind << 1 | 1].r - Tree[ind << 1 | 1].l + 1;
			Tree[ind].lazy = 0;
			return;
		}
	}
	void PU(int ind)
	{
		Tree[ind].colored = Tree[ind << 1].colored + Tree[ind << 1 | 1].colored;
	}
	void Modify(int ind, int l, int r, int ope)	//Ope:Operations:1->color,2->discolor
	{
		if (l >= r) return;
		if (Tree[ind].l > r || Tree[ind].r < l) return;
		if (Tree[ind].lazy == ope) return;
		if (l <= Tree[ind].l && Tree[ind].r <= r)
		{
			Tree[ind].lazy = ope;
			if (ope == -1 || ope == 0) Tree[ind].colored = 0;
			else Tree[ind].colored = Tree[ind].r - Tree[ind].l + 1;
			return; 
		}
		PD(ind);
		Modify(ind << 1, l, r, ope);
		Modify(ind << 1 | 1, l, r, ope);
		PU(ind);
	}
};
SegmentTree st;
int N, M;
int main(int argc, char **argv)
{
	ios::sync_with_stdio(false);
	cin >> N >> M;
	st.Build(1, 1, N);
	for (register int i = 1; i <= M; ++i)
	{
		int ope, l, r;
		cin >> ope >> l >> r;
		if (ope == 1) st.Modify(1, l, r - 1, 1);	//记得这边要是r - 1 
		else st.Modify(1, l, r - 1, -1);
	}
	cout << st.Tree[1].colored << endl;
	return 0;
}