2019上海网络赛 - Light bulbs

题目链接：Light bulbs

一道离散化+差分
由于区间很大，我们不能直接去差分，必然TLE，但是我们可以注意到修改次数十分小，于是我们可以想到离散化之后再差分。

对于求解答案，我们可以只分析区间。同时根据差分的思想，用一个变量记录前缀和。如果当前是左区间则加一，否则减一（右区间）。然后每次记录答案，如果当前的前缀和为奇数，那么代表是亮的，于是我们答案加上当前后面的那个值，与当前这个值之间的和，因为这个区间没有操作能改变它们了。注意不能加到后面那个值的位置，因为那是未知的，可能被后续操作改变。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int T,n,m,ts,res,s,tot;
struct node{
	int x,id;
}t[N<<1];
int cmp(const node s1,const node s2){
	return s1.x<s2.x;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>m;	res=s=tot=0;
		for(int i=1;i<=m;i++){
			int a,b;	cin>>a>>b;
			t[++tot]={a,1};	t[++tot]={b+1,-1};
		}
		sort(t+1,t+1+tot,cmp);
		for(int i=1;i<=tot;i++){
			s+=t[i].id;
			if(s&1)	res+=(t[i+1].x-t[i].x);
		}
		printf("Case #%d: %d\n",++ts,res);
	}
	return 0;
}