传送门
题意：序列上有nnn个商店，有两种事件会发生：
- sss商店上进购标价为vvv的一个物品
- 求编号为[l,r][l,r][l,r]之间的位置买ddd天内新进购的所有物品与一个数xxx异或值的最大值。
每个位置都有一种物品每天会新进购（最开始会给出）。
思路：
第一眼显然的线段树套可持久化01trie 恭喜MLE走人
然后发现每个人的询问可以放到按时间建出的线段树上，这个不就可以线段树分治离线处理了吗。
于是把每天进购的物品排个序下放，每一层线段树用一个可持久化01trie来统计答案即可（注意这个并不是线段树和可持久化01trie套在一起）
代码：
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e5+5,P=17;
int n,m,stk[N],rt[N],siz[N*20],son[N*20][2],top=0,tot=0,sig=0,ans[N],cnt=0;
vector<int>e[N],qry[N<<2];
struct Query{int l,r,dl,dr,v;}pd[N];
struct UPD{int s,v,d;}upd[N],t1[N],t2[N];
inline void insert(int&p,int last,int val){
int o=p=++tot;
for(ri i=17;~i;--i){
int tmp=(val>>i)&1;
son[o][tmp]=++tot,son[o][tmp^1]=son[last][tmp^1];
o=son[o][tmp],last=son[last][tmp],siz[o]=siz[last]+1;
}
}
inline int query(int ql,int qr,int val){
int ret=0;
for(ri i=17;~i;--i){
int tmp=(val>>i)&1;
if(siz[son[qr][tmp^1]]^siz[son[ql][tmp^1]])ret|=(1<<i),ql=son[ql][tmp^1],qr=son[qr][tmp^1];
else ql=son[ql][tmp],qr=son[qr][tmp];
}
return ret;
}
inline void update(int p,int l,int r,int ql,int qr,int v){
if(ql>r||qr<l||ql>qr)return;
if(ql<=l&&r<=qr){qry[p].push_back(v);return;}
if(qr<=mid)update(lc,l,mid,ql,qr,v);
else if(ql>mid)update(rc,mid+1,r,ql,qr,v);
else update(lc,l,mid,ql,mid,v),update(rc,mid+1,r,ql,qr,v);
}
inline void calc(int p,int l,int r){
tot=top=0;
for(ri i=l;i<=r;++i){
int s=upd[i].s,v=upd[i].v;
stk[++top]=s,insert(rt[top],rt[top-1],v);
}
for(ri i=0;i<qry[p].size();++i){
int x=qry[p][i];
int ql=upper_bound(stk+1,stk+top+1,pd[x].l-1)-stk-1;
int qr=upper_bound(stk+1,stk+top+1,pd[x].r)-stk-1;
ans[x]=max(ans[x],query(rt[ql],rt[qr],pd[x].v));
}
}
inline void solve(int p,int l,int r,int ql,int qr){
if(ql>qr)return;
calc(p,ql,qr);
if(l==r)return;
int hd1=0,hd2=0;
for(ri i=ql;i<=qr;++i)if(upd[i].d<=mid)t1[++hd1]=upd[i];else t2[++hd2]=upd[i];
for(ri i=1;i<=hd1;++i)upd[ql+i-1]=t1[i];
for(ri i=1;i<=hd2;++i)upd[ql+hd1+i-1]=t2[i];
solve(lc,l,mid,ql,ql+hd1-1),solve(rc,mid+1,r,ql+hd1,qr);
}
inline bool cmp(const UPD&a,const UPD&b){return a.s<b.s;}
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i)insert(rt[i],rt[i-1],read());
for(ri i=1,op,ql,qr,x,s,d,v;i<=m;++i){
op=read();
if(op){
ql=read(),qr=read(),x=read(),d=read();
ans[++sig]=query(rt[ql-1],rt[qr],x);
pd[sig]=(Query){ql,qr,max(1,cnt-d+1),cnt,x};
}
else s=read(),v=read(),upd[++cnt]=(UPD){s,v,cnt};
}
for(ri i=1;i<=sig;++i)update(1,1,cnt,pd[i].dl,pd[i].dr,i);
sort(upd+1,upd+cnt+1,cmp);
solve(1,1,cnt,1,cnt);
for(ri i=1;i<=sig;++i)cout<<ans[i]<<'\n';
return 0;
}