[FJOI2015]火星商店问题（线段树分治+可持久化Trie）

重新写一年前抄题解的那题，当时我啥都不会只是Ctrl+C，Ctrl+V写过的题，今天重新写一遍。

题解：

不会线段树分治，还是学一下这东西吧，这是我的第一道线段树分治。

首先对于特殊商品，可以直接可持久化Trie记录答案。首先考虑对每个线段树开一个vector，把询问的时间区间看成一段一段的塞到线段树里，修改实际上是相当于一个后缀。然后把修改按位置排序，然后仿照线段树的形式按时间分治，mid前的修改扔到左边数组里递归，反之扔到右边，这样能够排除这一维的限制。然后空间上用可持久化Trie，前缀和相减即可。最开始的修改，要按照商店顺序排序，这样可以把中间的商店忽略，一个修改挨着一个修改建主席树，复杂度得以保证。

#include<bits/stdc++.h>

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const int N=1e5+;

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

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

int n,m,n1,n2,tot,top,rt[N],ans[N],st[N],ch[N*][],sz[N*];

vector<int>a[N];

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

void build(int&x,int u,int S)

{

    x=++tot;

    int now=x;

    for(int i=;~i;i--)

    {

        bool d=S>>i&;

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

        now=ch[now][d],u=ch[u][d],sz[now]=sz[u]+;

    }

}

int query(int l,int r,int S)

{

    int ret=;

    for(int i=;~i;i--)

    {

        bool d=S>>i&;

        if(sz[ch[r][d^]]-sz[ch[l][d^]]>)l=ch[l][d^],r=ch[r][d^],ret+=<<i;

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

    }

    return ret;

}

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

{

    if(L>R)return;

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

    int mid=l+r>>;

    if(L<=mid)update(L,R,x,lson);

    if(R>mid)update(L,R,x,rson);

}

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

{

    top=tot=;

    for(int i=L;i<=R;i++)st[++top]=q[i].s,build(rt[top],rt[top-],q[i].v);

    for(int i=,k,l,r;i<a[x].size();i++)

    {

        k=a[x][i];

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

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

    }

}

void divide(int l,int r,int rt,int L,int R)

{

    if(L>R)return;

    int mid=l+r>>,cnt1=,cnt2=;

    calc(rt,L,R);

    if(l==r)return;

    for(int i=L;i<=R;i++)if(q[i].t<=mid)t1[++cnt1]=q[i];else t2[++cnt2]=q[i];

    for(int i=;i<=cnt1;i++)q[i+L-]=t1[i];

    for(int i=;i<=cnt2;i++)q[i+L-+cnt1]=t2[i];

    divide(lson,L,L+cnt1-);

    divide(rson,L+cnt1,R);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,x;i<=n;i++)scanf("%d",&x),build(rt[i],rt[i-],x);

    for(int i=,op,l,r,x,d;i<=m;i++)

    {

        scanf("%d%d%d",&op,&l,&r);

        if(!op)q[++n1]=(buy){l,r,n1};

        else{

            scanf("%d%d",&x,&d);

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

            p[n2]=(guest){l,r,max(,n1-d+),n1,x};

        }

    }

    for(int i=;i<=n2;i++)update(p[i].L,p[i].R,i,,n1,);

    sort(q+,q+n1+,cmp);

    divide(,n1,,,n1);

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

}

巴特西

[FJOI2015]火星商店问题（线段树分治+可持久化Trie）

最新文章

热门文章