Light bulbs （树状数组模板题）

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

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

Given the value of N and a sequence of M 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, T. T test cases follow. Each test case starts with a line containing two integers N and M, the number of light bulbs and the number of operations, respectively. Then, there are M more lines, the i-th of which contains the two integers Li? and Ri?, indicating that the ii-th operation would like to flip all the bulbs from Li? to Ri? , inclusive.

1≤T≤1000

1 ≤N≤1000000

1 ≤M≤1000

0≤Li?≤Ri?≤N−1

OutputFile

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 11) and yyis 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个灯，m次操作，每次把一个区间的灯反转，最初都是暗的，问最后有多少灯是亮的；
题解：树状数组，每次调用add（）函数把L处加一，R+1处减一，然后最后把每一个区间用排序去重之后计算当前区间处L（只用L就够了）被加了多少次（通过调用ask（）函数计算），偶数就代表当前区间的灯都是关的，反之就是开的，然后这个区间长度就是
（str[i+1]-1）-str[i]+1；
还有就是记得内存限制；
最后每一次树状数组清零时是通过保存输入进行清零的，L处减一，R+1处加一；
总的复杂度是O（t*m*log（n））；

#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
const int maxn=2e3+5;
int str[maxn],str2[maxn],c[1000005],n,m;
int ask(int x)
{
    int ans=0;
    for(; x; x-=x&-x)ans+=c[x];
    return ans;
}
void add(int x,int y)
{
    for(; x<=n; x+=x&-x)c[x]+=y;
}
template<class T>
inline void read(T&x)
{
    T ans=0,f=1;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘)
    {
        if(ch==‘-‘)f=-1;
        ch=getchar();
    }
    while(ch>=‘0‘&&ch<=‘9‘)
    {
        ans=ans*10+ch-‘0‘;
        ch=getchar();
    }
    x=ans*f;
}
int main()
{
    int t,l,r,cnt=0,k=0;
    read(t);
    while(t--)
    {
        cnt=0;
        read(n);
        read(m);
        int m2=m;
        while(m2--)
        {
            read(l);read(r);
            ++l,++r;
            add(l,1);
            add(r+1,-1);
            str[++cnt]=l,str2[cnt]=l;
            str[++cnt]=r+1,str2[cnt]=r+1;
        }
        sort(str+1,str+cnt+1);
        int cnt2=0;
        for(int i=1; i<=cnt; ++i)
        {
            if(str[i]!=str[cnt2])
                str[++cnt2]=str[i];
        }
        int ans=0,flag;
        for(int i=1; i<cnt2; ++i)
        {
            flag=ask(str[i]);
            if((flag&1)==1)
                ans+=str[i+1]-1-str[i]+1;
        }
        printf("Case #%d: %d\n",++k,ans);
        for(int i=1; i<=2*m; i+=2)
        {
            add(str2[i],-1);
            add(str2[i+1],1);
        }
    }
    return 0;
}