P4839

Inui_Sana · 2024-04-22 22:47:11 · 题解

有人搞错了复杂度白开心了一下午/kk

基于离线 ST 表+前缀线性基合并的 O(m\log m\log^2V)-O(\log^2V) 做法。

upd：@chenxinyang2006 的在线 O(n\log V(\log V+\log m)) 做法。

考虑将操作离线下来，具体是对于序列的每一个位置开一个类似前缀线性基（即 CF1100F 中的 trick），优先记录操作时间 t 更小的向量。这里就要提到时间轴的一个很好的性质：我们只记录最小时间产生的 01 向量一定是更优的。

然后用 ST 表维护区间的前缀线性基的并。可以用 ST 表是因为线性基显然是有可重复贡献性的。至于前缀线性基合并，和普通线性基合并相差无几。

总时间复杂度是 O(m\log m\log^2V+n\log^2V)。由于用线段树维护的许多剪枝方法不能用在这种线性基上，且 n,m 同阶，所以跑得远不如大部分 O(n\log m\log^2V) 快。但还是有一定意义的吧（

code：

int n,m,k,l[N],r[N],t[N];
struct XXJ{
    int a[31],b[31];
    void insert(int x,int t){
        drep(i,30,0){
            if(!(x>>i&1)){
                continue;
            }
            if(a[i]){
                if(t<b[i]){
                    swap(a[i],x),swap(b[i],t);
                }
                x^=a[i];
            }else{
                a[i]=x,b[i]=t;
                break;
            }
        }
    }
    int query(int x,int t){
        drep(i,30,0){
            if((x^a[i])>x&&b[i]<=t){
                x^=a[i];
            }
        }
        return x;
    }
    XXJ operator+(const XXJ &rhs)const{
        XXJ r;
        rep(i,0,30){
            r.a[i]=a[i],r.b[i]=b[i];
        }
        rep(i,0,30){
            if(rhs.a[i]){
                r.insert(rhs.a[i],rhs.b[i]);
            }
        }
        return r;
    }
};
struct STable{
    XXJ st[17][N];
    void init(){
        rep(i,1,__lg(m)){
            rep(j,1,m-(1<<i)+1){
                st[i][j]=st[i-1][j]+st[i-1][j+(1<<(i-1))];
            }
        }
    }
    XXJ query(int l,int r){
        int k=__lg(r-l+1);
        return st[k][l]+st[k][r-(1<<k)+1];
    }
}ST;
void Yorushika(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        int op=read(),x=read(),y=read();
        if(op==1){
            ST.st[0][x].insert(y,i);
        }else{
            k++,l[k]=x,r[k]=y,t[k]=i;
        }
    }
    ST.init();
    rep(i,1,k){
        printf("%d\n",ST.query(l[i],r[i]).query(0,t[i]));
    }
}
signed main(){
    int t=1;
    //  scanf("%d",&t);
    while(t--)
        Yorushika();
}

upd：@chenxinyang2006 在他的 P5607 题解中提到了这题的 log^2 在线做法。大致讲一下。

具体就是运用猫树的思想建一棵线段树。每个节点如果是它父亲的左儿子，则维护一个后缀线性基，否则维护前缀线性基，根节点空。

每次修改，我们不再只修改叶子节点，而是将线段树上对应儿子到根的整条链修改。这是一个很巧妙的均摊复杂度的方法，因为注意到原来不算 pushup，每次只需要 O(\log m+\log V) 的复杂度。新做法中，一共 O(\log m) 次 O(\log V) 的插入。并不影响复杂度。

查询时，类似猫树分治的做法，设询问区间为 [L,R]，找到第一个满足 L\le mid\le R 的区间 [l,r]，因为维护了区间的前/后缀线性基，我们只需要一次简单的 O(\log^2V) 的合并，再在线性基中查询最大值，就可以完成询问。

总时间复杂度 O(n\log V(\log V+\log m))。非常优秀的做法，同时也是非常有启发意义的。

int n,m,k,l[N],r[N],t[N];
struct XXJ{
    int a[31],b[31];
    void insert(int x,int t,int lim){
        drep(i,30,0){
            if(!(x>>i&1)){
                continue;
            }
            if(a[i]){
                if(abs(t-lim)<abs(b[i]-lim)){
                    swap(a[i],x),swap(b[i],t);
                }
                x^=a[i];
            }else{
                a[i]=x,b[i]=t;
                break;
            }
        }
    }
    int query(int x){
        drep(i,30,0){
            if((x^a[i])>x){
                x^=a[i];
            }
        }
        return x;
    }
};
struct SGT{
    XXJ tr[N<<2];
    void update(int l,int r,int o,int x,int y){
        if(o>1){
            if(o&1){
                tr[o].insert(y,x,0);
            }else{
                tr[o].insert(y,x,m);
            }
        }
        if(l==r){
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            update(l,mid,o<<1,x,y);
        }else{
            update(mid+1,r,o<<1|1,x,y);
        }
    }
    int query(int l,int r,int o,int x,int y){
        int mid=(l+r)>>1;
        if(x<=mid&&y>=mid){
            XXJ r;
            rep(i,0,30){
                r.a[i]=r.b[i]=0;
                if(tr[o<<1].b[i]>=x&&tr[o<<1].b[i]<=y){
                    r.insert(tr[o<<1].a[i],0,0);
                }
                if(tr[o<<1|1].b[i]>=x&&tr[o<<1|1].b[i]<=y){
                    r.insert(tr[o<<1|1].a[i],0,0);
                }
            }
            return r.query(0);
        }
        if(x<=mid){
            return query(l,mid,o<<1,x,y);
        }
        return query(mid+1,r,o<<1|1,x,y);
    }
}T;
void Yorushika(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        int op=read(),x=read(),y=read();
        if(op==1){
            T.update(1,m,1,x,y);
        }else{
            printf("%d\n",T.query(1,m,1,x,y));
        }
    }
}
signed main(){
    int t=1;
    //  scanf("%d",&t);
    while(t--)
        Yorushika();
}