【GDKOI 2016】魔法少女Code&&Details

Code

#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define ll long long
const int maxn=100007;
const int mo=100000007;
struct node{
    int l[2],r[2],zong;
    ll sum[2];
}t[10][maxn*3],ans;
using namespace std;
int i,j,k,l,n,m;
ll ans1;
char ch;
int a[maxn],mi[100];
inline int read(int n)
{
    char ch=getchar();
    while((ch!='-')&&((ch<'0')||(ch>'9')))ch=getchar();
    int q=0,w=1;if(ch=='-')w=-1,ch=getchar();
    while(ch>='0' && ch<='9'){q=q*10+ch-48;ch=getchar();}n=q*w;return n;
}
inline void merge(node &x,int lei,int xx){
    node y=t[lei][xx*2],z=t[lei][xx*2+1];
    x.zong=y.zong^z.zong;
    x.l[0]=(y.l[0]+z.l[y.zong]+1-y.zong)%mo;
    x.r[0]=(z.r[0]+y.r[z.zong]+1-z.zong)%mo;
    x.l[1]=(y.l[1]+y.zong+z.l[1-y.zong])%mo;
    x.r[1]=(z.r[1]+z.zong+y.r[1-z.zong])%mo;
    x.sum[1]=(y.sum[1]+z.sum[1]+y.r[0]*z.l[1]+y.r[1]*z.l[0]+y.r[1]+z.l[1])%mo;
}
inline void merge1(node &x,node y,node z){
    x.zong=y.zong^z.zong;
    x.l[0]=(y.l[0]+z.l[y.zong]+1-y.zong)%mo;
    x.r[0]=(z.r[0]+y.r[z.zong]+1-z.zong)%mo;
    x.l[1]=(y.l[1]+y.zong+z.l[1-y.zong])%mo;
    x.r[1]=(z.r[1]+z.zong+y.r[1-z.zong])%mo;
    x.sum[1]=(y.sum[1]+z.sum[1]+y.r[0]*z.l[1]+y.r[1]*z.l[0]+y.r[1]+z.l[1])%mo;
}
inline void build(int lei,int x,int l,int r){
    int mid=(l+r)/2;
    if(l==r){
        t[lei][x].zong=((a[l]&mi[lei])>0);
    }
    else{
        build(lei,x*2,l,mid);
        build(lei,x*2+1,mid+1,r);
        merge(t[lei][x],lei,x);
    }
}
inline void change(int lei,int x,int l,int r,int y){
    if(l==r){
        t[lei][x].zong=((a[y]&mi[lei])>0);
    }
    else{
        int mid=(l+r)/2;
        if(y<=mid) change(lei,x*2,l,mid,y);
        else change(lei,x*2+1,mid+1,r,y);
        merge(t[lei][x],lei,x);
    }
}
void find(int lei,int x,int l,int r,int y,int z){
    if(l==y&&r==z){
         if (ans.zong<0) ans=t[lei][x];else 
         merge1(ans,ans,t[lei][x]);
    }
    else{
        int mid=(l+r)/2;
        if(z<=mid)find(lei,x*2,l,mid,y,z);
        else if(y>mid)find(lei,x*2+1,mid+1,r,y,z);
        else{
            find(lei,x*2,l,mid,y,mid);
            find(lei,x*2+1,mid+1,r,mid+1,z);
        }
    }
}
int main(){
    scanf("%d",&n);
    fo(i,1,n){
        scanf("%d",&a[i]);
    }
    fo(j,0,9)mi[j]=(1<0,9){
        build(j,1,1,n);
    }
    scanf("%d",&m);
    fo(i,1,m){
       // scanf("%s%d%d",ch,&k,&l);
        ch=getchar();
        while(ch!='Q'&&ch!='M')ch=getchar();
        k=read(k);
        l=read(l);
        ans1=0;
        if(ch=='Q'){
            fo(j,0,9){
                ans.zong=-1;
                find(j,1,1,n,k,l);
                ans1=(ans1+(ans.r[1]+ans.l[1]+ans.sum[1]+ans.zong)*mi[j])%mo;
            }    
            printf("%lld
",ans1);
        }
        else{
            a[k]=l;
            fo(j,0,9){
                change(j,1,1,n,k);
            }  
        } 
    }
}