描述:

  给定n个硬币，编号为0, 1, 2, ......, n-1，都为反面朝上（即都为0）。有m次操作，每次将a, b区间内的硬币翻转，请输出翻转后的硬币排列。

输入：

5 2

输出：

10110

解析：

  对于该题，最简单的做法是模拟，即建立数组s[n]，初始化为0，然后每次将[a, b]上的数字+1，最后顺序输出。如果s[i]为偶数，则为0面朝上，否则为1面朝上。这种做法的修改的时间复杂度为O(m*n)，输出为O(n)，当m和n都比较大的时候代价难以承受。

  显然题目要求是对区间进行操作，所以自然而然地想到了树状数组或线段树。经过模拟方法的分析后，发现操作为区间修改，求单点的值，用树状数组或线段树都可以实现。由于线段树的代码比较复杂，所以选择树状数组。

#include
    
     #include
     
      #include
      
       #include
       
        #define lowbit(a) (a&(-a))using namespace std;int n,m;int s[100100];void add(int x,int c){    for(int i=x;i>0;i-=lowbit(i)) s[i]+=c;}int sum(int x){    int r=0;    for(int i=x;i<=n;i+=lowbit(i)) r+=s[i];    return r;}int main(){    memset(s,0,sizeof(s));    cin>>n>>m;    int a,b;    for(int i=1;i<=m;i++)    {        cin>>a>>b;        add(a-1,-1);        add(b,1);    }    for(int i=1;i<=n;i++)    {        int c=sum(i);        cout<<(c&1);    }    return 0;}