正解:线段树+$trie$树
解题报告:
$umm$题目有点儿长我先写下题目大意趴$QwQ$,就说有$n$个初始均为空的集合和$m$次操作,每次操作为向某个集合内加入一个数$x$,或者查询最近的$d$次向编号在$[l,r]$内的集合加入的元素中,与$x$异或和的最大值
首先看到异或就想到$trie$树昂$QwQ$
然后就还有一个时间限制和一个位置限制.
先考虑时间限制趴?就魔改下$trie$树,本来每个节点记录的是是否存在这个节点?现在变成这个节点最近一次被更新的时间,这样就能满足时间限制了嘛$QwQ$
然后对于位置限制,就考虑加一个线段树.
因为这种最大值问题是满足结合律的?所以可以分别在每个节点上做然后合并起来就成.
$over$
昂然后不开$O2$会$T$,但是反正开了$O2$能过嘛我就懒得管了$kk$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fi first
#define sc second
#define gc getchar()
#define mp make_pair
#define P pair<int,int>
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) const int N=1e7+;
int n,m,dat,rt[N],rt_cnt,nod_cnt,T;
struct node{int to[],tot;}nod[N];
vector<P>S[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void insert(ri dat,ri pre)
{
//printf("dat=%d pre=%d\n",dat,pre);
rt[++rt_cnt]=++nod_cnt;nod[rt[rt_cnt]]=nod[rt[pre]];ri nw=rt[rt_cnt];++nod[nw].tot;
my(i,,)
{ri t=(dat>>i)&;nod[++nod_cnt]=nod[nod[nw].to[t]];nod[nw].to[t]=nod_cnt;nw=nod[nw].to[t];++nod[nw].tot;}
}
il int ask(ri l,ri r,ri dat)
{
//printf("l=%d r=%d dat=%d\n",l,r,dat);
ri as=;
my(i,,)
{
ri t=!((dat>>i)&);
if(nod[nod[r].to[t]].tot-nod[nod[l].to[t]].tot)as+=<<i,r=nod[r].to[t],l=nod[l].to[t];
else r=nod[r].to[!t],l=nod[l].to[!t];
}
return as;
}
void modify(ri nw,ri l,ri r,ri to,ri dat,ri tim)
{
insert(dat,S[nw].back().sc);S[nw].push_back(mp(tim,rt_cnt));if(l==r)return;
ri mid=(l+r)>>;to<=mid?modify(nw<<,l,mid,to,dat,tim):modify(nw<<|,mid+,r,to,dat,tim);
}
int query(ri nw,ri l,ri r,ri to_l,ri to_r,ri K,ri dat)
{
if(to_l<=l && r<=to_r)
{
ri pos=upper_bound(S[nw].begin(),S[nw].end(),mp(dat,))-S[nw].begin()-;
//printf("%d-%d %d-%d dat=%d\n",S[nw][pos].sc,S[nw][pos].fi,S[nw].back().sc,S[nw].back().fi,dat);
//ri tmp=S[nw].size();rp(i,0,tmp-1)printf(" %d",S[nw][i].fi);printf("\n");
//printf("pos=%d\n",pos);
return ask(rt[S[nw][pos].sc],rt[S[nw].back().sc],K);
}
ri mid=(l+r)>>,ret=;
if(to_l<=mid)ret=max(ret,query(nw<<,l,mid,to_l,to_r,K,dat));
if(mid<to_r)ret=max(ret,query(nw<<|,mid+,r,to_l,to_r,K,dat));
return ret;
} int main()
{
//freopen("4585.in","r",stdin);freopen("4585.out","w",stdout);
n=read();m=read();rp(i,,n)insert(read(),i-);rp(i,,n<<)S[i].push_back(mp(,));
while(m--)
{
ri opt=read();
if(opt)
{
ri l=read(),r=read(),x=read(),d=read(),as=ask(rt[l-],rt[r],x);
if(d)as=max(as,query(,,n,l,r,x,T-d+));;printf("%d\n",as);
}
else{ri x=read(),d=read();++T;modify(,,n,x,d,T);}
}
return ;
}