题意
T组案例，每组案例：n个灯泡（from 0 to n-1），m次操作，每次操作把区间[L,R]内的灯泡翻转(开变关，关变开)，问m次操作之后有多少灯泡是亮着的。（时间限制：1000ms 内存限制：8192K）
题解
这道题不仅卡时间，更是卡内存，所以用线段树会爆内存
正解：
该题可以转换为经典的差分问题：每次操作对[L,R]的所有数进行+1操作，求最后有多少个奇数。（设该数组为a[n],每次操作a[L]+1,a[R+1]-1,求前缀和sum[i]=sum[i-1]+a[i]即可得到进行区间所有数+1操作后每个数的值sum[i])
利用差分的思想，但如果是遍历n还是会超时超内存，此题m较小，所以可以从m下手，只需存端点，最后遍历所有端点即可。官方题解如下：
Code
#include<bits/stdc++.h> using namespace std; const int maxn=2005; pair<int,int>p[maxn]; int main() { int T,cas=0; scanf("%d",&T); while(T--){ int n,m,l,r,cnt=0; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&l,&r); p[cnt++]=make_pair(l,1); p[cnt++]=make_pair(r+1,-1); } sort(p,p+cnt); int sum=0,now=0,ans=0; for(int i=1;i<cnt;i++){ sum+=p[i].second; if(sum&1) ans+=p[i].first-p[i-1].first; } printf("Case #%d: %d\n",++cas,ans); } return 0; }
差分：
何为差分？差分就是将数列中的每一项分别与前一项数做差。
例如：原数列a[n]，差分数列b[n]，b[i]=a[i]-a[i-1]，a[i]=差分数列的前缀和sum[i]。
（注意：1.差分序列的第一个数和原来的第一个数一样，相当于第一个数去减0；2.差分序列最后会比原序列多一个数，相当于0减最后一个数）
一个序列原本为 1 3 5 2 9 3，差分后得到 1 2 2 -3 7 -6。
两个性质：
①差分序列求前缀和可得原序列；
②原序列区间[L,R]中的元素全部+K，可以转化操作为差分序列L处+K，R+1处-K；