分块，#8 1.08s，#9 1.10s，tle求条

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
#include <stack>
using namespace std;

#define int long long
#define maxn 500005

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void out(int x){
    if(x<0)putchar('-'),x=-x; 
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
int n,m;
int a[maxn];
int k[1005];
int tag[1005];
int kcnt;

signed main(){
	n=read();m=read();
	kcnt=sqrt(n);
	for(int i=0;i<n;++i) a[i]=0;
	while(m){
	    m--;
		int opt;
		opt=read();
		int wym1,wym2;
		if(opt==1){
			int l,r;
			l=read();r=read();
			l--;r--;
			wym1=l/kcnt;wym2=r/kcnt;
			if(wym1==wym2){
				for(int i=l;i<=r;++i){
					a[i]^=1;
					if(a[i]!=tag[i/kcnt]){
						++k[i/kcnt];
					}
					else{
						--k[i/kcnt];
					}
				}
				continue;
			}//一个块内的修改
			if(l%kcnt!=0){
				for(int i=l;i<=(wym1+1)*kcnt-1;++i){
					a[i]^=1;
					if(a[i]!=tag[i/kcnt]){
						++k[i/kcnt];
					}
					else{
						--k[i/kcnt];
					}
				}
				++wym1;
			}
			if((r+1)%kcnt!=0){
				for(int i=wym2*kcnt;i<=r;++i){
					a[i]^=1;
					if(a[i]!=tag[i/kcnt]){
						++k[i/kcnt];
					}
					else{
						--k[i/kcnt];
					}
				}
				--wym2;
			}//单点的修改
			for(int i=wym1;i<=wym2;++i){
				k[i]=kcnt-k[i];//区间修改
				tag[i]^=1;//单点修改
			}
		}
		else{
			int ans=0;
			int l;l=read();l--;
			if(a[l]!=tag[l/kcnt]){
			    out(1);printf("\n");
			}
			else{out(0);printf("\n");}
		}
	}
	return 0;
}