有人搞错了复杂度白开心了一下午/kk
基于离线 ST 表+前缀线性基合并的 做法。
upd：@chenxinyang2006 的在线 做法。
考虑将操作离线下来，具体是对于序列的每一个位置开一个类似前缀线性基（即 CF1100F 中的 trick），优先记录操作时间 更小的向量。这里就要提到时间轴的一个很好的性质：我们只记录最小时间产生的 01 向量一定是更优的。
然后用 ST 表维护区间的前缀线性基的并。可以用 ST 表是因为线性基显然是有可重复贡献性的。至于前缀线性基合并，和普通线性基合并相差无几。
总时间复杂度是 。由于用线段树维护的许多剪枝方法不能用在这种线性基上，且 同阶，所以跑得远不如大部分 快。但还是有一定意义的吧（
code：
int n,m,k,l[N],r[N],t[N];
struct XXJ{
int a[31],b[31];
void insert(int x,int t){
drep(i,30,0){
if(!(x>>i&1)){
continue;
}
if(a[i]){
if(t<b[i]){
swap(a[i],x),swap(b[i],t);
}
x^=a[i];
}else{
a[i]=x,b[i]=t;
break;
}
}
}
int query(int x,int t){
drep(i,30,0){
if((x^a[i])>x&&b[i]<=t){
x^=a[i];
}
}
return x;
}
XXJ operator+(const XXJ &rhs)const{
XXJ r;
rep(i,0,30){
r.a[i]=a[i],r.b[i]=b[i];
}
rep(i,0,30){
if(rhs.a[i]){
r.insert(rhs.a[i],rhs.b[i]);
}
}
return r;
}
};
struct STable{
XXJ st[17][N];
void init(){
rep(i,1,__lg(m)){
rep(j,1,m-(1<<i)+1){
st[i][j]=st[i-1][j]+st[i-1][j+(1<<(i-1))];
}
}
}
XXJ query(int l,int r){
int k=__lg(r-l+1);
return st[k][l]+st[k][r-(1<<k)+1];
}
}ST;
void Yorushika(){
scanf("%d%d",&n,&m);
rep(i,1,n){
int op=read(),x=read(),y=read();
if(op==1){
ST.st[0][x].insert(y,i);
}else{
k++,l[k]=x,r[k]=y,t[k]=i;
}
}
ST.init();
rep(i,1,k){
printf("%d\n",ST.query(l[i],r[i]).query(0,t[i]));
}
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
upd：@chenxinyang2006 在他的 P5607 题解中提到了这题的 log^2 在线做法。大致讲一下。
具体就是运用猫树的思想建一棵线段树。每个节点如果是它父亲的左儿子，则维护一个后缀线性基，否则维护前缀线性基，根节点空。
每次修改，我们不再只修改叶子节点，而是将线段树上对应儿子到根的整条链修改。这是一个很巧妙的均摊复杂度的方法，因为注意到原来不算 pushup，每次只需要 的复杂度。新做法中，一共 次 的插入。并不影响复杂度。
查询时，类似猫树分治的做法，设询问区间为 ，找到第一个满足 的区间 ，因为维护了区间的前/后缀线性基，我们只需要一次简单的 的合并，再在线性基中查询最大值，就可以完成询问。
总时间复杂度 。非常优秀的做法，同时也是非常有启发意义的。
int n,m,k,l[N],r[N],t[N];
struct XXJ{
int a[31],b[31];
void insert(int x,int t,int lim){
drep(i,30,0){
if(!(x>>i&1)){
continue;
}
if(a[i]){
if(abs(t-lim)<abs(b[i]-lim)){
swap(a[i],x),swap(b[i],t);
}
x^=a[i];
}else{
a[i]=x,b[i]=t;
break;
}
}
}
int query(int x){
drep(i,30,0){
if((x^a[i])>x){
x^=a[i];
}
}
return x;
}
};
struct SGT{
XXJ tr[N<<2];
void update(int l,int r,int o,int x,int y){
if(o>1){
if(o&1){
tr[o].insert(y,x,0);
}else{
tr[o].insert(y,x,m);
}
}
if(l==r){
return;
}
int mid=(l+r)>>1;
if(x<=mid){
update(l,mid,o<<1,x,y);
}else{
update(mid+1,r,o<<1|1,x,y);
}
}
int query(int l,int r,int o,int x,int y){
int mid=(l+r)>>1;
if(x<=mid&&y>=mid){
XXJ r;
rep(i,0,30){
r.a[i]=r.b[i]=0;
if(tr[o<<1].b[i]>=x&&tr[o<<1].b[i]<=y){
r.insert(tr[o<<1].a[i],0,0);
}
if(tr[o<<1|1].b[i]>=x&&tr[o<<1|1].b[i]<=y){
r.insert(tr[o<<1|1].a[i],0,0);
}
}
return r.query(0);
}
if(x<=mid){
return query(l,mid,o<<1,x,y);
}
return query(mid+1,r,o<<1|1,x,y);
}
}T;
void Yorushika(){
scanf("%d%d",&n,&m);
rep(i,1,n){
int op=read(),x=read(),y=read();
if(op==1){
T.update(1,m,1,x,y);
}else{
printf("%d\n",T.query(1,m,1,x,y));
}
}
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
