POJ3468 A Simple Problem with Integers【线段树 成段更新+求和 lazy标志】

 

 用longlong替换__int64也成。

#define LL long long

输入输出用%lld

Problem: 3468		User: qq1203456195
Memory: 4284K		Time: 1579MS
Language: C		Result: Accepted

 

#include 
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 111111
#define INT __int64
INT sum[maxn<<2],lazy[maxn<<2];
INT ret;
void PullUp(int rt)
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int len)
{lazy[rt<<1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];sum[rt<<1]+=lazy[rt]*(len-(len>>1));sum[rt<<1|1]+=lazy[rt]*(len>>1);lazy[rt]=0;
}
void build(int l,int r,int rt)
{int m=(r+l)>>1;lazy[rt]=0;if(l==r){scanf("%I64d",&sum[rt]);return;}build(lson);build(rson);PullUp(rt);
}
void update(INT v,int L,int R,int l,int r,int rt)
{int m=(l+r)>>1;if(l>=L&&r<=R){sum[rt]+=(r-l+1)*v;lazy[rt]+=v;return;}if(lazy[rt]!=0)    PushDown(rt,r-l+1);if(L<=m)        update(v,L,R,lson);if(R>m)            update(v,L,R,rson);PullUp(rt);
}
void query(int L,int R,int l,int r,int rt)
{int m=(l+r)>>1;if(l>=L&&r<=R){ret+=sum[rt];return;}if(lazy[rt]!=0)    PushDown(rt,r-l+1);if(L<=m)        query(L,R,lson);if(R>m)            query(L,R,rson);    
}
int main()
{int n,q,L,R;INT v;char op[2];while (~scanf("%d%d",&n,&q)){build(1,n,1);while (q--){scanf("%s",op);if(op[0]=='C'){scanf("%d%d%I64d",&L,&R,&v);update(v,L,R,1,n,1);}if(op[0]=='Q'){ret=0;scanf("%d%d",&L,&R);query(L,R,1,n,1);printf("%I64d
",ret);}}}return 0;
}