CodeForces - 587E[线段树+线性基+差分] ->(线段树维护区间合并线性基)

题意：给你一个数组，有两种操作，一种区间xor一个值，一个是查询区间xor的结果的种类数

做法一：
对于一个给定的区间，我们可以通过求解线性基的方式求出结果的种类数，而现在只不过将其放在线树上维护区间线性基。

用线段树去维护区间合并

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5;

struct node {

    int bas[],lazy,st;

    void init() {

        memset(bas,,sizeof(bas));

        lazy = ;st = ;

    }

    int Count() {

        int ans = ;

        for(int i = ;i<=;i++) {

            if(bas[i]) ans++;

        }

        return ans;

    }

    void add(int x) {

        for(int i = ;i>=;i--) {

            if((x>>i)&){

                if(bas[i])x^=bas[i];

                else {

                    bas[i] = x;

                    break;

                }

            }

        }

    }

    node operator + (const node &a) const{

        node ans;  ans.init();

        for(int i = ;i<=;i++) {

            ans.add(bas[i]);

            ans.add(a.bas[i]);

        }

        ans.add(st^a.st);

        ans.st = a.st;

        return ans;

    }

}tr[*maxn],ans;

int n,q;

void pushdown(int st) {

    if(tr[st].lazy) {

        tr[st<<].lazy ^= tr[st].lazy;

        tr[st<<].st ^= tr[st].lazy;

        tr[st<<|].lazy ^= tr[st].lazy;

        tr[st<<|].st ^= tr[st].lazy;

        tr[st].lazy = ;

    }

}

void build(int l,int r,int st) {

    tr[st].init();

    if(l == r) {

        scanf("%d",&tr[st].st);

        return ;

    }

    int mid = (l+r)>>;

    build(l,mid,st<<);

    build(mid+,r,st<<|);

    tr[st] = tr[st<<] + tr[st<<|];

}

void update(int l,int r,int st,int L,int R,int d) {

    if(l>=L && r<=R) {

        tr[st].lazy ^= d;

        tr[st].st ^= d;

        return ;

    }

    pushdown(st);

    int mid = (l+r) >>;

    if(L<=mid) update(l,mid,st<<,L,R,d);

    if(R> mid) update(mid+,r,st<<|,L,R,d);

    tr[st] = tr[st<<] + tr[st<<|];

}

void Query(int l,int r,int st,int L,int R) {

    if(l >= L && r <= R) {

        ans = ans + tr[st];

        return ;

    }

    pushdown(st);

    int mid = (l+r) >>;

    if(L<=mid) Query(l,mid,st<<,L,R);

    if(R>mid)  Query(mid+,r,st<<|,L,R);

    tr[st] = tr[st<<] + tr[st<<|];

}

int main() {

    int op,l,r,d;

    scanf("%d %d",&n,&q);

    build(,n,);

    while(q--) {

        scanf("%d %d %d",&op,&l,&r);

        if(op == ) {

            scanf("%d",&d);

            update(,n,,l,r,d);

        }

        else {

            ans.init();

            Query(,n,,l,r);

            printf("%d\n",<<ans.Count());

        }

    }

    return ;

}

做法二：

对原序列a进行差分，使得b[i] = a[i] ^ a[i+1]，那么al,al+1,al+2,ar可以构成的一个异或和，在al,bl,bl+1,bl+2,br-1中肯定也可以被构造出来，因此二者是等价的。

对于a序列的区间[l,r]的更新实际上b序列上只有bl-1和br被影响，中间的数由于是两两所以抵消掉了。

所以现在就变成了单点更新线段树维护区间线性基，然后再用一个树状数组维护l位置被修改的值，这也用到了差分，这里的作用是要求a[l]的值。

#include <bits/stdc++.h>

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const int mx = 2e5 + ;

int n,m,a[mx],b[mx];

int pre[mx],mv;

struct node{

    int gao[];

    void add(int x){

        for(int i=;i>=;i--){

            if(x&(<<i)){

                if(!gao[i]){

                    gao[i] = x;

                    break;

                }else x ^= gao[i];

            }

        }

    }

    node operator + (node A)const

    {

        node ret = A;

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

        if(gao[i]) ret.add(gao[i]);

        return ret;

    }

}s[mx<<];

void add(int x,int v){

    while(x<=n){

        pre[x] ^= v;

        x += x&(-x);

    }

}

int getpre(int x){

    int ans = ;

    while(x){

        ans ^= pre[x];

        x -= x&(-x);

    }

    return ans;

}

void build(int l,int r,int rt)

{

    if(l==r){

        b[l] = a[l]^a[l+];

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

        if((<<i)&b[l]){

            s[rt].gao[i] = b[l];

            break;

        }

        return ;

    }

    int mid = (l+r)>>;

    build(lson);build(rson);

    s[rt] = s[rt<<] + s[rt<<|];

}

void update(int l,int r,int rt,int M)

{

    if(l==r){

        b[l] ^= mv;

        memset(s[rt].gao,,sizeof(s[rt].gao));

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

        if((<<i)&b[l]){

            s[rt].gao[i] = b[l];

            break;

        }

        return ;

    }

    int mid = (l+r)>>;

    if(M<=mid) update(lson,M);

    else update(rson,M);

    s[rt] = s[rt<<] + s[rt<<|];

}

node query(int l,int r,int rt,int L,int R)

{

    if(L<=l&&r<=R) return s[rt];

    int mid = (l+r)>>;

    if(L<=mid&&R>mid) return query(lson,L,R) + query(rson,L,R);

    if(L<=mid) return query(lson,L,R);

    return query(rson,L,R);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d",a+i);

    if(n>) build(,n-,);

    int o,l,r;

    while(m--){

        scanf("%d%d%d",&o,&l,&r);

        if(o==){

            scanf("%d",&mv);

            add(l,mv);add(r+,mv);

            if(l>) update(,n-,,l-);

            if(r<n) update(,n-,,r);

        }else{

            int v = a[l]^getpre(l);

            if(n==||l==r) printf("%d\n",v?:);

            else{

                node ans = query(,n-,,l,r-);

                ans.add(v);

                int ret = ;

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

                if(ans.gao[i]) ret++;

                printf("%d\n",<<ret);

            }

        }

    }

    return ;

}

巴特西

CodeForces - 587E[线段树+线性基+差分] ->(线段树维护区间合并线性基)

最新文章

热门文章