[FJOI2015]火星商店问题

lindongli2004 · 2020-05-09 00:07:35 · 题解

标签：线段树 + 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\} )。

下面是参考代码：

#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;
}

小结：遇到题目要理清思路，找到突破口，顺藤摸瓜找到解决方案。