P12827 「DLESS-2」XOR and Even 题解

· · 题解

AI 做不出这种题吗，挺有道理的。

最开始做这个题的时候，我就想过如果区间异或上一个数时，如果简单地将线性基内的元素全部异或，那么只有偶数个元素的集合搞出来是正确的，所以直接做是不可行的，但在这个题上却刚刚好。

先用带时间戳的线性基把询问区间的线性基搞出来（要离线扫描线）。

对于第二种询问，我们将线性基中每一个数都异或 2^{30}，x 也异或上 2^{30}，这样因为要贪心取最大值，所以最后的方案一定是取了偶数个数。否则答案不带 2^{30} 一定更小。

对于第一种询问，我们同样地做，这样奇数个数的方案异或出来的值带有 2^{30} > x，所以一定不合法，求答案只需按位贪心，假设前面几位都顶到了上界，此时异或出来的值是确定的，然后分讨计算即可。最后答案要乘上 2^{r-l+1-cnt}（cnt 是线性基的元素个数）。

分讨的部分可以看看代码。

const int V=60;
struct Linear_Basis{
    int b[V+5],tm[V+5];
    inline void Insert(int x,int t,int st){
        for(int i=st;i>=0;i--){
            if((x>>i)&1){
                if(b[i]){
                    if(tm[i]<t){
                        Insert(x^b[i],tm[i],i-1);
                        b[i]=x;tm[i]=t;
                        break;
                    }
                    else x^=b[i];
                }else{
                    b[i]=x;tm[i]=t;
                    break;
                }
            }
        }
    }
    inline int Query(int x,int v){
        int now=v;
        for(int i=30;i>=0;i--)
            if(tm[i]>=x&&!(now>>i&1))
                now^=b[i];
        return now;
    }
    int c[60];
    inline int Get(int l,int r,int x){
        int cnt=0,ans=0,now=0;
        c[0]=(b[0]!=0)&&tm[0]>=l;
        for(int i=1;i<=30;i++)c[i]=c[i-1]+((b[i]!=0)&&tm[i]>=l);
        for(int i=30;i>=0;i--)if(tm[i]>=l&&b[i])++cnt;
        for(int i=30;;i--){
            if(i==-1){
                if(now<=x)Add(ans,1);
                break;
            }
            if(x>>i&1){
                if((now>>i&1)&&(b[i]&&tm[i]>=l))Add(ans,i?m2[c[i-1]]:1);
                if(!(now>>i&1)){
                    if(b[i]&&tm[i]>=l){
                        now^=b[i];
                        if(i)Add(ans,m2[c[i-1]]);
                        else Add(ans,1);
                    }else{
                        if(i)Add(ans,m2[c[i-1]]);
                        else Add(ans,1);
                        break;
                    }
                }
            }else{
                if(now>>i&1){
                    if(!b[i]||tm[i]<l)break;
                    else if(tm[i]>=l)now^=b[i];
                }
            }
        }
        ans=1ll*ans*m2[r-l+1-cnt]%mod;
        return ans;
    }
    inline void Clear(){
        memset(b,0,sizeof b);
        memset(tm,0,sizeof tm);
    }
}LB;
inline void Solve(){
    rd(n,q);
    for(int i=1;i<=n;i++)rd(a[i]);
    for(int i=1;i<=q;i++){
        int op,l,r,x;rd(op,l,r,x);
        vec[r].emplace_back(op,l,x,i);
    }
    LB.Clear();
    for(int i=1;i<=n;i++){
        LB.Insert(a[i]^(1<<30),i,30);
        for(auto[op,l,x,id]:vec[i]){
            if(op==1){
                ans[id]=LB.Query(l,x^(1<<30))^(1<<30);
            }else{
                ans[id]=LB.Get(l,i,x);
            }
        }
    }
    for(int i=1;i<=n;i++)vec[i].clear();
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
signed main(){
    m2[0]=1;
    for(int i=1;i<=500000;i++)m2[i]=m2[i-1]*2%mod;
    rd(T);
    while(T--)Solve();
    return 0;
}