fzu 2105 Digits Count

题目大意：

长度为n（1~10^6）的数组A[]（0<=A[i]<16），有4中操作。

1：and opn l r l<=i<=r A[i]&opn

2：or opn l r l<=i<=r A[i]|opn

3：xor opn l r l<=i<=r A[i]^opn

1：sum l r l<=i<=r sum{A[l~r]}

操作总数为m（1~10^5）。

题目思路：

很裸的线段树，维护区间中每个数各位上1的个数。

就是要细心，不然可能会写错。

代码：

[cpp]
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define eps (1e-8)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#pragma comment(linker, "/STACK:102400000,102400000")
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
template <class T> T _abs(T x){return (x < 0)? -x:x;}
template <class T> T _mod(T x,T y){return (x > 0)? x%y:((x%y)+y)%y;}
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
template <class T> void getmax(T& x,T y){x=(y > x)? y:x;}
template <class T> void getmin(T& x,T y){x=(x<0 || y<x)? y:x;}
int TS,cas=1;
const int M=1000000+5;
int n,m;
int cv[M<<2][4],xr[M<<2][4];
int sum[M<<2][4],len[M<<2],a;

void pushUp(int rt){
    for(int i=0;i<4;i++) sum[rt][i]=sum[ls][i]+sum[rs][i];
}

void pushDown(int rt){
    for(int i=0;i<4;i++){
        if(cv[rt][i]!=-1){
            sum[ls][i]=(cv[ls][i]=cv[rt][i])*len[ls];
            sum[rs][i]=(cv[rs][i]=cv[rt][i])*len[rs];
            cv[rt][i]=-1,xr[ls][i]=xr[rs][i]=0;
        }else if(xr[rt][i]){
            sum[ls][i]=len[ls]-sum[ls][i];
            if(cv[ls][i]!=-1) cv[ls][i]^=1;
            else xr[ls][i]^=1;
            sum[rs][i]=len[rs]-sum[rs][i];
            if(cv[rs][i]!=-1) cv[rs][i]^=1;
            else xr[rs][i]^=1;
            xr[rt][i]=0;
        }
    }
}

void build(int l,int r,int rt){
    int i;
    len[rt]=r-l+1;
    for(i=0;i<4;i++) cv[rt][i]=-1,xr[rt][i]=0;
    if(l==r){
        scanf("%d",&a);
        for(i=0;i<4;i++,a>>=1) sum[rt][i]=a&1;
        return;
    }
    int mid=middle;
    build(lson),build(rson);
    pushUp(rt);
}

void op_and(int rt,int c){
    for(int i=0,j;i<4;i++,c>>=1){
        j=c&1;
        if(j) continue;
        cv[rt][i]=0,xr[rt][i]=0;
        sum[rt][i]=0;
    }
}

void op_or(int rt,int c){
    for(int i=0,j;i<4;i++,c>>=1){
        j=c&1;
        if(!j) continue;
        cv[rt][i]=1,xr[rt][i]=0;
        sum[rt][i]=len[rt];
    }
}

void op_xor(int rt,int c){
    for(int i=0,j;i<4;i++,c>>=1){
        j=c&1;
        if(!j) continue;
        sum[rt][i]=len[rt]-sum[rt][i];
        if(cv[rt][i]!=-1) cv[rt][i]^=1;
        else xr[rt][i]^=1;
    }
}

void update(int l,int r,int rt,int L,int R,int c,int op){
    if(L<=l && r<=R){
        switch(op){
            case 1:op_and(rt,c);break;
            case 2:op_or(rt,c);break;
            case 3:op_xor(rt,c);break;
        }
        return;
    }
    pushDown(rt);
    int mid=middle;
    if(L<=mid) update(lson,L,R,c,op);
    if(mid<R) update(rson,L,R,c,op);
    pushUp(rt);
}

int query(int l,int r,int rt,int L,int R){
    int ret=0;
    if(L<=l && r<=R){
        for(int i=0,j=1;i<4;i++,j<<=1) if(sum[rt][i]){
            ret+=j*sum[rt][i];
        }
        return ret;
    }
    pushDown(rt);
    int mid=middle;
    if(L<=mid) ret+=query(lson,L,R);
    if(mid<

补充：软件开发 , Vc ,