https://www.luogu.com.cn/problem/P4585
线段树分治+可持久化 trie
如果只有特殊商品，那么直接一个可持久化 trie，根据异或的性质，在 trie 上贪心走路径就行了
所以这部分特殊商品单独维护，考虑其他普通商品如何维护
考虑以商店编号为下标，建立线段树。那么每个商店区间 \([l,r]\) 可以被分为 \(O(\log n)\) 个区间，我们分别对这些区间打上标记来维护商品信息
其实就是线段树再套一个可持久化 trie，每个节点维护两个 vector，分别表示每个 trie 的根，以及对应的添加时的时间。然后每次添加的时候，加一个根，再拿上一个根一起可持久化建树就行了
询问的时候，还是把询问的商店区间分成若干小区间，对于每个完全覆盖了个区间，二分一下此节点最靠前的一个符合条件的时间，然后拿那个时间对应的根，和当前添加的最后一个根，在可持久化 trie 上贪心取最大值
复杂度 \(O(n\log n\log T)\)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<cstring>
#define reg register
#define EN puts("")
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m;
#define MAX 18
#define N 100006
struct Trie{
struct Node{
Node *son[2];
int cnt;
}dizhi[N*128],*root[N],*null=&dizhi[0];
int tot;
inline void New(Node *&a){
a=&dizhi[++tot];
a->son[0]=a->son[1]=null;
}
void insert(Node *tree,Node *last,int x,int pos){
tree->cnt=last->cnt+1;
if(pos<0) return;
int nex=(x>>pos)&1;
New(tree->son[nex]);
tree->son[nex^1]=last->son[nex^1];
insert(tree->son[nex],last->son[nex],x,pos-1);
}
int ask(Node *left,Node *right,int x,int pos){
if(pos<0) return 0;
int nex=(x>>pos)&1;nex^=1;
if(right->son[nex]->cnt>left->son[nex]->cnt)
return (1<<pos)+ask(left->son[nex],right->son[nex],x,pos-1);
return ask(left->son[nex^1],right->son[nex^1],x,pos-1);
}
}trie;
struct Seg{
struct Node{
Node *ls,*rs;
std::vector<int>time;
std::vector<Trie::Node*>root;
Trie::Node *now_root;
}dizhi[N*2],*root=&dizhi[0];
int tot;
void build(Node *tree,int l,int r){
tree->time.push_back(0);
tree->root.push_back(trie.root[0]);
tree->now_root=trie.root[0];
if(l==r) return;
int mid=(l+r)>>1;
tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
build(tree->ls,l,mid);build(tree->rs,mid+1,r);
}
void change(Node *tree,int l,int r,int pos,int val,int day){
tree->time.push_back(day);
Trie::Node *tmp;trie.New(tmp);
trie.insert(tmp,tree->now_root,val,MAX);
tree->root.push_back(tmp);tree->now_root=tmp;
// printf("Seg::change : tmp->son[0]->son[0]->son[1]->cnt=%d\n",tmp->son[0]->son[0]->son[1]->cnt);
// printf("Seg::change : tmp->son[0]->son[0]->son[0]->son[1]->cnt=%d\n",tmp->son[0]->son[0]->son[0]->son[1]->cnt);
// EN;
if(l==r) return;
int mid=(l+r)>>1;
pos<=mid?change(tree->ls,l,mid,pos,val,day):change(tree->rs,mid+1,r,pos,val,day);
}
int ask(Node *tree,int l,int r,int ql,int qr,int x,int lim,int day){
if(ql<=l and r<=qr){
if(tree->time.size()<=1 or tree->time.back()<lim) return 0;
reg int L=1,R=tree->time.size()-1,mid,ans;
while(L<=R){
mid=(L+R)>>1;
if(tree->time[mid]>=lim) ans=mid,R=mid-1;
else L=mid+1;
}
// printf("Seg::ask : ans=%d\n",ans);
return trie.ask(tree->root[ans-1],tree->now_root,x,MAX);
}
int mid=(l+r)>>1,ret=0;
if(ql<=mid) ret=std::max(ret,ask(tree->ls,l,mid,ql,qr,x,lim,day));
if(qr>mid) ret=std::max(ret,ask(tree->rs,mid+1,r,ql,qr,x,lim,day));
return ret;
}
}seg;
int main(){
n=read();m=read();
trie.null->son[0]=trie.null->son[1]=trie.null;
trie.New(trie.root[0]);
for(reg int i=1;i<=n;i++){
trie.New(trie.root[i]);
trie.insert(trie.root[i],trie.root[i-1],read(),MAX);
}
seg.build(seg.root,1,n);
reg int op,x,y,day=0;int l,r;
while(m--){
op=read();
if(!op){
day++;x=read();y=read();
seg.change(seg.root,1,n,x,y,day);
}
else{
l=read();r=read();x=read();y=read();
printf("%d\n",std::max(trie.ask(trie.root[l-1],trie.root[r],x,MAX),
seg.ask(seg.root,1,n,l,r,x,day-y+1,day)));
}
}
return 0;
}