bzoj4137&&dtoj#2259. 火星商店问题

向右看齐 2022-01-07 09:15 110阅读 0赞

### 题目描述： ###

火星上的一条商业街里按照商店的编号$1,2,3,…,n$，依次排列着$n$个商店。商店里出售的琳琅满目的商品中，每种商品都用一个非负整数$val$来标价。每个商店每天都有可能进一些新商品，其标价可能与已有商品相同。

火星人在这条商业街购物时，通常会逛这条商业街某一段路上的所有商店，譬如说商店编号在区间$\[L,R\]$中的商店，从中挑选$1$件自己最喜欢的商品。每个火星人对商品的喜好标准各不相同。通常每个火星人都有一个自己的喜好密码$x$。对每种标价为$val$的商品，喜好密码为$x$的火星人对这种商品的喜好程度与$val$异或$x$的值成正比。也就是说，$val\\space xor\\space x$的值越大，他就越喜欢该商品。每个火星人的购物卡在所有商店中只能购买最近$d$天内（含当天）进货的商品。另外，每个商店都有一种特殊商品不受进货日期限制，每位火星人在任何时刻都可以选择该特殊商品。每个商店中每种商品都能保证供应，不存在商品缺货的问题。

对于给定的按时间顺序排列的事件，计算每个购物的火星人的在本次购物活动中最喜欢的商品，即输出$val\\space xor\\space x$的最大值。这里所说的按时间顺序排列的事件是指以下$2$种事件：

事件$0$，用三个整数$0,s,v$，表示编号为$s$的商店在当日新进一种标价为$v$的商品。

事件$1$，用$5$个整数$1,L,R,x,d$，表示一位火星人当日在编号为$L$到$R$的商店购买$d$天内的商品，该火星人的喜好密码为$x$。

(补充说明：每个事件$0$代表新一天的开始。每个事件$1$和其之前的最后一个事件$0$同一天，如果没有当做第$0$天。第一个事件$0$代表第$1$天的开始。）

### 数据范围： ###

对于数据点 $ 1 $，$ n,m \\leq 1000 $。  
对于数据点 $ 2 , 3$，$ d = 0 $。  
对于数据点 $ 4 , 5 , 6 $，$ d = $进货次数。  
对于数据点 $ 7 $，$ n = m = 20000 $。  
对于数据点 $ 8 $，$ n = m = 50000 $。  
对于所有数据点，$ 1\\leq n,m,x,val\\leq 100000$。

### 算法标签：可持久化trie树，线段树分治 ###

### 思路： ###

对于时间没有要求的点，可以先单独拿出来，建成一棵可持久化线段树，先统计答案。

之后把每一个商品挂在线段树上，之后在线段树上依此递归，每一层只对在当前这层区间的商品在可持久化线段树上更新，并对答案进行更新。

### 以下代码： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define il inline
    #define _(d) while(d(isdigit(ch=getchar())))
    using namespace std;
    const int N=1e5+5;
    int n,m,son[N*20][2],cnt=1,sz[N*20],tot,nt,ans[N],st,top,dy[N],rt[N];
    vector<int> v[N<<2];
    struct node{
        int s,v,d;
    }t[N],tmp1[N],tmp2[N];
    struct data{
        int l,r,ql,qr,v;
    }s[N];
    bool cmp(node t1,node t2){
        return t1.s<t2.s;
    }
    il int read(){
        int x,f=1;char ch;
        _(!)ch=='-'?f=-1:f;x=ch^48;
        _()x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    il void ins(int &x,int y,int v){
        x=++tot;
        int xx=x;
        for(int i=17;i>=0;i--){
            int o=(v>>i)&1;
            son[xx][o]=++tot;son[xx][o^1]=son[y][o^1];
            xx=son[xx][o];y=son[y][o];
            sz[xx]=sz[y]+1;
        }
    }
    il void insert(int x,int l,int r,int ql,int qr,int val){
        if(ql<=l&&r<=qr){
            v[x].push_back(val);return;
        }
        int mid=(l+r)>>1;
        if(ql<=mid)insert(x<<1,l,mid,ql,qr,val);
        if(mid<qr)insert(x<<1|1,mid+1,r,ql,qr,val);
    }
    il int query(int x,int y,int v){
        int ret=0;
        for(int i=17;i>=0;i--){
            int o=(v>>i)&1;
            if(sz[son[x][o^1]]^sz[son[y][o^1]])ret|=(1<<i),x=son[x][o^1],y=son[y][o^1];
            else x=son[x][o],y=son[y][o];
        }
        return ret;
    }
    il void work(int x,int l,int r){
        tot=0;top=0;
        for(int i=l;i<=r;i++){
            int s=t[i].s;
            dy[++top]=s;
            ins(rt[top],rt[top-1],t[i].v);
        }
        for(int i=0;i<v[x].size();i++){
            int now=v[x][i];
            int ql=lower_bound(dy+1,dy+1+top,s[now].l)-dy-1;
            int qr=upper_bound(dy+1,dy+1+top,s[now].r)-dy-1;
            ans[now]=max(ans[now],query(rt[ql],rt[qr],s[now].v));
        }
    }
    il void solve(int x,int l,int r,int ql,int qr){
        work(x,ql,qr);
        if(l==r)return;int mid=(l+r)>>1;
        int a=0,b=0;
        for(int i=ql;i<=qr;i++){
            if(t[i].d<=mid)tmp1[++a]=t[i];
            else tmp2[++b]=t[i];
        }
        for(int i=ql;i<=ql+a-1;i++)t[i]=tmp1[i-ql+1];
        for(int i=ql+a;i<=qr;i++)t[i]=tmp2[i-ql-a+1];
        solve(x<<1,l,mid,ql,ql+a-1);solve(x<<1|1,mid+1,r,ql+a,qr);
    }
    int main()
    {
        n=read();m=read();
        for(int i=1;i<=n;i++)ins(rt[i],rt[i-1],read());
        for(int i=1;i<=m;i++){
            int op=read();
            if(!op){
                int s=read(),v=read();
                t[++cnt]=(node){s,v,cnt};
            }
            else{
                int l=read(),r=read(),x=read(),d=read();
                ans[++st]=query(rt[l-1],rt[r],x);
                s[st]=(data){l,r,max(1,cnt-d+1),cnt,x};
            }
        }
        for(int i=1;i<=st;i++)insert(1,1,cnt,s[i].ql,s[i].qr,i);
        sort(t+1,t+1+cnt,cmp);
        solve(1,1,cnt,1,cnt);
        for(int i=1;i<=st;i++)printf("%d\n",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/Jessie-/p/10434990.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/c7984f59f8cd4bd58e1752fe492169b2.png