light oj 1080 Binary Simulation (线段树lazy标记，区间更新，单点查询)
题意：给出一个长度为n的数列，每个位置是0或者1，给出q个操作，操作有两种类型，分别是将一段区间中反转，和询问当前某位置是0还是1
思路：lazy标记。lazy[i]记录以i节点为根节点的子树对应的区间中被翻转的次数，初始为0.然后查询的时候，根据被翻转次数的奇偶性确定答案。
wa了好多发。。。比较致命的是。。PushDown函数忘记改了。。。还按照染色的方法直接赋值的。。。然而这里是统计次数。。。所以是累加。。。。
1/* ***********************************************
2Author :111qqz
3Created Time :Wed 14 Sep 2016 12:59:07 AM CST
4File Name :code/loj/1080.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int lazy[N<<2];//记录翻转次数
33int n;
34string st;
35int a[N];
36void PushDown( int rt)
37{
38 if (lazy[rt])
39 {
40 lazy[rt<<1] +=lazy[rt];
41 lazy[rt<<1|1]+=lazy[rt];
42 lazy[rt] = 0;
43 }
44}
45void build(int l,int r,int rt)
46{
47 if (l==r)
48 {
49 lazy[rt] = 0;
50 return;
51 }
52 int m = (l+r)>>1;
53 build(lson);
54 build(rson);
55}
56void update(int L,int R,int l,int r,int rt)
57{
58 if (L<=l&&r<=R)
59 {
60 lazy[rt]++;
61 return;
62 }
63 PushDown(rt);
64 int m = (l+r)>>1;
65 if (L<=m) update(L,R,lson);
66 if (R>=m+1) update(L,R,rson);
67}
68int query( int p,int l,int r,int rt)
69{
70 if (l==r) return lazy[rt];
71 PushDown(rt);
72 int m = (l+r)>>1;
73 //int res;
74 if (p<=m) query(p,lson);
75 else query(p,rson);
76 // return res;
77}
78int main()
79{
80 #ifndef ONLINE_JUDGE
81 freopen("code/in.txt","r",stdin);
82 #endif
83 int T;
84 cin>>T;
85 int cas= 0 ;
86 while (T--){
87 ms(lazy,0);
88 ms(a,0);
89 cin>>st;
90 n = st.length();
91 for ( int i = 0 ; i < n ; i++)
92 {
93 a[i+1] = st[i]-'0';
94 }
95 build(1,n,1);
96 printf("Case %d:\n",++cas);
97 int q;
98 cin>>q;
99 while (q--)
100 {
101 char opt[3];
102 int x,y;
103 scanf("%s",opt);
104 if (opt[0]=='I')
105 {
106 scanf("%d%d",&x,&y);
107 update(x,y,1,n,1);
108 }
109 else
110 {
111 scanf("%d",&x);
112 int p = query(x,1,n,1);
113 int ans;
114 if (p%2==1) ans = 1-a[x];
115 else ans = a[x];
116 printf("%d\n",ans);
117 }
118 }
119 }
120 #ifndef ONLINE_JUDGE
121 fclose(stdin);
122 #endif
123 return 0;
124}