bzoj 4137 [FJOI2015]火星商店问题【CDQ分治+可持久化trie】

其实我不太清楚这个应该叫CDQ分治还是整体二分

参考：http://blog.csdn.net/lvzelong2014/article/details/78688727

一眼做法是线段树套可持久化trie，但是会MLE+TLE

考虑用CDQ推掉线段树

首先对于没有时间限制的商品建一棵可持久化trie，先更新一遍ans。

然后对于询问和修改分别处理，多记录一维时间，把修改操作按照商店编号排序，对于询问操作的d，改为在时间维度上的一段区间[s,t]

对时间维进行二分，模拟线段树操作。

第一步，对于当前区间[L,R]进行处理。

第二步，枚举所有可能属于当前区间的询问，如果该询问包含本区间，用本区间处理后的答案更新这个询问的答案。

第三步，还原处理数据。

第四步，分治，取mid=L+R>>1，如果某个询问和[L,mid]有交集，那么把这些询问放到询问队列中递归解决左区间。然后再把和[mid+1,R]有交集的询问入队列，递归解决右区间即可。

写了三天，写完我整个人都分治了。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=100005;

int n,m,rt[N],tot,nt,num[N],a[N],dy,ans[N],gc,qc,id[N],d[N],dt;

struct qwe

{

    int c[2],sum;

}t[N*32];

struct wen

{

    int l,r,x,d,s,t;

}q[N];

struct gai

{

    int s,v,t;

}g[N],tmpl[N],tmpr[N];

bool cmp(const gai &a,const gai &b)

{

    return a.s<b.s;

}

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

int zhao(int x)

{

    int l=1,r=nt,re=0;

    while(l<=r)

    {

        int mid=(l+r)>>1;

        if(num[mid]<=x)

            re=mid,l=mid+1;

        else

            r=mid-1;

    }

    return re;

}

void update(int &ro,int pr,int v)

{

    ro=++tot;

	int x=ro;

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

    {

        t[x].sum=t[pr].sum+1;

        t[x].c[0]=t[pr].c[0];

        t[x].c[1]=t[pr].c[1];

        int d=(v&(1<<i))>>i;

        t[x].c[d]=++tot;

        x=t[x].c[d];

        pr=t[pr].c[d];

    }

    t[x].sum=t[pr].sum+1;

}

int ques(int l,int r,int v)

{

    if(l>r)

        return 0;

    int re=0;

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

    {

        int d=(v&(1<<i))>>i;

        if(t[t[r].c[d^1]].sum-t[t[l].c[d^1]].sum)

        {

            re+=(1<<i);

            l=t[l].c[d^1];

            r=t[r].c[d^1];

        }

        else

        {

            l=t[l].c[d];

            r=t[r].c[d];

        }

    }

    return re;

}

void wk(int ml,int mr)

{

    tot=0,nt=0;

    for(int i=ml;i<=mr;i++)

    {

        nt++;

        update(rt[nt],rt[nt-1],g[i].v);

        num[nt]=g[i].s;

    }

    for(int i=1;i<=dt;i++)

    {

        int l=zhao(q[d[i]].l-1),r=zhao(q[d[i]].r);

        ans[d[i]]=max(ans[d[i]],ques(rt[l],rt[r],q[d[i]].x));

    }

}

void cdq(int gl,int gr,int tl,int tr,int w)

{

    if(gl>gr||!w)

        return;

    int mid=(tl+tr)>>1;

    dt=0;

    for(int i=1;i<=w;i++)

        if(q[id[i]].s<=tl&&q[id[i]].t>=tr)

            d[++dt]=id[i];

    wk(gl,gr);

    int lt=0,rt=0;

    for(int i=gl;i<=gr;i++)

    {

        if(g[i].t<=mid)

            tmpl[lt++]=g[i];

        else

            tmpr[rt++]=g[i];

    }

    for(int i=0;i<lt;i++)

        g[i+gl]=tmpl[i];

    for(int i=0;i<rt;i++)

        g[i+gl+lt]=tmpr[i];

    if(tl==tr)

		return;

    int idt=0;

    for(int i=1;i<=w;i++)

        if((q[id[i]].s>tl||q[id[i]].t<tr)&&q[id[i]].s<=mid)

            swap(id[i],id[++idt]);

    cdq(gl,gl+lt-1,tl,mid,idt);

    idt=0;

    for(int i=1;i<=w;i++)

        if((q[id[i]].s>tl||q[id[i]].t<tr)&&q[id[i]].t>mid)

            swap(id[i],id[++idt]);

    cdq(gl+lt,gr,mid+1,tr,idt);

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=n;i++)

    {

        a[i]=read();

        update(rt[i],rt[i-1],a[i]);

    }

    for(int i=1;i<=m;i++)

    {

        int o=read();

        if(!o)

        {

            g[++gc].t=++dy;

            g[gc].s=read(),g[gc].v=read();

        }

        else

        {

            q[++qc].l=read(),q[qc].r=read(),q[qc].x=read();

            int d=read();

            q[qc].s=max(dy-d,0)+1;

            q[qc].t=dy;

            ans[qc]=ques(rt[q[qc].l-1],rt[q[qc].r],q[qc].x);

        }

    }

    sort(g+1,g+1+gc,cmp);

    for(int i=1;i<=qc;i++)

        id[i]=i;

    cdq(1,gc,1,dy,qc);

    for(int i=1;i<=qc;i++)

        printf("%d\n",ans[i]);

    return 0;

}

巴特西

bzoj 4137 [FJOI2015]火星商店问题【CDQ分治+可持久化trie】

最新文章

热门文章