前言：为什么好多题解用可持久化 Trie 或者离线下来处理。其实可以不用这么干啊。再喷一下出题人：每天以进货结束，差点以为天以任意事件结束。

如果只有一个商店怎么做？

如果没有购买时间限制，这就是一个 01trie 模板。

如果有，我们在遍历 trie 时顺便记录每个点所有子节点时间戳最大的是多少。

如果有商店，就对商店线段树分治即可。具体地，每个线段表示所有子节点商品价格的 trie。

所以为什么题解喜欢对时间分治（虽然线段树分治模板是时间分治）。这题时间和商品都是一个区间，都可以分治。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, X = 20;

int rt[N*4], idx, mt[N*400], tr[N*400][2];

void ins(int p, int t, int x)
{
	int i;
	for(i=X;~i;i--)
	{
		mt[p] = max(mt[p],t);
		if(!tr[p][(x>>i)&1]) tr[p][(x>>i)&1] = ++idx;
		p = tr[p][(x>>i)&1];
	}
	mt[p] = max(mt[p],t);
}
int task(int p, int t, int x)
{
	int i, ans = 0;
	for(i=X;~i;i--)
	{
		int y = ((x >> i) & 1) ^ 1;
		if(tr[p][y]&&mt[tr[p][y]]>=t) ans += 1 << i, p = tr[p][y];
		else p = tr[p][1-y];
	}
	return ans;
}
void build(int p, int l, int r)
{
	rt[p] = ++idx;
	if(l==r) return;
	build(p*2,l,(l+r)>>1);build(p*2+1,((l+r)>>1)+1,r);
}
void add(int p, int L, int R, int x, int y, int z)
{
	ins(rt[p],y,z);
	if(L==R) return;
	int mid = L + R >> 1;
	if(x<=mid) add(p*2,L,mid,x,y,z);else add(p*2+1,mid+1,R,x,y,z);
}
int ask(int p, int l, int r, int t, int x, int L, int R)
{
	if(l<=L&&R<=r) return task(rt[p],t,x);
	int mid = L + R >> 1, ans = 0;
	if(l<=mid) ans = max(ans,ask(p*2,l,r,t,x,L,mid));
	if(mid<r) ans = max(ans,ask(p*2+1,l,r,t,x,mid+1,R));
	return ans;
}
int main()
{
	int n, m, day = 1, a, i;
	cin>>n>>m;
	build(1,1,n);
	for(i=1;i<=n;i++) cin>>a, add(1,1,n,i,114514,a);
	while(m--)
	{
		int op, l, r, x, d;
		cin>>op>>l>>r;
		if(op==0) add(1,1,n,l,++day,r);
		else cin>>x>>d, cout<<ask(1,l,r,day-d+1,x,1,n)<<'\n';
	}
	return 0;
}

C140 线段树分治+01Trie P4585 [FJOI2015] 火星商店问题

// 线段树分治 O(nlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define N 100005
#define mid ((l+r)>>1)
#define rs ((u<<1)|1)
#define ls (u<<1)

struct shop{
  int s,v,t; //商店编号,价格,时间
}p[N],p1[N],p2[N];
struct Q{
  int l,r,L,R,x; //商店区间,时间区间,密码
}q[N];
int n,m,idx,cnt,top;
int rt[N],ch[N*20][2],siz[N*20]; //01Trie
int s[N],ans[N];
vector<int> tr[N]; //节点

bool cmp(shop &x,shop &y){
  return x.s<y.s;
}
void ins(int v){ //插入Trie
  rt[++idx]=++cnt;
  int x=rt[idx-1],y=rt[idx];
  for(int i=17;i>=0;i--){
    int j=v>>i&1;
    ch[y][!j]=ch[x][!j];   //异位继承
    ch[y][j]=++cnt;        //新位开点
    x=ch[x][j];y=ch[y][j]; //走位
    siz[y]=siz[x]+1;       //新位多1
  }
}
int query(int x,int y,int v){ //查询异或最值
  int ans=0;
  for(int i=17;i>=0;i--){
    int j=v>>i&1;
    if(siz[ch[y][!j]]>siz[ch[x][!j]])
      ans+=(1<<i),j=!j;
    x=ch[x][j]; y=ch[y][j];
  }
  return ans;
}
void solve(int u,int l,int r){
  // 重建当前区间的01Trie，查询区间异或最值
  top=idx=cnt=0;
  for(int i=l;i<=r;i++){
    s[++top]=p[i].s; //用栈记录商店编号
    ins(p[i].v);     //标价插入Trie
  }
  for(auto i:tr[u]){
    // 该区间商店编号有重复值，应该找靠右的编号
    int a=upper_bound(s+1,s+1+top,q[i].l-1)-s-1;
    int b=upper_bound(s+1,s+1+top,q[i].r)-s-1;
    ans[i]=max(ans[i],query(rt[a],rt[b],q[i].x));
  }
  
  if(l==r)return;
  // 时间小的修改扔到左边，时间大的修改扔到右边。
  // 分拣后，子区间依然是按商店编号有序的。
  int n1=0,n2=0;
  for(int i=l;i<=r;i++)
    p[i].t<=mid ? p1[++n1]=p[i] : p2[++n2]=p[i];
  for(int i=1;i<=n1;i++) p[i+l-1]=p1[i];
  for(int i=1;i<=n2;i++) p[i+mid]=p2[i];
  solve(ls,l,mid);
  solve(rs,mid+1,r);
}
void insert(int u,int l,int r,int L,int R,int x){
  if(L>r||R<l)return ;
  if(L<=l&&r<=R){tr[u].push_back(x);return;}
  insert(ls,l,mid,L,R,x);
  insert(rs,mid+1,r,L,R,x);
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1,x;i<=n;i++)
    scanf("%d",&x), ins(x);
  int cnt=0,tot=0; //cnt天数,tot询问数
  for(int i=1,opt,s,v,l,r,x,d;i<=m;i++){
    scanf("%d",&opt);
    if(!opt){
      scanf("%d%d",&s,&v);
      p[++cnt]={s,v,cnt}; //修改
    }
    else{
      scanf("%d%d%d%d",&l,&r,&x,&d);
      q[++tot]={l,r,cnt-d+1,cnt,x}; //询问
      ans[tot]=query(rt[l-1],rt[r],x);
    }
  }
  for(int i=1;i<=tot;i++) //询问时间插入线段树
    insert(1,1,cnt,q[i].L,q[i].R,i);
  sort(p+1,p+1+cnt,cmp);  //按商店编号排序  
  solve(1,1,cnt);
  for(int i=1;i<=tot;i++)printf("%d\n",ans[i]);
}