火星商店问题：线段树分治与持久化Trie树的应用

### 问题描述
在一个火星上有编号为1到n的商店，每个商店有一个初始的永久商品价值v。题目包含两种操作：

- **操作1**：时间过了一天，第x个商店增加了一个价值为val的新商品。
- **操作2**：给定一个密码值x，询问从第L个商店到第R个商店，在当前天-d+1到当前天的所有商品中（包括永久商品），与密码值x的最大异或结果。

### 解决方案
最大异或值的问题可以通过持久化Trie树来解决。首先，我们需要将每个商店的永久商品价值提前更新到Trie树中。

#### 构建时间线段树
我们构建一棵时间线段树，并将所有的查询操作按时间顺序插入到这棵树中。具体步骤如下：

1. **初始化**：将所有商店的永久商品价值提前更新到Trie树中。
2. **时间线段树**：将所有查询操作按时间顺序插入到线段树中。
3. **CDQ分治**：对操作进行CDQ分治处理，确保操作按时间顺序正确执行。
4. **排序**：为了保证持久化Trie树的有序性，需要对操作按照商店编号进行排序。
5. **处理非连续编号**：由于商店编号可能不连续，因此需要用一个映射来维护持久化Trie树中的节点编号。

### 代码实现
```cpp
#include
using namespace std;

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repp(i, a, b) for (int i = (a); i >= (b); --i)
#define ll long long
#define see(x) (cerr <<(#x) <<"=" <<(x) <#define inf 0x3f3f3f3f
#define CLR(A, v) memset(A, v, sizeof A)

const int N = 1e5 + 10;
int t[N <<5][2], T[N], siz[N <<5], ncnt, b[N];

void upnode(int k, int x, int pre, int &pos) {
pos = ++ncnt;
t[pos][0] = t[pre][0];
t[pos][1] = t[pre][1];
siz[pos] = siz[pre] + 1;
if (k <0) return;
int c = (x >> k) & 1;
upnode(k - 1, x, t[pre][c], t[pos][c]);
}

int qmax(int k, int x, int pre, int pos) {
if (k <0) return 0;
int c = (x >> k) & 1;
if (siz[t[pos][c ^ 1]] - siz[t[pre][c ^ 1]] > 0)
return (1 < else
return qmax(k - 1, x, t[pre][c], t[pos][c]);
}

vector node[N <<2];
int n, m, ans[N];

void addnode(int x, int L, int R, int l, int r, int pos) {
if (L > R) return;
if (L <= l && r <= R) {
node[pos].push_back(x);
return;
}
int m = (l + r) >> 1;
if (L <= m) addnode(x, L, R, l, m, pos <<1);
if (R > m) addnode(x, L, R, m + 1, r, pos <<1 | 1);
}

struct marspeo {
int L, R, s, t, x;
} peo[N];

struct upp {
int t, x, val;
} up[N], s1[N], s2[N];

int cnt1, cnt0;

void calc(int L, int R, int pos) {
int nn = 0;
ncnt = 0;
rep(i, L, R) {
nn++;
b[nn] = up[i].x;
upnode(20, up[i].val, T[nn - 1], T[nn]);
}
for (auto v : node[pos]) {
int l = lower_bound(b + 1, b + 1 + nn, peo[v].L) - b;
int r = upper_bound(b + 1, b + 1 + nn, peo[v].R) - b - 1;
int temp = qmax(20, peo[v].x, T[l - 1], T[r]);
ans[v] = max(ans[v], temp);
}
}

void cdq(int L, int R, int l, int r, int pos) {
if (L > R) return;
calc(L, R, pos);
if (l == r) return;
int temp1 = 0, temp2 = 0, mid = (l + r) >> 1;
rep(i, L, R)
if (up[i].t <= mid)
s1[++temp1] = up[i];
else
s2[++temp2] = up[i];
rep(i, 1, temp1) up[i + L - 1] = s1[i];
rep(i, 1, temp2) up[i + L + temp1 - 1] = s2[i];
cdq(L, L + temp1 - 1, l, mid, pos <<1);
cdq(L + temp1, R, mid + 1, r, pos <<1 | 1);
}

int main() {
scanf("%d%d", &n, &m);
int x, l, r, op, d;
rep(i, 1, n) {
scanf("%d", &x);
upnode(20, x, T[i - 1], T[i]);
}
while (m--) {
scanf("%d", &op);
if (!op) {
scanf("%d%d", &l, &r);
cnt0++;
up[cnt0] = (upp){cnt0, l, r};
} else {
scanf("%d%d%d%d", &l, &r, &x, &d);
peo[++cnt1] = (marspeo){l, r, max(1, cnt0 - d + 1), cnt0, x};
ans[cnt1] = qmax(20, x, T[l - 1], T[r]);
}
}
rep(i, 1, cnt1) addnode(i, peo[i].s, peo[i].t, 1, cnt0, 1);
sort(up + 1, up + 1 + cnt0, [](upp a, upp b) { return a.x cdq(1, cnt0, 1, cnt0, 1);
rep(i, 1, cnt1) printf("%d\n", ans[i]);
return 0;
}
```