[FJOI2015]火星商店问题

标签：线段树 + $01-trie$ 首先，看到与 $x$ 的异或值最大，我们应该立即想到 $01-tire$ 的贪心算法，即： - 我们把已有的数字从第 $30$ 位到第 $1$ 位按照二进制，依次插入到 $tire$ 树中。 - 查询数字 $x$ 时，从第 $30$ 位到第 $1$ 位贪心：设当前二进制位为 $y$ ，那么数字 $x$ 的这个二进制位为 th=x>>y&1，那么如果当前 $trie$ 树上有 th^1 这个分支，说明 $x$ 在 $y$ 这个二进制位上可以取到值，所以 $ans+=(1<<y)$，递归到 th^1 这个分支，否则就递归到 th 这个分支，继续往下找。 现在我们就有了一个显然的暴力：每个商店维护一个 $01-trie$，查询时从 $l$ 枚举到 $r$, 把结果取 $max$，修改时，我们可以在每个 $01-trie$ 的结点上记录：该结点最晚的修改时间 $dmx$，这样查询时，如果要进入的结点的 $dmx$ 小于最早的合法时限，那就 $return$ 即可。 总结一下上述操作：单点修改，区间查询，可以用线段树维护，线段树的每个结点维护这个区间内的所有数的 $01-trie$ ，实现用到了标记永久化的技巧。 时空复杂度：$O(n \;log n \;log\;max\{val\} )$。 下面是参考代码： ```cpp #include<iostream> #include<cstdio> using namespace std; const int MX=4e7,INF=1e9; int n,tot; struct Tire_01{ int c[MX][2],mx[MX]; // mx 记录的是该结点的最晚修改时间 inline void add(int k,int x,int d){ for(int i=20;i>=0;i--){ int th=x>>i&1; k=c[k][th]?c[k][th]:(c[k][th]=++tot); mx[k]=max(mx[k],d); } } inline int ask(int k,int x,int d){ int r=0; for(int i=20;i>=0;i--){ int th=x>>i&1; if(c[k][th^1] && mx[c[k][th^1]]>=d)r|=(1<<i),k=c[k][th^1]; else if(mx[c[k][th]]>=d)k=c[k][th]; else return r; } return r; } }tr; int query(int k,int l,int r,int ql,int qr,int x,int d){ if(ql<=l && qr>=r)return tr.ask(k,x,d); int mid=(l+r)>>1,ans=0; if(ql<=mid)ans=max(ans,query(k<<1,l,mid,ql,qr,x,d)); if(qr>mid) ans=max(ans,query(k<<1|1,mid+1,r,ql,qr,x,d)); return ans; } void change(int k,int l,int r,int x,int y,int d){ tr.add(k,y,d); if(l==r)return; int mid=(l+r)>>1; if(x<=mid)change(k<<1,l,mid,x,y,d); else change(k<<1|1,mid+1,r,x,y,d); } inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){x=x*10+ch-'0';ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(); int aq=read(); tot=n<<2; for(int i=1;i<=n;i++) change(1,1,n,i,read(),INF); int cnt=0; while(aq--){ int op=read(),l=read(),r=read(),x,y; if(!op)++cnt,change(1,1,n,l,r,cnt); else x=read(),y=read(),printf("%d\n",query(1,1,n,l,r,x,max(0,cnt-y+1))); } return 0; } ``` 小结：遇到题目要理清思路，找到突破口，顺藤摸瓜找到解决方案。