B. Light bulbs

B. Light bulbs

There are NNN light bulbs indexed from 000 to N−1N-1N−1. Initially, all of them are off.

A FLIP operation switches the state of a contiguous subset of bulbs. FLIP(L,R)FLIP(L, R)FLIP(L,R) means to flip all bulbs xxx such that L≤x≤RL leq x leq RL≤x≤R. So for example, FLIP(3,5)FLIP(3, 5)FLIP(3,5) means to flip bulbs 333 , 444 and 555, and FLIP(5,5)FLIP(5, 5)FLIP(5,5) means to flip bulb 555.

Given the value of NNN and a sequence of MMM flips, count the number of light bulbs that will be on at the end state.

InputFile

The first line of the input gives the number of test cases, TTT. TTT test cases follow. Each test case starts with a line containing two integers NNN and MMM, the number of light bulbs and the number of operations, respectively. Then, there are MMM more lines, the iii-th of which contains the two integers LiL_iLi​ and RiR_iRi​, indicating that the iii-th operation would like to flip all the bulbs from LiL_iLi​ to RiR_iRi​ , inclusive.

1≤T≤10001 leq T leq 10001≤T≤1000

1≤N≤1061 leq N leq 10^61≤N≤106

1≤M≤10001 leq M leq 10001≤M≤1000

0≤Li≤Ri≤N−10 leq L_i leq R_i leq N-10≤Li​≤Ri​≤N−1

OutputFile

For each test case, output one line containing Case #x: y, where xxx is the test case number (starting from 111) and yyy is the number of light bulbs that will be on at the end state, as described above.

样例输入

2
10 2
2 6
4 8
6 3
1 1
2 3
3 4

样例输出

Case #1: 4

Case #2: 3

题意：

   N 个 灯泡（编号 0 ~ N-1） M 次操作(初始灯都是关的)

   每次操作 给 2个数 L, R,把[L, R]区间内的开关翻转 

   求 M次操作后 有多少灯开着 

题解：
　　把操作区间的左右位置le,ri离散化到一维数组b中，，记录每个区间被操作的次数，最后前缀和判断奇偶即可

//B. Light bulbs
#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
using namespace std;
int a[1000005],b[2005];//a是记录操作次数，b是记录区间离散化到数组中的位置
int main()
{
    int t;
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        int n,m,cnt=0;
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        for(int i=1;i<=m;i++)
        {
            int le,ri;
            scanf("%d%d",&le,&ri);
            if(a[le]==0)
                b[cnt++]=le;
            if(a[++ri]==0)
                b[cnt++]=ri;
            a[le]++;
            a[ri]++;
        }
        sort(b,b+cnt);
        int ans=0;
        ll num=a[b[0]];
        for(int i=1;i<cnt;i++)
        {
            if(num%2==1)
                ans=ans+b[i]-b[i-1];//区间长度就是亮灯个数
            num=num+a[b[i]];//求区间[0,b[i]]所有灯泡操作次数
        }
        printf("Case #%d: %d
",k,ans);

    }
    return 0;
}