【线段树】P2846 [USACO08NOV] Light Switching G|LG4|普及+

本文涉及知识点

C++线段树

[USACO08NOV] Light Switching G

题目描述

Farmer John tries to keep the cows sharp by letting them play with intellectual toys. One of the larger toys is the lights in the barn. Each of the $N(2\le N\le 10^5)$ cow stalls conveniently numbered $1\dots N$ has a colorful light above it.

At the beginning of the evening, all the lights are off. The cows control the lights with a set of N pushbutton switches that toggle the lights; pushing switch i changes the state of light i from off to on or from on to off.

The cows read and execute a list of $M(1\le M\le 10^5)$ operations expressed as one of two integers ( $0\le$ operation $\le 1$ ).

The first kind of operation (denoted by a $0$ command) includes two subsequent integers $S_i$ and $E_i(1\le S_i\le E_i\le N)$ that indicate a starting switch and ending switch. They execute the operation by pushing each pushbutton from $S_i$ through $E_i$ inclusive exactly once.

The second kind of operation (denoted by a $1$ command) asks the cows to count how many lights are on in the range given by two integers $S_i$ and $E_i(1\le S_i\le E_i\le N)$ which specify the inclusive range in which the cows should count the number of lights that are on.

Help FJ ensure the cows are getting the correct answer by processing the list and producing the proper counts.

农夫约翰试图让奶牛玩智力玩具来保持它们的敏锐。谷仓里的灯是较大的玩具之一。$N(2\le N\le 10^5)$ 个牛栏编号为 $1\dots N$，每个牛栏上面都有一盏灯。起初所有的灯都关着。

共有 $M$ 次操作，分为两种。

1. 指定一个区间 $[S_i,E_i]$，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
2. 指定一个区间 $[S_i,E_i]$，要求你输出这个区间内有多少盏灯是打开的。

输入格式

第 $1$ 行: 用空格隔开的两个整数 $N$ 和 $M$，$N$ 是灯数。

第 $2\dots M+1$ 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, $S_i$ 和 $E_i$。

若指令号为 $0$，则表示改变 $[S_i,E_i]$ 区间内的灯的状态（把开着的灯关上，关着的灯打开）。

若指令号为 $1$，则表示输出 $[S_i,E_i]$ 这个区间内有多少盏灯是打开的。

输出格式

样例 #1

样例输入 #1

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

样例输出 #1

1
2

提示

数据点编号	$N$	$M$
$1\sim 2$	$\le 100$	$\le 100$
$3\sim 4$	$\le 1000$	$\le 1000$
$5\sim 6$	$\le 10000$	$\le 10000$
$7\sim 8$	$\le 10^5$	$\le 100$
$9\sim 10$	$\le 100$	$\le 10^5$
$11\sim 12$	$\le 1000$	$\le 10^5$
$13\sim 14$	$\le 10^5$	$\le 1000$
$15\sim 16$	$\le 10000$	$\le 10000$
$17\sim 18$	$\le 10$	$\le 10^5$
$19\sim 20$	$\le 2000$	$\le 10^6$

求和线段树

相加后对2取模。
保存类型int: 当前节点有多少盏灯开着。
设置缓存类型int：开灯、关灯次数。
叶子节点和非叶子节点的更新函数相同：

virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) override
{
if (0 == update % 2) { return; }
save = (iSaveRight - iSaveLeft + 1) - save;
}

代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for(int i=0;i < n ;i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 12 * 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;}inline void write(char ch){*m_p++ = ch;}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);}
private:char  puffer[N], * m_p;
};template<int N = 12 * 1'000'000>
class CInBuff
{
public:inline CInBuff() {fread(buffer, 1, N, stdin);}inline int Read() {int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);return f ? -x : x;}
private:char buffer[N], * S = buffer;
};template<class TSave, class TRecord >
class CRangUpdateLineTree
{
protected:virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight) = 0;virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) = 0;virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight) = 0;virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
};template<class TSave, class TRecord >
class CVectorRangeUpdateLineTree : public CRangUpdateLineTree<TSave, TRecord>
{
public:CVectorRangeUpdateLineTree(int iEleSize, TSave tDefault, TRecord tRecordNull) :m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_record(iEleSize * 4, tRecordNull) {m_recordNull = tRecordNull;}void Update(int iLeftIndex, int iRightIndex, TRecord value){Update(1, 0, m_iEleSize - 1, iLeftIndex, iRightIndex, value);}void Query(int leftIndex, int rightIndex) {Query(1, 0, m_iEleSize - 1, leftIndex, rightIndex);}//void Init() {//	Init(1, 0, m_iEleSize - 1);//}TSave QueryAll() {return m_save[1];}void swap(CVectorRangeUpdateLineTree<TSave, TRecord>& other) {m_save.swap(other.m_save);m_record.swap(other.m_record);std::swap(m_recordNull, other.m_recordNull);assert(m_iEleSize == other.m_iEleSize);}
protected://void Init(int iNodeNO, int iSaveLeft, int iSaveRight)//{//	if (iSaveLeft == iSaveRight) {//		this->OnInit(m_save[iNodeNO], iSaveLeft);//		return;//	}//	const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;//	Init(iNodeNO * 2, iSaveLeft, mid);//	Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);//	this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);//}void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {this->OnQuery(m_save[iNodeNO], iSaveLeft, iSaveRight);return;}if (iSaveLeft == iSaveRight) {//没有子节点return;}Fresh(iNodeNO, iSaveLeft, iSaveRight);const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (mid >= iQueryLeft) {Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);}if (mid + 1 <= iQueryRight) {Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);}}void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value){if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight)){this->OnUpdate(m_save[iNode], iSaveLeft, iSaveRight, value);this->OnUpdateRecord(m_record[iNode], value);return;}if (iSaveLeft == iSaveRight) {return;//没有子节点}Fresh(iNode, iSaveLeft, iSaveRight);const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;if (iMid >= iOpeLeft){Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);}if (iMid + 1 <= iOpeRight){Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);}// 如果有后代，至少两个后代this->OnUpdateParent(m_save[iNode], m_save[iNode * 2], m_save[iNode * 2 + 1], iSaveLeft, iSaveRight);}void Fresh(int iNode, int iDataLeft, int iDataRight){if (m_recordNull == m_record[iNode]){return;}const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_record[iNode]);Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_record[iNode]);m_record[iNode] = m_recordNull;}vector<TSave> m_save;vector<TRecord> m_record;TRecord m_recordNull;const int m_iEleSize;
};typedef int TSave;
typedef int  TRecord;
class  CMyLineTree : public  CVectorRangeUpdateLineTree<TSave, TRecord>
{
public:int m_ans = 0;using CVectorRangeUpdateLineTree::CVectorRangeUpdateLineTree;
protected:virtual void OnQuery(const TSave& save, const int& iSaveLeft, const int& iSaveRight) {m_ans += save;}virtual void OnUpdate(TSave& save, const int& iSaveLeft, const int& iSaveRight, const TRecord& update) override{if (0 == update % 2) { return; }save = (iSaveRight - iSaveLeft + 1) - save;}virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, const int& iSaveLeft, const int& iSaveRight)  override{par = left + r;}virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override{old = (old + newRecord) % 2;}
};//P2846 [USACO08NOV] Light Switching G
class Solution {
public:vector<int> Ans(const int N, vector<tuple<int, int, int>>& que) {CMyLineTree lineTree(N + 1, 0, 0);vector<int> ans;for (const auto& [kind, L, R] : que) {if (0 == kind) {lineTree.Update(L, R, 1);}else {lineTree.m_ans = 0;lineTree.Query(L, R);ans.emplace_back(lineTree.m_ans);}}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	int n, q;cin >> n >> q;auto que = Read<tuple<int, int, int>>(q);auto res = Solution().Ans(n,que);COutBuff<24*1000'000> ob;for (const auto& i : res) {ob.write(i);ob.write('\n');}ob.ToFile();
#ifdef _DEBUG	printf(",n=%d,", n);Out(que, "que=");	
#endif // DEBUG	return 0;
}

单元测试

int n;vector<tuple<int, int, int>> que;TEST_METHOD(TestMethod11){n = 4, que = { {0,1,2},{0,2,4},{1,2,3},{0,2,4},{1,1,4} };auto res = Solution().Ans(n, que);AssertEx({ 1,2 }, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。