[GDKOI2016] Day1 魔卡少女 線段樹

很久之前寫的題，今天看到的一句話概括了這道題的精髓：

xor的每一位具有獨立性，分開維護即可

10棵線段樹+1e8+7，很好寫很好過

#include <iostream>
#include <cstdio>

#define N 2000050
#define mod 100000007

#define mid ( (l+r)>>1 )
#define ls l,mid,(t<<1)
#define rs mid+1,r,((t<<1)^1)

using namespace std;

typedef long long LL;
int a[N],n,m,p,x,v,ll,rr;
LL ans;

struct Tree{LL siz,sum,L,R,f;}identity,S;

struct Segment_Tree{
    Tree tr[N];
    LL yh(int t,int p) {
        return p ==  ? tr[t].siz - tr[t].L : tr[t].siz - tr[t].R;
    }

    Tree mer(Tree p1,Tree p2) {
        Tree tmp = identity;
        tmp.siz = p1.siz + p2.siz;
        tmp.f   = p1.f   ^ p2.f;
        tmp.L = p1.L + (p1.f ? (p2.siz - p2.L) : p2.L);
        tmp.R = p2.R + (p2.f ? (p1.siz - p1.R) : p1.R);

        tmp.sum = (p1.sum + p2.sum) % mod;
        tmp.sum = ( tmp.sum + p1.R * (p2.siz - p2.L) + p2.L * (p1.siz - p1.R) ) % mod;
        return tmp;
    }

    void build(int l,int r,int t) {
        if (l == r) { 
            tr[t].sum = tr[t].f = tr[t].L = tr[t].R = (a[l]&); 
            tr[t].siz = ; 
            return ; 
        }
        build(ls); build(rs);
        tr[t] = mer(tr[*t],tr[*t+]);
    }
    void update(int l,int r,int t) {
        if (l == r) { tr[t].sum = tr[t].f = tr[t].L = tr[t].R = (v&); return ; }
        if (p<=mid) update(ls); else update(rs);
        tr[t] = mer(tr[*t],tr[*t+]);
    }
    void query(int l,int r,int t) {
        if (l >= ll && r <= rr) { S = mer(S,tr[t]); return ;}
        if (ll <= mid) query(ls);
        if (rr > mid) query(rs);
    }
}T[];

void solve() {
    scanf("%d",&n);
    for (int i=;i<=n;i++) scanf("%d",&a[i]);
    for (int i=;i<;i++) {
        T[i].build(,n,);
        for (int j=;j<=n;j++) a[j] >>= ;
    }
    scanf("%d",&m);
    while (m--) {
        char cmd[]; scanf("%s",cmd+);
        if (cmd[] == 'M') {
            scanf("%d%d",&p,&x);
            for (int i=;i<;i++) {
                v = (x&); x >>= ;
                T[i].update(,n,);
            }
        } else {
            scanf("%d%d",&ll,&rr);
            ans = 0LL;
            for (int i=;i<;i++) {
                S = identity;
                T[i].query(,n,);
                ans = (ans + S.sum * (LL<<i)) % mod;
            }
            printf("%d\n",(int)ans);
        }
    }
}

int main()
{
    freopen("cardcaptor.in","r",stdin); 
    freopen("cardcaptor.out","w",stdout);
    solve();
    fclose(stdin); fclose(stdout);
    return ;
}