线段树上维护这种括号序列，如果信息可差分是好做的，但现在只能合并。
先说如何合并信息。
- max 是简单的。
- 至于 nand，不需要考虑结合律，只要维护一个
bool[32][2]表示当某一位的第一个操作数是 0/1 时，经过它们的传递、运算的结果是什么。见于 P2114 [NOI2014] 起床困难综合症。
枚举算法发现可以用兔队线段树（单侧递归）来做。
考虑它做楼房重建（严格前缀最大值）的算法，calc 过程中，对于一棵子树，求大于 \(x\) 的严格前缀最大值个数：
- 如果处于叶子，返回节点值是否大于 \(x\)；
- 如果此树最大 <= \(x\)，返回 0；
- 如果左最大 <= \(x\)，那么只要右的答案，向右递归；
- 否则需要合并右侧传上来的答案（而不是右节点存的答案）与左侧递归答案（大于 \(x\) 的严格前缀最大值个数）。
此处右侧传上来的答案是用 tr[x].ans-tr[x*2].ans 算的。这回不能差分，所以在 x 处把这个存下来。还要存储左括号与右括号信息。
考虑它做现问题的算法，calc 过程中，对于一棵子树，求前 \(x\) 个左括号的信息：
- 如果处于叶子或左括号刚好 \(x\) 个，返回左括号信息；
- 如果 左侧左括号数 不多于 右侧右括号数，那么只要右的答案，向右递归；
- 否则考虑左侧剩余的左括号数：
- 如果不少于 \(x\) 就直接向左递归；
- 否则需要合并左侧传上来的答案（而不是左节点存的答案）与右侧递归答案。
右括号同理。
考虑交换区间。把线段树改造成 WBLT。以代码 EDU。
点击查看代码
//#define dxx
#ifdef dxx
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define dex(a) dbg(#a"=%lld onL%d infun %s\n",(ll)a,__LINE__,__FUNCTION__)
#include<cstdlib>
#define pause sys##tem("read -p \"panss2continue..\"")
#define _GLIBCXX_DEBUG
#endif
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using llu=unsigned long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}
template<class T> T sqr(T a){return a*a;}
const int NV=2e6;
int N,a[NV+5],b[NV+5];
struct INFO{
unsigned mx,tdr[2],cnt;
INFO(unsigned _mx=0,unsigned tab0=0,unsigned tab1=-1,unsigned _cnt=0){
mx=_mx;
cnt=_cnt;
tdr[0]=tab0;
tdr[1]=tab1;
}
};
INFO operator+(INFO a,INFO b){
return INFO(max(a.mx,b.mx),
~a.tdr[0]&b.tdr[0]|a.tdr[0]&b.tdr[1],
~a.tdr[1]&b.tdr[0]|a.tdr[1]&b.tdr[1],
a.cnt+b.cnt
);
}
namespace wblt{
struct SEGN{
INFO lw,rw,s;
int l,r,siz;
} tr[5000006];
int trash[NV+5],cnt,rt;
int create(){
return *trash?trash[(*trash)--]:++cnt;
}void del(int x){
trash[++*trash]=x;
}int create(int x,int y){
int z=create();
tr[z].l=tr[z].r=0;
tr[z].siz=1;
tr[z].lw=tr[z].rw=tr[z].s=INFO();
(x?tr[z].rw:tr[z].lw)=INFO(y,-1,~y,1);
return z;
}INFO quer(int x,int K){
if(tr[x].siz==1||tr[x].rw.cnt==K) return tr[x].rw;
if(tr[tr[x].l].rw.cnt<=tr[tr[x].r].lw.cnt)
return quer(tr[x].r,K);
else{
int t=tr[tr[x].l].rw.cnt-tr[tr[x].r].lw.cnt;
if(K<=t) return quer(tr[x].l,K);
else return tr[x].s+quer(tr[x].r,K-t);
}
}INFO quel(int x,int K){
if(tr[x].siz==1||tr[x].lw.cnt==K) return tr[x].lw;
if(tr[tr[x].l].rw.cnt>=tr[tr[x].r].lw.cnt)
return quel(tr[x].l,K);
else{
int t=tr[tr[x].r].lw.cnt-tr[tr[x].l].rw.cnt;
if(K<=t) return quel(tr[x].r,K);
else return quel(tr[x].l,K-t)+tr[x].s;
}
}void up(int x){
tr[x].siz=tr[tr[x].l].siz+tr[tr[x].r].siz;
const int ls=tr[x].l,rs=tr[x].r,delta=(int)tr[ls].rw.cnt-tr[rs].lw.cnt;
if(delta>0){
auto t=quer(ls,delta);
tr[x].s=t;
tr[x].lw=tr[ls].lw;
tr[x].rw=t+tr[rs].rw;
}else if(delta<0){
auto t=quel(rs,-delta);
tr[x].s=t;
tr[x].lw=tr[ls].lw+t;
tr[x].rw=tr[rs].rw;
}else{
tr[x].lw=tr[ls].lw;
tr[x].rw=tr[rs].rw;
tr[x].s=INFO(0,0,-1,0);
}
}int merge(int x,int y){
int z=create();
tr[z].l=x;
tr[z].r=y;
up(z);
return z;
}int build(int l,int r){
if(l==r) return create(a[l],b[l]);
int mid=l+r>>1;
return merge(build(l,mid),build(mid+1,r));
}void doupd(int x,int z){
if(tr[x].rw.cnt){
tr[x].rw=INFO();
tr[x].lw=INFO(z,-1,~z,1);
}else{
tr[x].lw=INFO();
tr[x].rw=INFO(z,-1,~z,1);
}
}void upd(int x,int p,int z){
if(tr[x].siz==1){
doupd(x,z);
return;
}
int mid=tr[tr[x].l].siz;
if(p<=mid) upd(tr[x].l,p,z);
else upd(tr[x].r,p-mid,z);
up(x);
}int merot(int x,int y){
if(!x||!y) return x|y;
if(tr[x].siz>tr[y].siz*4){
int t=merge(tr[x].l,merot(tr[x].r,y));
del(x);
return t;
}
if(tr[y].siz>tr[x].siz*4){
int t=merge(merot(x,tr[y].l),tr[y].r);
del(y);
return t;
}
return merge(x,y);
}void split(int x,int K,int&a,int&b){
if(!K){
a=0;
b=x;
return;
}
if(tr[x].siz==1){
a=x;
b=0;
return;
}
int mid=tr[tr[x].l].siz;
if(K<=mid){
split(tr[x].l,K,a,b);
del(x);
b=merot(b,tr[x].r);
}else{
split(tr[x].r,K-mid,a,b);
del(x);
a=merot(tr[x].l,a);
}
}int split(int x,int l,int r){
if(l==1&&r==tr[x].siz) return x;
int mid=tr[tr[x].l].siz;
if(r<=mid) return split(tr[x].l,l,r);
if(mid<l) return split(tr[x].r,l-mid,r-mid);
return merge(split(tr[x].l,l,mid),split(tr[x].r,1,r-mid));
}void swp(int l,int r){
int x,y,z;
split(rt,l-1,x,y);
split(y,r-l+1,y,z);
rt=merot(merot(x,z),y);
}unsigned que(int l,int r){
int tmpc=cnt,tmpt=*trash;
int x=split(rt,l,r);
cnt=tmpc;
*trash=tmpt;
auto ans=tr[x].lw+tr[x].rw;
return ans.mx^ans.tdr[1];
}
}
namespace xm{
void _(){
int Q;
scanf("%d%d",&N,&Q);
for(int i=1;i<=N;++i) scanf("%d%d",a+i,b+i);
wblt::rt=wblt::build(1,N);
while(Q--){
int x,y;
short op;
scanf("%hd%d%d",&op,&x,&y);
if(op==1) wblt::upd(wblt::rt,x,y);
else if(op==2) printf("%u\n",wblt::que(x,y));
else wblt::swp(x,y);
}
}
}
signed main(){
xm::_();
return 0;
}