题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4137
关于可持久化01trie树：https://www.cnblogs.com/LadyLex/p/7281110.html
看了看它的两道例题，就没写。
特殊商品可以直接用可持久化trie做。
其他部分用线段树分治。修改是单点的，询问是区间，原来想的是把询问区间定位后有 mlogn 个，在线段树的每个叶子上贡献一番；结果TLE了，因为若是在叶子处贡献，一个询问就要做 r-l+1 次。
要在线段树的每个节点上建可持久化trie，可持久化的顺序就是商店的编号；这样就能对于 mlogn 个区间，先二分找到在可持久化trie的哪一段有贡献，然后贡献给那个询问了。
做出每个节点的可持久化trie，不用trie树合并什么的，只要把当前节点表示的区间的修改排序然后一个一个加进去就行了。一共只会加 nlogn 次。
为了省时间，不用再每个节点的时候给那些修改按商店排序，而可以先按商店排好序，然后像 CDQ 分治那样稳定地把属于左边的给左边、属于右边的给右边。
在线段树的每个节点的时候，虽然可以认为同一个商店的在一棵trie树上，不同商店之间的trie树合并起来，但写的时候不能像 “if( cr==pr ) { ... sm[cr]++; ... }” 这样 “当在同一个商店的时候按普通构建trie树那样赋值” ，因为已经可持久化了， sm[cr]++ 的这个 cr 可能可以通过之前的 rt 走过来，就会出错。
注意空间不是 18*n 而是 19*n ，因为边有 18 层，节点就有 19 层。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ls Ls[cr]
#define rs Rs[cr]
#define pb push_back
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
const int N=1e5+,K=,M=19e5+;//19 not 18 for -1
int n,m,ct,sp[N],st[N],en[N],ans[N];
int tot,Ls[N<<],Rs[N<<],len;
struct Node{
int x,id,t;
bool operator< (const Node &b)const
{return id<b.id;}
}vl[N],tp[N];
struct Ques{int l,r,x;}q[N];
vector<int> vt[N<<];
namespace Tri{
int tot,c[M][],sm[M],rt[N],bin[K+];
void Init()
{bin[]=;for(int i=;i<=K;i++)bin[i]=bin[i-]<<;}
void ins(int x,int cr,int pr)
{
rt[cr]=++tot; cr=rt[cr]; pr=rt[pr];
for(int t=K;t>=;t--)
{
bool d=(x&bin[t]);
c[cr][d]=++tot; c[cr][!d]=c[pr][!d];
cr=c[cr][d]; pr=c[pr][d]; sm[cr]=sm[pr]+;
}
}
int qry(int l,int r,int x)
{
l=rt[l-]; r=rt[r]; int ret=;
for(int t=K;t>=;t--)
{
bool d=(x&bin[t]);
if(sm[c[r][!d]]-sm[c[l][!d]])
l=c[l][!d], r=c[r][!d], ret|=bin[t];
else l=c[l][d], r=c[r][d];
}
return ret;
}
}
void build(int l,int r,int cr)
{
if(l==r)return; int mid=l+r>>;
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+,r,rs);
}
void ins(int l,int r,int cr,int L,int R,int k)
{
if(l>=L&&r<=R){vt[cr].pb(k);return;}
int mid=l+r>>;
if(L<=mid)ins(l,mid,ls,L,R,k);
if(mid<R)ins(mid+,r,rs,L,R,k);
}
int fnd(int x,bool fx)
{
int l=,r=len,ret=;
while(l<=r)
{
int mid=l+r>>;
if(!fx)
{if(tp[mid].id>=x)ret=mid,r=mid-;else l=mid+;}
else
{if(tp[mid].id<=x)ret=mid,l=mid+;else r=mid-;}
}
return ret;
}
void solve(int l,int r,int cr,int L,int R)
{
for(int i=L,j=;i<=R;i++,j++)tp[j]=vl[i];//out of if()
if(vt[cr].size())
{
len=R-L+; Tri::tot=;//
for(int i=;i<=len;i++)Tri::ins(tp[i].x,i,i-);
for(int i=,j=vt[cr].size();i<j;i++)
{
int bh=vt[cr][i]; Ques k=q[bh];
int tl=fnd(k.l,), tr=fnd(k.r,);//tl,tr not l,r!!!
if(!tl||!tr||tl>tr)continue;
ans[bh]=Mx(ans[bh],Tri::qry(tl,tr,k.x));
}
}
if(l==r)return; int mid=l+r>>,p0=L-;
int tl=R-L+;
for(int i=;i<=tl;i++)if(tp[i].t<=mid)vl[++p0]=tp[i];
int p1=p0;
for(int i=;i<=tl;i++)if(tp[i].t>mid)vl[++p0]=tp[i];
solve(l,mid,ls,L,p1); solve(mid+,r,rs,p1+,R);
}
int main()
{
n=rdn();int T=rdn();
for(int i=;i<=n;i++)sp[i]=rdn();
for(int i=,op,d;i<=T;i++)
{
op=rdn();
if(!op)
{
m++; vl[m].id=rdn();vl[m].x=rdn();vl[m].t=m;
}
else
{
ct++; q[ct].l=rdn();q[ct].r=rdn();q[ct].x=rdn();
d=rdn(); st[ct]=Mx(,m-d+);en[ct]=m;
}
}
Tri::Init();
if(m)//
{
tot=;build(,m,);
for(int i=;i<=ct;i++)
if(st[i]<=en[i])ins(,m,,st[i],en[i],i);//if
sort(vl+,vl+m+); solve(,m,,,m);
}
Tri::tot=;
for(int i=;i<=n;i++)Tri::ins(sp[i],i,i-);
for(int i=;i<=ct;i++)
{
ans[i]=Mx(ans[i],Tri::qry(q[i].l,q[i].r,q[i].x));
printf("%d\n",ans[i]);
}
return ;
}