P5057 【[CQOI2006]简单题】

洛谷P5057[CQOI2006]简单题

差分

树状数组基本操作不说了，主要想记录一下异或下的差分

a数组为每一位的真实值（假设$a[0]=0$），t为差分后的数组

则$t[i]=a[i]$^$a[i-1]$

所以我们如果想要查询$a[i]$

则$a[i]=a[0]$^$a[1]$$a[1]$^$a[2]$$a[2]$^$\dots$$a[i]$^{$a[i]$=$t[1]$}$t[2]$^$\dots$$t[i]$

所以在树状数组中记录t数组，修改时指修改（异或上1）$l$和$r+1$的值就行

查询就是异或和

当然这个题的数据范围也可以分块做

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define R register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n;

inline int lowbit(int x){return x&(-x);}

int tree[100006];

inline int fq(int pos){

	R int ans=0;

	for(;pos;pos-=lowbit(pos)) ans^=tree[pos];

	return ans;

}

inline void add(int pos){

	for(;pos<=n;pos+=lowbit(pos)) tree[pos]^=1;

}

int main(){

	n=read();int m=read();

	while(m--){

		int op=read();

		if(op==1){

			int l=read(),r=read();

			add(l);add(r+1);

		}

		else std::printf("%d\n",fq(read()));

	}

	return 0;

}

巴特西

P5057 【[CQOI2006]简单题】

洛谷P5057[CQOI2006]简单题

最新文章

热门文章