[FJOI2015]火星商店问题(线段树分治,可持久化,Trie树)

[FJOI2015]火星商店问题

前天考了到线段树分治模板题,全场都切了,就我不会QAQ

于是切题无数的Tyher巨巨就告诉我:"你可以去看看火星商店问题,看了你就会了."

第一道线段树分治题,看了yyb博客,学习了一波.

其实线段树分治就是对操作的时间分治.

对线段树每个节点开一个\(vector\),把询问的区间(时间的区间)看成一段一段放到线段树的\(vector\)里面存着.

注意到修改会延续到最后一刻,所以修改只是左端点不一样而已,相当于一个后缀.

把修改按照位置排序(这个时候时间是乱序的),接着仿照线段树的形式按时间分治,在\(mid\)之前的修改,就扔到左边的数组里递归,否则就扔到右边的子树.这样就除掉了时间这一维的限制.

那么空间这一维,就用一个可持久化trie树来维护,\(r\)和\(l-1\)的对应的字典树前缀和相减就是区间的字典树.注意最开始修改要按照商店编号排序,这样按照时间分拣之后它的商店编号依然是有序的,你不妨把这些有修改的商店之间的其他商店都忽略掉,一个修改挨着一个修改地构建主席树,保证了时间复杂度.

还有一个值得注意的问题,就是当把点加到可持久化字典树里的时候,要重新从当前左端点构出字典树(相当于清空这棵可持久化字典树,假如这个询问对应的答案是当前区间之前的某次修改加入的值,那么这个询问也一定会被丢到对应的线段树节点上计算,所以不用担心之前的修改会影响询问的答案)这样可以避免撤销带来的常数.

再按照trie树找异或最大值的方法来找答案,一个询问会被放到线段树的多个节点上(会被分成很多段时间),所以答案要取\(max\).

注意线段树上的是修改时间,字典树是按照空间构建的.这个很重要,总是写着写着就忘了...

时间复杂度\(O(nlog^2n)\),线段树分治和trie树\(nlogn\),字典树\(logn\)

#include<bits/stdc++.h>

#define maxn 100005

#define mid ((l+r)>>1)

#define rc ((rt<<1)|1)

#define lc (rt<<1)

using namespace std;

int gi()

{

    char c;int x,sign=1;

    while((c=getchar())>'9'||c<'0')if(c=='-')sign=-1;

    x=c-'0';while((c=getchar())>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0';

    return x*sign;

}

int n,m,cnt1,cnt2,tot,top;

int rt[maxn],ans[maxn],st[maxn];

int ch[maxn*20][2],sz[maxn*20];

vector<int> a[maxn];

struct guest{int l,r,L,R,x;}p[maxn];

struct buy{int s,v,t;}q[maxn],t1[maxn],t2[maxn];

bool cmp(const buy x,const buy y){return x.s<y.s;}

void insert(int &x,int u,int w)

{

    int now;now=x=++tot;

    for(int i=17;i>=0;i--)

    {

        bool d=w&(1<<i);

        ch[now][d^1]=ch[u][d^1];ch[now][d]=++tot;

        now=ch[now][d];u=ch[u][d];

        sz[now]=sz[u]+1;

    }

}

int query(int l,int r,int w)

{

    int res=0;

    for(int i=17;i>=0;i--)

    {

        bool d=w&(1<<i);

        if(sz[ch[r][d^1]]-sz[ch[l][d^1]]>0)

            l=ch[l][d^1],r=ch[r][d^1],res+=(1<<i);

        else l=ch[l][d],r=ch[r][d];

    }

    return res;

}

void update(int rt,int l,int r,int L,int R,int x)

{

    if(L>R||r<L||l>R)return ;

    if(L<=l&&r<=R){a[rt].push_back(x);return;}

    update(lc,l,mid,L,R,x);update(rc,mid+1,r,L,R,x);

}

void calc(int x,int L,int R)

{

    top=tot=0;

    for(int i=L;i<=R;i++)

    {

        st[++top]=q[i].s;

        insert(rt[top],rt[top-1],q[i].v);

    }

    for(int i=0,sz=a[x].size();i<sz;i++)

    {

        int k=a[x][i],t;

        int l=upper_bound(st+1,st+1+top,p[k].l-1)-st-1;

        int r=upper_bound(st+1,st+1+top,p[k].r)-st-1;

        ans[k]=max(ans[k],t=query(rt[l],rt[r],p[k].x));

        //cout<<x<<" "<<k<<" "<<t<<endl;

    }

}

void divide(int rt,int l,int r,int L,int R)//按时间分治

{

    if(L>R)return;

    int cn1=0,cn2=0;

    calc(rt,L,R);

    if(l==r)return;

    for(int i=L;i<=R;i++)//修改的区间右端点都是cnt1,相当于影响到之后的时间

        if(q[i].t<=mid)t1[++cn1]=q[i];

        else t2[++cn2]=q[i];

    for(int i=1;i<=cn1;i++)q[i+L-1]=t1[i];//左端点在mid左边的放在左区间

    for(int i=1;i<=cn2;i++)q[i+L-1+cn1]=t2[i];//否则放右边

    divide(lc,l,mid,L,L+cn1-1);

    divide(rc,mid+1,r,L+cn1,R);

}

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)insert(rt[i],rt[i-1],gi());

    for(int i=1,ty,l,r,x,d,s,v;i<=m;i++)

    {

        ty=gi();

        if(!ty)s=gi(),v=gi(),q[++cnt1]=(buy){s,v,cnt1};//起点,价格,时间

        else

        {

            l=gi(),r=gi(),x=gi(),d=gi();

            ans[++cnt2]=query(rt[l-1],rt[r],x);

            p[cnt2]=(guest){l,r,max(1,cnt1-d+1),cnt1,x};

            //商店左端点,商店右端点,开始时间,结束时间,喜好密码

        }

    }

    for(int i=1;i<=cnt2;i++)update(1,1,cnt1,p[i].L,p[i].R,i);

    sort(q+1,q+1+cnt1,cmp);//按照商店编号排序

    divide(1,1,cnt1,1,cnt1);

    for(int i=1;i<=cnt2;i++)printf("%d\n",ans[i]);

    return 0;

}