线段树套trie+可持久化trie or 分治
分治的做法比较神，还没看，先讲讲数据结构。
对于特殊商品，肯定是可持久化trie来搞。
对于其他商品，对商店1~n建线段树，每个节点下建trie树，维护数字出现的最迟时间即可。
然而我被卡内存了，在别的OJ上过了，就当能过吧。。。
#include<cstdio> #define N 100005 #define ll long long using namespace std; namespace ziqian { const int INF = 1<<29; int mecnt, timer, pcnt; struct node { node *ch[2]; int v; }*trie[N],*null,me[N*300],*root[N*15],*pool[N*15]; int in() { register int r = 0; register char c = getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')r=r*10+c-'0',c=getchar(); return r; } void init() { null = &me[++mecnt]; null->ch[0] = null->ch[1] = null; null->v = 0; trie[0] = null; root[0] = null; } void inser_trie(node *x, node *y, int val) { for(int i = 31; i>=0; i--) { int v = ((val>>i)&1); y->ch[v^1] = x->ch[v^1]; y->ch[v] = &me[++mecnt]; y->ch[v]->v = x->ch[v]->v+1; y = y->ch[v]; x = x->ch[v]; } } void inser_trie(node *x, int val) { for(int i = 31; i>=0; i--) { int v = (val>>i)&1; if(x->ch[v] == null) { x->ch[v] = &me[++mecnt]; *x->ch[v] = *null; } x->ch[v]->v = timer; x = x->ch[v]; } } void inser_seg(int x, int l, int r, int pos, int val) { inser_trie(root[x], val); if(l==r)return; int mid = (l+r)>>1; if(pos <= mid)inser_seg(x<<1,l,mid,pos,val); else inser_seg(x<<1|1,mid+1,r,pos,val); } void build(int x, int l, int r) { root[x] = &me[++mecnt]; *root[x] = *null; if(l == r)return; int mid = (l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } void fetch(int x, int l, int r, int ql, int qr) { if(ql<=l&&r<=qr) { pool[++pcnt] = root[x]; return; } int mid = (l+r)>>1; if(ql <= mid)fetch(x<<1,l,mid,ql,qr); if(mid < qr)fetch(x<<1|1,mid+1,r,ql,qr); } void main() { int n=in(), m=in();; init(); for(int i = 1, a; i <= n; i++) { a=in(); trie[i] = &me[++mecnt]; inser_trie(trie[i-1],trie[i],a); } build(1,1,n); for(int i = 1, opt, a, b, c, d; i <= m; i++) { opt=in(); if(opt == 0) { a=in(),b=in(); ++timer; inser_seg(1, 1, n, a, b); } else { a=in(),b=in(),c=in(),d=in(); pcnt = 0; fetch(1,1,n,a,b); node *x = trie[a-1], *y = trie[b]; ll ans = 0; for(int k = 31; k>=0; k--) { bool found = 0; int v = ((c>>k)&1)^1; if(y->ch[v]->v - x->ch[v]->v > 0) found = 1; for(int j = 1; j <= pcnt && !found; j++) { if(pool[j] -> ch[v] -> v > timer - d) found = 1; } if(found)ans += 1ll<<k; x=x->ch[found?v:(v^1)]; y=y->ch[found?v:(v^1)]; for(int j = 1; j <= pcnt; j++) pool[j]=pool[j]->ch[found?v:(v^1)]; } printf("%lld\n",ans); } } } } int main() { ziqian::main(); }