【gdkoi2016】【day1t1】【魔卡少女】【cardcaptor】【線段樹】

魔卡少女cardcaptor

題意：一段數，支援單點修改，查詢一段區間内子區間異或和的和。

具體做法：先做個異或字首和， [l,r] 異或和即 ∑sum[i]⊕sum[j](l−1<=i,j<=r)(⊕為異或) ，每個位對答案的貢獻為 [l−1,r] 中零的個數乘以一的個數，至于為什麼可以自行腦補。對于修改可以把不同的位的 [x,n] 的零和一的個數調換，對此可以懶标記區間修改，但是一定要記得修改完兒子後，把自己的零和一的個數重新統計一下。為此我調試了半天~~~。可是常數巨大，貼上tle80分的代碼。

#include<set>
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const oo=;
int const maxn=;
int const p=;
typedef struct{int x,y;}note;
inline int get(){
    char ch=getchar();while((ch!='-')&&((ch<'0')||(ch>'9')))ch=getchar();
    int u=,v=;if(ch=='-')u=-;else v=ch-'0';ch=getchar();
    while((ch>='0')&&(ch<='9'))v=v*10+ch-'0',ch=getchar();
    return u*v;
}
inline char getch(){
    char ch=getchar();
    while((ch<'A')||(ch>'Z'))ch=getchar();
    return ch;
}
int n,m,a[maxn+],tr[maxn*6+][+][],exchange[maxn*6+][+];
inline void scan(){
    //srand(time(NULL));
    //rand()%100;
    n=get();
    fo(i,,n)
        a[i]=get();
}
void add(int t,int l,int r,int i,int j,int k){
    tr[t][i][j]++;
    if(l==r)return;
    int m=(l+r)/;
    if(k<=m)add(t*2,l,m,i,j,k);
    else add(t*2+,m+,r,i,j,k);
}
void relax(int t,int i){
    if(exchange[t][i]){
        exchange[t][i]=false;
        int tt=tr[t][i][];
        tr[t][i][]=tr[t][i][];
        tr[t][i][]=tt;
        exchange[t*2][i]=!exchange[t*2][i];
        exchange[t*2+][i]=!exchange[t*2+][i];
    }
}
void updata(int t,int i){
    tr[t][i][]=tr[t*2][i][]+tr[t*2+][i][];
    tr[t][i][]=tr[t*2][i][]+tr[t*2+][i][];
}
ll get(int t,int l,int r,int i,int j,int l1,int r1){
    relax(t,i);
    if((l==l1)&&(r==r1))return tr[t][i][j];
    int m=(l+r)/,ans=;
    if(r1<=m)ans=get(t*2,l,m,i,j,l1,r1);
    else if(m<l1)ans=get(t*2+,m+,r,i,j,l1,r1);
    else ans=get(t*2,l,m,i,j,l1,m)+get(t*2+,m+,r,i,j,m+,r1);
    relax(t*2,i);relax(t*2+,i);
    updata(t,i);
    return ans;
}
void change(int t,int l,int r,int i,int l1,int r1){
    if((l==l1)&&(r==r1))
        exchange[t][i]=!exchange[t][i];
    relax(t,i);
    if((l==l1)&&(r==r1))return;
    int m=(l+r)/;
    if(r1<=m)change(t*2,l,m,i,l1,r1);
    else if(m<l1)change(t*2+,m+,r,i,l1,r1);
    else{
        change(t*2,l,m,i,l1,m);
        change(t*2+,m+,r,i,m+,r1);
    }
    relax(t*2,i);relax(t*2+,i);
    updata(t,i);
}
inline void solve(){
    int sum=;
    fo(i,,n){
        int tmp=sum;
        fo(j,,){
            add(,,n,j,tmp%2,i);
            tmp/=;
        }
        sum^=a[i+];
    }
    m=get();
    fo(i,,m){
        char ch=getch();
        int x=get(),y=get();
        if(ch=='Q'){
            ll ans=;
            fd(j,,)
                ans=((((<<(j-))*get(,,n,j,,x-,y))%p*get(,,n,j,,x-,y))%p+ans)%p;
            printf("%lld\n",ans);
        }
        else{
            int tmp=y;
            fo(j,,){
                if(a[x]%2!=tmp%2)
                    change(,,n,j,x,n);
                a[x]/=;
                tmp/=;
            }
            a[x]=y;
        }
    }
}
int main(){
    scan();
    solve();
    return ;
}