fzu 2105 Digits Count - windows编程基础

TOP

fzu 2105 Digits Count (一)

2014-11-23 19:09:39 【大中小】浏览:629次

Tags：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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 T _max(T x,T y){return x>y x:y;}
template T _min(T x,T y){return x template T _abs(T x){return (x < 0) -x:x;}
template T _mod(T x,T y){return (x > 0) x%y:((x%y)+y)%y;}
template void _swap(T &x,T &y){T t=x;x=y;y=t;}
template void getmax(T& x,T y){x=(y > x) y:x;}
template void getmin(T& x,T y){x=(x<0 || y 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 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 return ret;
}

void run(){
int i,j;
scanf("%d%d",&n,&m);
build(0,n-1,1);
char opr[5];
int opn,l,r;
while(m--){
scanf("%s",opr);
if(opr[0]=='S'){
scanf("%d%d",&l,&r);
printf("%d\n",query(0,n-1,1,l,r));
}else{
scanf("%d%d%d",&opn,&l,&r);

首页上一页 1 2 3 下一页尾页 1/3/3
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：VC++面向对象的static	下一篇：VC++中面向过程的Static