描述:
给定n个硬币，编号为0, 1, 2, ......, n-1，都为反面朝上（即都为0）。有m次操作，每次将a, b区间内的硬币翻转，请输出翻转后的硬币排列。
输入：
5 2
1 2
2 4
输出：
10110
解析：
对于该题，最简单的做法是模拟，即建立数组s[n]，初始化为0，然后每次将[a, b]上的数字+1，最后顺序输出。如果s[i]为偶数，则为0面朝上，否则为1面朝上。这种做法的修改的时间复杂度为O(m*n)，输出为O(n)，当m和n都比较大的时候代价难以承受。
显然题目要求是对区间进行操作，所以自然而然地想到了树状数组或线段树。经过模拟方法的分析后，发现操作为区间修改，求单点的值，用树状数组或线段树都可以实现。由于线段树的代码比较复杂，所以选择树状数组。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#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;
}