P4585 [FJOI2015]火星商店问题线段树分治+可持久化trie树

绝地灬酷狼 2023-08-17 15:48 83阅读 0赞

题意：有编号为1-n的商店 每个商店有一个永久化的商品价值为v

操作1：时间过了一天 第x商店增加了一个价值为val的货物

操作2：该火星人有自己的密码值x 问第L个商店到第R个商店的 当前天-d+1 到 当前天 的所有货物中（包括永久化商品) 异或x的最大值

最大异或值显然是可持久化trie树

一开始永久化的话在一开始更新即可

建立一棵时间线段树 先把火星人扔进时间线段树

然后把操作按照时间进行cdq即可

注意操作要按商店编号排序 因为可持久化更新要求有序性

注意商店编号不一定是连续的 所以用一个序来维护可持久化trie

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

#include<bits/stdc++.h>
    using namespace std;
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define repp(i,a,b) for(int i=(a);i>=(b);--i)
    #define ll long long
    #define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
    #define inf 0x3f3f3f3f
    #define CLR(A,v)  memset(A,v,sizeof A)
    /
    const int N=1e5+10;
    int t[N<<5][2],T[N],siz[N<<5],ncnt,b[N];
    void upnode(int k,int x,int pre,int &pos)
    {
        pos=++ncnt;
        t[pos][0]=t[pre][0];t[pos][1]=t[pre][1];
        siz[pos]=siz[pre]+1;
        if(k<0)return ;
        int c=(x>>k)&1;
        upnode(k-1,x,t[pre][c],t[pos][c]);
    }
    int qmax(int k,int x,int pre,int pos)
    {
        if(k<0)return 0;
        int c=(x>>k)&1;
        if( siz[t[pos][c^1]-t[pre][c^1]]>0 )return (1<<k)+qmax(k-1,x,t[pre][c^1],t[pos][c^1]);
        else return qmax(k-1,x,t[pre][c],t[pos][c]);
    }
    vector<int>node[N<<2];
    int n,m,ans[N];
    void addnode(int x,int L,int R,int l,int r,int pos)
    {   
        if(L>R)return ;
        if(L<=l&&r<=R){node[pos].push_back(x);return;}
        int m=(l+r)>>1;
        if(L<=m)addnode(x,L,R,l,m,pos<<1);
        if(R>m)addnode(x,L,R,m+1,r,pos<<1|1);
    }
    struct marspeo{
         int L, R, s, t, x;}peo[N];
    struct upp{
         int t,x,val;}up[N],s1[N],s2[N];
    int cnt1,cnt0;
    
    void calc(int L,int R,int pos)
    {   
        int nn=0;ncnt=0;
        rep(i,L,R)
        {   
            nn++;b[nn]=up[i].x;
            upnode(20,up[i].val,T[nn-1],T[nn]);
        }
        for(auto v:node[pos])
        {   
            int l=lower_bound(b+1,b+1+nn,peo[v].L)-b;
            int r=upper_bound(b+1,b+1+nn,peo[v].R)-b-1;
            int temp=qmax(20,peo[v].x,T[l-1],T[r]);
            ans[v]=max(ans[v],temp);
        }
    }
    void cdq(int L,int R,int l,int r,int pos)//L R 为操作数
    {
        if(L>R)return ;
        calc(L,R,pos);
        if(l==r)return ;
        int temp1=0,temp2=0,mid=(l+r)>>1;
        rep(i,L,R)
        if(up[i].t<=mid)s1[++temp1]=up[i];
        else s2[++temp2]=up[i];
        rep(i,1,temp1)up[i+L-1]=s1[i];
        rep(i,1,temp2)up[i+L+temp1-1]=s2[i];
        cdq(L,L+temp1-1, l,mid,pos<<1);
        cdq(L+temp1,R,   mid+1,r,pos<<1|1);
    }
    int main()
    {
        scanf("%d%d",&n,&m);int x,l,r,op,d;
        rep(i,1,n)scanf("%d",&x),upnode(20,x,T[i-1],T[i]);
        while(m--)
        {
            scanf("%d",&op);
            if(!op){scanf("%d%d",&l,&r);cnt0++;up[cnt0]=(upp){cnt0,l,r};}
            else 
            {   
                scanf("%d%d%d%d",&l,&r,&x,&d);
                peo[++cnt1]=(marspeo){l,r,max(1,cnt0-d+1),cnt0,x};
                ans[cnt1]=qmax(20,x,T[l-1],T[r]);
            }
        }
        rep(i,1,cnt1)addnode(i,peo[i].s,peo[i].t,1,cnt0,1);
        sort(up+1,up+1+cnt0,[](upp a,upp b){
         return a.x<b.x;});
        cdq(1,cnt0,1,cnt0,1);
        rep(i,1,cnt1)printf("%d\n",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/bxd123/p/11587195.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/3ec409aa732844fc8f4c8ac45ce8f2d6.png