给定一个长度为N的序列，起始时所有数都为0.以后有2种操作： 1:对于操作1，读入两个数x,y，表示从x到y把对应的序列上的数都做取反操作。即，该位置是0，操作以后为1；该位置是1，操作以后是0。 2:对于操作2，读入一个数x，输出当前序列中x位置上的数字。 对于两种操作，共有p次。
输入格式 Input Format
第一行，一个数N； 第二行，一个数p； 以后p行，每行第一个数表示操作k，k=1或2；对于k=1，读入两个数x，y；对于k=2，读入一个数x。
输出格式 Output Format
对于每一个操作2，输出一行，一个数为所求。
这道题目与poj的matrix一题其实是一样的，用树状数组比较方便，当然二维树状数组也可以。用树状数组就需要理解树状数组与线段树有一个类似的地方就是树状数组也是这对区间进行操作的，对于取反操作，我们完全可以想象成是一个统计问题，统计当前节点被处理了几次，但是树状数组适合于求和，这是需要考虑到取反统计的特殊性，即加两次等于没有加，这样便可以把一个点的问题变成一个区间的问题。比如要在5到10之间处理，那么我们把5~n都加1，即incc(5)，这样很容易知道5~10的内容已经被我们处理了，那么1~4我们没有动过，所以结果不会变，但是11~n也被我们处理了，这样只需要再执行一次incc(11)，即将11~n加两次，这样相当于没有变过。这样一个点的统计问题就可以变成一个区间的统计问题。
1 var 2 c:array[0..200000] of longint; 3 k,i,n,p,x,y:longint; 4 5 procedure incc(x:longint); 6 begin 7 while x<=n do 8 begin 9 c[x]:=(c[x]+1)mod 2; 10 inc(x,x and -x); 11 end; 12 end; 13 14 function sum(x:longint):longint; 15 var 16 k:longint; 17 begin 18 k:=0; 19 while x>0 do 20 begin 21 k:=(k+c[x])mod 2; 22 dec(x,x and -x); 23 end; 24 exit(k); 25 end; 26 27 begin 28 readln(n); 29 readln(p); 30 for i:=1 to p do 31 begin 32 read(k); 33 if k=1 then 34 begin 35 readln(x,y); 36 incc(x); 37 incc(y+1); 38 end else 39 if k=2 then 40 begin 41 readln(x); 42 writeln(sum(x)); 43 end; 44 end; 45 end.
最新评论