【题解】「FJOI2015」火星商店问题 线段树分治+可持久化 Trie 树 luogu4585 —Qiuly

感觉 $luogu$ 的题面 好 丑 啊 。

很显然的一个想法是用线段树套可持久化 $\rm{Trie}$ ，或者分块 $+$可持久化 $\rm{Trie}$ ，前者会爆空间 (当然可能可以卡过去？) ，后者好像也会爆炸。

正解是线段树分治。

按照时间构造一棵线段树，然后对于每个询问操作，将其拆入到线段树中。线段树每个点用 $vector$ 存下询问区间包含该点区间的那些询问的编号。

然后开始分治，设 $solve(x,l,r,L,R)$ 表示到了线段树 $x$ 点，区间为 $l,r$ ，时间在 $l,r$ 区间的是 $L,R$ 区间的所有插入操作，然后这下子处理一下 $x$ 的 $vector$ 中的那些点的贡献即可，用可持久化 $\rm{Trie}$ 。

Code：

#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define freopen(x) {freopen(x".in","r",stdin);freopen(x".out","w",stdout);}

const int N=1e5+2;
int n,m,cnt0,cnt1,ans[N];
struct Add {int s,v,t;}q0[N],tmp1[N],tmp2[N];
struct Query {int l,r,tl,tr,x;}q1[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Trie {
    struct Trie_Node {int ch[2],val;} t[N<<5];
    int tot,rt[N];
    void insert(int&now,int last,int val,int k) {
        t[now=++tot]=t[last],t[now].val++;
        if(k==-1) return;
        bool c=val&(1<<k);
        insert(t[now].ch[c],t[last].ch[c],val,k-1);
    }
    int query(int l,int r,int val,int k) {
        if(k==-1) return 0;
        bool c=val&(1<<k);
        if(t[t[r].ch[c^1]].val-t[t[l].ch[c^1]].val) 
            return query(t[l].ch[c^1],t[r].ch[c^1],val,k-1)+(1<<k);
        else return query(t[l].ch[c],t[r].ch[c],val,k-1);
    }
}T;

#define mid ((l+r)>>1)
vector <int> tree[N];
void modify(int x,int l,int r,int L,int R,int id) {
    if(L>R) return;
    if(L<=l&&r<=R) {tree[x].push_back(id);return;}
    if(L<=mid) modify(x<<1,l,mid,L,R,id);
    if(R>mid) modify(x<<1|1,mid+1,r,L,R,id);
}

int S[N],cnt;
inline int search(int x) {
    int l=1,r=cnt,res=0;
    while(l<=r) S[mid]<=x?res=mid,l=mid+1:r=mid-1;
    return res;
}
inline void calc(int x,int L,int R) {
    cnt=T.tot=0;
    for(int i=L;i<=R;++i) {
        S[++cnt]=q0[i].s;
        T.insert(T.rt[cnt],T.rt[cnt-1],q0[i].v,18);
    }
    int limit=tree[x].size()-1;
    for(int i=0;i<=limit;++i) {
        int id=tree[x][i],l=search(q1[id].l-1),r=search(q1[id].r);
        ans[id]=max(ans[id],T.query(T.rt[l],T.rt[r],q1[id].x,18));
    }
}
void solve(int x,int l,int r,int L,int R) {
    if(L>R) return;
    int cnt1=0,cnt2=0;calc(x,L,R);
    if(l==r) return;
    for(int i=L;i<=R;++i) q0[i].t<=mid?tmp1[++cnt1]=q0[i]:tmp2[++cnt2]=q0[i];
    for(int i=1;i<=cnt1;++i) q0[L+i-1]=tmp1[i];
    for(int i=1;i<=cnt2;++i) q0[L+cnt1+i-1]=tmp2[i];
    solve(x<<1,l,mid,L,L+cnt1-1),
    solve(x<<1|1,mid+1,r,L+cnt1,R);
}

bool cmp(Add a,Add b) {return a.s<b.s;}
int main() {
    freopen("4585");
    IN(n),IN(m),T.tot=0;
    for(int i=1,v;i<=n;++i) IN(v),T.insert(T.rt[i],T.rt[i-1],v,18);
    for(int i=1;i<=m;++i) {
        int op,s,v,x,d,L,R;IN(op);
        if(op) {
            IN(L),IN(R),IN(x),IN(d);
            ans[++cnt1]=T.query(T.rt[L-1],T.rt[R],x,18);
            q1[cnt1]=(Query){L,R,max(1,cnt0-d+1),cnt0,x};
        } else IN(s),IN(v),q0[++cnt0]=(Add){s,v,cnt0};
    }
    sort(&q0[1],&q0[1+cnt0],cmp);
    for(int i=1;i<=cnt1;++i) modify(1,1,cnt0,q1[i].tl,q1[i].tr,i);
    solve(1,1,cnt0,1,cnt0);
    for(int i=1;i<=cnt1;++i) printf("%d\n",ans[i]);
    return 0;
}