从零开始学算法/C++/第三天

懒标记好简单,原理就是使变化的叠加尽可能远离叶子节点，
也就是说从叶子节点往根节点走，这条路径上最多只有一个地方有懒标记 ，要将这个懒标记尽可能远离叶子节点，拖延症了属于是，这样显然时间复杂度相较不用懒标记的要低很多。
算法竞赛进阶指南里面称懒标记为延迟标记，这两种称呼都很好。
今天做了两道题[https://www.acwing.com/problem/content/244/](AcWing 243 一个简单的整数问题2)/[https://www.luogu.com.cn/problem/P3870](P3870 [TJOI2009] 开关)
整数问题琢磨了一会儿，主要在于变化函数和查询函数都要下传懒标记，已经想明白了（原理就是本博客的第二行），后面写洛谷的题十分钟秒了。

一个简单的整数问题2 https://www.acwing.com/problem/content/244/

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 1;
long long w[N];
struct node
{
	int l, r;
	long long sum, add;
}t[N << 2];
void build(int p, int l, int r)
{
	t[p] = { l,r };
	if (l == r) { t[p] = { l,l,w[l],0 }; return; }
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}
void lyy(int p)
{
	if (t[p].add)
	{
		t[p << 1].add += t[p].add;
		t[p << 1 | 1].add += t[p].add;
		t[p << 1].sum += t[p].add * (t[p << 1].r - t[p << 1].l + 1);
		t[p << 1 | 1].sum += t[p].add * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1);
		t[p].add = 0;
	}
}
void modify(int p, int l, int r, long long d)
{
	if (l <= t[p].l && t[p].r <= r)
	{
		t[p].sum += d * (t[p].r - t[p].l + 1);
		t[p].add += d;
		return;
	}
	lyy(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid)modify(p << 1, l, r, d);
	if (r > mid)modify(p << 1 | 1, l, r, d);
	t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}
long long ffind(int p, int l, int r)
{
	if (l <= t[p].l && t[p].r <= r)return t[p].sum;
	lyy(p);
	int mid = t[p].l + t[p].r >> 1;
	if (r <= mid)return ffind(p << 1, l, r);
	else if (l > mid)return ffind(p << 1 | 1, l, r);
	else return ffind(p << 1, l, r) + ffind(p << 1 | 1, l, r);
}
int n, m, l, r;
char ch;
long long d;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)cin >> w[i];
	build(1, 1, n);
	while (m--)
	{
		cin >> ch >> l >> r;
		if (ch == 'C')
			cin >> d, modify(1, l, r, d);
		else cout << ffind(1, l, r) << endl;
	}
	return 0;
}

P3870 [TJOI2009] 开关 https://www.luogu.com.cn/problem/P3870

#include <iostream>
using namespace std;
const int N = 1e5 + 1;
int w[N];
struct node
{
	int l, r, sum, add;
}t[N << 2];
void build(int p, int l, int r)
{
	t[p] = { l,r };
	if (l == r) { t[p] = { l,l,0 }; return; }
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}
void lyy(int p)
{
	if (t[p].add & 1)
	{
		t[p << 1].sum = t[p << 1].r - t[p << 1].l + 1 - t[p << 1].sum;
		t[p << 1 | 1].sum = t[p << 1 | 1].r - t[p << 1 | 1].l + 1 - t[p << 1 | 1].sum;
		++t[p << 1].add;
		++t[p << 1 | 1].add;
		t[p].add = 0;
	}
	else t[p].add = 0;
}
void modify(int p, int l, int r)
{
	if (l <= t[p].l && t[p].r <= r)
	{
		++t[p].add;
		t[p].sum = t[p].r - t[p].l + 1 - t[p].sum;
		return;
	}
	lyy(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid)modify(p << 1, l, r);
	if (r > mid)modify(p << 1 | 1, l, r);
	t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
}
int ffind(int p, int l, int r)
{
	if (l <= t[p].l && t[p].r <= r)return t[p].sum;
	lyy(p);
	int mid = t[p].l + t[p].r >> 1;
	if (r <= mid)return ffind(p << 1, l, r);
	else if (l > mid)return ffind(p << 1 | 1, l, r);
	else
	{
		return ffind(p << 1, l, r) + ffind(p << 1 | 1, l, r);
	}
}
int n, m, c, a, b;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	build(1, 1, n);
	while (m--)
	{
		cin >> c >> a >> b;
		if (a > b)swap(a, b);
		if (c)cout << ffind(1, a, b) << endl;
		else modify(1, a, b);
	}
	return 0;
}

算法竞赛进阶指南p241的扫描线看着好难，还是看看远方的分块算法吧。