题目：火星上的一条商业街里按照商店的编号1，2 ，…，n ，依次排列着n个商店。商店里出售的琳琅满目的商品中，每种商品都用一个非负整数val来标价。每个商店每天都有可能进一些新商品，其标价可能与已有商品相同。
火星人在这条商业街购物时，通常会逛这条商业街某一段路上的所有商店，譬如说商店编号在区间[L,R]中的商店，从中挑选1件自己最喜欢的商品。每个火星人对商品的喜好标准各不相同。通常每个火星人都有一个自己的喜好密码x。对每种标价为val的商品，喜好密码为x的火星人对这种商品的喜好程度与val异或x的值成正比。也就是说，val xor x的值越大，他就越喜欢该商品。每个火星人的购物卡在所有商店中只能购买最近d天内（含当天）进货的商品。另外，每个商店都有一种特殊商品不受进货日期限制，每位火星人在任何时刻都可以选择该特殊商品。每个商店中每种商品都能保证供应，不存在商品缺货的问题。
对于给定的按时间顺序排列的事件，计算每个购物的火星人的在本次购物活动中最喜欢的商品，即输出val xor x的最大值。这里所说的按时间顺序排列的事件指以下2种事件
事件0，用三个整数0,s,v，表示编号为s的商店在当日新进一种标价为v 的商品。
事件1，用5个整数1,L,R,x,d，表示一位火星人当日在编号为L到R的商店购买d天内的商品，该火星人的喜好密码为x。
对于所有数据点，1<= n,m,x,val <= 100000，d<=经过天数（进货次数），两种操作的数量大致相同。 3s，256mb
题解：
很容易想到用可持久化线段树套可持久化TRIE树，然后就是码农题啦。
由于两种操作数量大致相同，所以不会爆内存。
#include<iostream> #include<cstdio> #include<cstring> #define MN 20000000 #define MM 1900000 #define ML 20 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int cnt=0,tcnt=0,n,m,c[ML],top=0,s[100005],rt[100005],nowdep=0,trt[100005]; struct Trie { int l,r,x; }T[MN+5]; struct Segment_Tree { int l,r,x; }t[MM+5]; void ins(int x,int&nn,int val) { nn=++tcnt;int nx=tcnt;memset(c,0,sizeof(c)); for(top=0;val;val>>=1) c[++top]=val&1; for(int i=17;i;--i) { if(c[i]) { T[nx].l=T[x].l;T[nx].r=++tcnt; T[nx].x=T[x].x+1;x=T[x].r;nx=T[nx].r; } else { T[nx].r=T[x].r;T[nx].l=++tcnt; T[nx].x=T[x].x+1;x=T[x].l;nx=T[nx].l; } //cout<<x<<" "<<nx<<" "<<c[i]<<endl; } T[nx].x=T[x].x+1; } int query(int x,int nx,int val) { memset(c,0,sizeof(c));int ch=val; for(top=0;val;val>>=1)c[++top]=(val&1); for(int i=17,j=1<<16;i;i--,j>>=1) { if(!c[i]) { if(T[T[nx].r].x-T[T[x].r].x) {ch^=j;x=T[x].r;nx=T[nx].r;} else {x=T[x].l;nx=T[nx].l;} } else { if(T[T[nx].l].x-T[T[x].l].x) {x=T[x].l;nx=T[nx].l;} else {ch^=j;x=T[x].r;nx=T[nx].r;} } // cout<<"query"<<x<<" "<<nx<<" "<<c[i]<<" "<<ch<<endl; } return ch; } void ins(int x,int nx,int k,int val,int l,int r) { // cout<<"insseg"<<x<<" "<<nx<<" "<<k<<" "<<val<<" "<<l<<" "<<r<<" "<<endl; ins(t[x].x,t[nx].x,val); if(l==r) return; int mid=l+r>>1; if(k<=mid){t[nx].r=t[x].r;ins(t[x].l,t[nx].l=++cnt,k,val,l,mid);} else{t[nx].l=t[x].l;ins(t[x].r,t[nx].r=++cnt,k,val,mid+1,r);} } int query(int x,int k,int val,int l,int r,int lt=1,int rt=n) { //cout<<"query"<<x<<" "<<k<<" "<<val<<" "<<l<<" "<<r<<" "<<lt<<" "<<rt<<endl; if(lt==l&&rt==r) return query(t[x].x,t[k].x,val); int mid=(lt+rt)>>1; if(r<=mid) return query(t[x].l,t[k].l,val,l,r,lt,mid); else if(l>mid) return query(t[x].r,t[k].r,val,l,r,mid+1,rt); else return max(query(t[x].l,t[k].l,val,l,mid,lt,mid),query(t[x].r,t[k].r,val,mid+1,r,mid+1,rt)); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { s[i]=read(); ins(trt[i-1],trt[i],s[i]); } for(int i=1;i<=m;i++) { int op=read(),x=read(),y=read(); if(!op) ins(rt[nowdep],rt[nowdep+1]=++cnt,x,y,1,n),nowdep++; else { int val=read(),d=read(); printf("%d ",max(query(trt[x-1],trt[y],val),query(rt[nowdep-d],rt[nowdep],val,x,y))); } } return 0; }