[NOI.AC#33]bst 线段树

链接

区间修改，完全二叉树，这引导我们把这棵树看成一棵线段树 。线段树的每一个节点相当于这棵二叉树的节点，

对于区间交换操作，我们对二叉树的每一层从上到下分别考虑，找到L,R在第i层对应的节点修改

这里有个技巧：在第i层，把这棵线段树的第i层当做叶子节点，即值域变为 \(1\dots2^i\)

每个点维护一个标记和一个翻转，标记存被翻转的深度集合，翻转标记记录该点是否被翻转

然后递归时，检查该点是否被翻转，如果被翻转，则进入另外的子树

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i(a);i<=(b);++i)

using namespace std;

struct FastIO{

    static const int S=1310720;

    char buf[S],wbuf[S],*si=buf,*ti=buf,*so=wbuf,*to=wbuf+S;

    ~FastIO(){fwrite(wbuf,1,so-wbuf,stdout);}

	#define gc (si==ti&&(ti=buf+fread(si=buf,1,S,stdin),si==ti)?EOF:*si++)

	template<typename T>inline void read(T&w){register char c,p=0;

		while(isspace(c=gc));if(c=='-')p=1,c=gc;

		for(w=c&15;isdigit(c=gc);w=w*10+(c&15));if(p)w=-w;

	}

	inline int read(){register int x;return read(x),x;}

	#define pc(c) (so==to?fwrite(wbuf,1,S,stdout),so=wbuf,*so++=c:*so++=c)

	template<typename T>inline void print(T w,char c='\n'){

		static char s[25];int top=0;

        if(w<0)pc('-'),w=-w;if(w==0)pc('0');

        for(top=0;w;w/=10)s[++top]=w%10;

        while(top)pc(s[top--]|'0');pc(c);

	}

	#undef gc

}io;

#define read io.read

const int N=1<<22;

int n,q;

#define ls o<<1

#define rs o<<1|1

int tag[N];bool rev[N];

inline void change(int o,int d,int v){tag[o]^=v;if(v>>d&1)rev[o]^=1;}

#define pushdown() if(tag[o])change(ls,d+1,tag[o]),change(rs,d+1,tag[o]),tag[o]=0

inline void update(int o,int l,int r,int d,int x,int y,int z){

	if(x<=l&&r<=y)return change(o,d,1<<z);

	int mid=l+r>>1;pushdown();

	if(x<=mid)rev[o]?update(rs,mid+1,r,d+1,x+r-mid,y+r-mid,z):update(ls,l,mid,d+1,x,y,z);

	if(y>mid)rev[o]?update(ls,l,mid,d+1,x-r+mid,y-r+mid,z):update(rs,mid+1,r,d+1,x,y,z);

}

inline int ask(int o,int l,int r,int d,int x){

	if(l==r)return l;

	int mid=l+r>>1;pushdown();

	if(rev[o])return x<=mid?ask(rs,mid+1,r,d+1,x+r-mid):ask(ls,l,mid,d+1,x-r+mid);

	return x<=mid?ask(ls,l,mid,d+1,x):ask(rs,mid+1,r,d+1,x);

}

int main(){

	n=read(),q=read();

	while(q--){

		int op=read(),x=read(),y;

		if(op==1){

			y=read();

			REP(i,0,n-1){

				int l=max(1<<i,x)-(1<<i),r=min((1<<i+1)-1,y)-(1<<i);

				if(l<=r)update(1,0,(1<<i)-1,0,l,r,i);

			}

		}else io.print(ask(1,0,(1<<n)-1,0,x-1)+1);

	}

	return 0;

}