学步园

简单题(easy)

有一个n个元素的数组，每个元素初始均为0。有m条指令，要么让其中一段连续序列数字反转——0变1，1变0（操作1），要么询问某个元素的值（操作2）。 

【输入文件】

输入文件easy.in第一行包含两个整数n，m，表示数组的长度和指令的条数，以下m行，每行的第一个数t表示操作的种类。若t=1，则接下来有两个数L,R
(L<=R)，表示区间[L,R]的每个数均反转；若t=2，则接下来只有一个数I，表示询问的下标。

 【输出文件】

    每个操作2输出一行（非0即1），表示每次操作2的回答。

【样例】

【限制】

50%的数据满足：1<=n<=1,000，1<=m<=10,000

100%的数据满足：1<=n<=100,000，1<=m<=500,000

测试数据下载：http://download.csdn.net/detail/yuyanggo/5253353

解析：线段树入门，用一个树形结构存储区间被翻转的次数，1代表区间1。。n,2代表区间1。。(n/2),3代表区间(n/2)+1。。n,。。。。。

若要翻转区间[l,r],那么就从上到下，依次对完全包含在[l,r]内的节点j的sum值加1，j的子节点就不必再进行翻转了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define maxn 400000+100
using namespace std;

int n,sum[maxn];

void init()
{
  freopen("easy.in","r",stdin);
  freopen("easy.out","w",stdout);
}
//在p号树节点所代表的区间【z，y】中，翻转区间【l，r】 
void modify(int p,int z,int y,int l,int r)
{
  if(z>=l&&y<=r){++sum[p];return;}
  int m=(z+y)>>1,k=p<<1;
  if(l<=m)modify(k,z,m,l,r);
  if(r>m)modify(k+1,m+1,y,l,r);
}
//从树顶1到p(代表区间【i，i】)的路径上，所有sum之和即为区间[i,i]被翻转的总次数 
int find(int i)
{
  int p=1,l=1,r=n,zo=0,m;
  while(l<r)//单l=r时，即找到区间【i，i】所对应的的树节点p，此处不能写成l<=r 
    {
	  zo+=sum[p],m=(l+r)>>1;
	  if(i<=m) r=m,p=p<<1;
	  else l=m+1,p=(p<<1)+1;
	}
  return (zo+=sum[p])%2;	
}

void work()
{
  int m;  scanf("%d%d",&n,&m);
  memset(sum,0,sizeof(int)*(4*n));
  int i,t,l,r;
  for(i=1;i<=m;i++)
    {
	  scanf("%d",&t);
	  if(t==1)
	    scanf("%d%d",&l,&r),modify(1,1,n,l,r);
	  else
        scanf("%d",&l),printf("%d\n",find(l));	  
	}
}

int main()
{ 
  init();
  work();
  return 0;
}