Description：

有若干个 $vector$ ，支持单点 $push\text_back$ ，以及询问最近 $d$ 次 $push\text_back$ 操作中在区间 $[l,r]$ 内的数与 $k$ 的异或最大值。

$1\leqslant n,m\leqslant 10^5$

Solution：

显然可以树套树，外层线段树，内层可持久化 $trie$ 。

但是这样并不优美，发现所有的询问都是区间的形式，那么我们就可以用线段树对时间分治，也就是说把一个询问拆成 $\log$ 个片段插入线段树中，这样我们就消去了事件的影响，然后对每个线段树的节点都拿出区间中所有的修改暴力构造一遍可持久化 $trie$ ，然后枚举询问查询对应区间即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int val[MAXN];

struct change

{

	int p,x;

}c[MAXN];

bool cmp_p(change a,change b){return a.p < b.p;}

int cnum = 0;

struct query

{

	int l,r,tl,tr,x;

}q[MAXN];

int qnum = 0;

namespace TRIE

{

	struct node

	{

		int c[2],s[2];

	}t[MAXN * 32];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root[MAXN];

	void insert(int rt,int fa,int v)

	{

		root[rt] = newnode();rt = root[rt];fa = root[fa];t[rt] = t[fa];

		for(int i = 18;i >= 0;--i)

		{

			int w = (v >> i) & 1,k = newnode();++t[rt].s[w];

			t[k] = t[t[rt].c[w]];t[rt].c[w] = k;rt = t[rt].c[w];

		}

		return;

	}

	int query(int l,int r,int v)

	{

		l = root[l];r = root[r];

		int res = 0;

		for(int i = 18;i >= 0;--i)

		{

			int w = (v >> i) & 1;

			if(t[r].s[w ^ 1] - t[l].s[w ^ 1] != 0)

			{

				w ^= 1;

				res = res + (1 << i);

			}

			r = t[r].c[w];l = t[l].c[w];

		}

		return res;

	}

}

int ans[MAXN];

struct node

{

	int lc,rc;

	vector<int> v;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		t[rt].v.push_back(k);

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

int p[MAXN],v[MAXN],tot = 0;

void dfs(int rt,int l,int r)

{

	if(l != r)

	{

		dfs(t[rt].lc,l,mid);

		dfs(t[rt].rc,mid + 1,r);

	}

	sort(c + l,c + r + 1,cmp_p);

	tot = 0;TRIE::ptr = 0;

	for(int i = l;i <= r;++i)

	{

		p[++tot] = c[i].p;

		v[tot] = c[i].x;

		TRIE::insert(tot,tot - 1,v[tot]);

	}

	p[++tot] = 0x3f3f3f3f;

	for(vector<int>::iterator it = t[rt].v.begin();it != t[rt].v.end();++it)

	{

		int l = lower_bound(p + 1,p + 1 + tot,q[*it].l) - p;

		int r = upper_bound(p + 1,p + 1 + tot,q[*it].r) - p - 1;

		if(l > r)continue;

		ans[*it] = max(ans[*it],TRIE::query(l - 1,r,q[*it].x));

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	for(int i = 1;i <= n;++i)TRIE::insert(i,i - 1,val[i]);

	int opt,l,r,x,d;

	int cnt = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&opt);

		if(opt == 0)

		{

			scanf("%d%d",&x,&d);

			c[++cnum] = (change){x,d};

		}

		else

		{

			scanf("%d%d%d%d",&l,&r,&x,&d);

			q[++qnum] = (query){l,r,max(1,cnum - d + 1),cnum,x};

			ans[qnum] = TRIE::query(l - 1,r,x);

		}

	}

	build(root,1,cnum);

	for(int i = 1;i <= qnum;++i)

	{

		add(root,q[i].tl,q[i].tr,i,1,cnum);

	}

	dfs(root,1,cnum);

	for(int i = 1;i <= qnum;++i)

	{

		printf("%d\n",ans[i]);

	}

	return 0;

}