前言
最近有很多算不上事的事，搞得有点心烦，补题难免就很水，没怎么搞，自我检讨一番~~
说实话网络赛题目的质量还是挺高的，题目都设计的挺好的，很值得学习。这场比赛那会只有我们大二的在做，其他人去参加$CCF$认证去了，赛后这题搞出来了，跟$lsq$一顿解释，说这个其实也不难，她就说但是你看就这个地方卡了多少人，那会才两百多人过了。的确，有的题目还是很考思维的。（个人感觉很久没写博客，写这篇还是有点混乱的，有些博主把这题加上离散化的标签，想起来好像是有那么点道理）
题意
有 $n $个灯泡，初始全部为关闭状态，有$ m $个操作，每次操作给出 $[l,r]$，让你将区间 $[l,r] $的灯泡反转，问最终有多少灯泡是亮着的。$[ link ]$
其中有 $T $组数据，$T leq 1000, n leq 10^{6}, m leq 1000$
分析
当时刚开始做的时候，那会因为刚好看了两天的差分，就觉得这题很对我胃口，肯定能搞出来，然而事实给了我一巴掌，$TLE$
我当时就想不通了明明是$O(n)$的做法，后来仔细一看，复杂度$T*n$，$10^{9}$多半是不行了，毕竟每次都还要把差分数组初始化为0。开始用到$for$循环初始化，也超时了，就换成了$memset$。后来$zym$提醒说$memset$很花时间，我就想多拿几个数组记录一下，把原来的状态的还原回去，结果开了四个数组，空间超了$cdots $，可能出题人也想到了有人会像我这样做（网上有博主好像用这种方法做出来了，具体的还没有看）这我就没有办法了，才不得不放弃。
$0(n)$的做法是利用差分每次只需要修改两个端点，最后求前缀和，是奇数就代表是灯是亮着的。（自认为是差分的精髓所在）这题需要强调的是对于每个端点修改的是一整个区间(以这个端点为最左边直到最右边的边界)，每组$l,r$，$l$和$r+1$所对应的区间都会加1，两者操作是一样的，所以对于所有要修改的区间的修改顺序是无所谓的，因此我把这些代表区间的端点进行排序，$a_{1}$ $to$ $a_{2}$, $a_{3} $ $to$ $ a_{4} ,cdots , a_{k-1}$ $to$ $a_{k}$两两相减加起来就能得到答案，在草稿纸上画一画想一想应该就知道了，并不需要把前缀和都求一遍。
Code
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6+5; int n, m; int a[maxn]; int main() { int t; scanf("%d", &t); for (int kase = 1; kase <= t; kase++) { scanf("%d%d", &n, &m); int k = 0; for (int i = 1; i <= m; i++) { int l, r; scanf("%d%d", &l, &r); a[++k] = l; a[++k] = r+1; } sort(a+1, a+1+k); int ans = 0; for (int i = 1; i <= k; i+=2) ans += a[i+1]-a[i]; printf("Case #%d: %d ", kase, ans); } }
参考文章：