全部定义为ll
就AC了。。妈蛋。
区间更新
#include <cstdio> #include <iostream> #include <cstring> using namespace std; #define Lson l,m,rt<<1 #define Rson m+1,r,rt<<1|1 typedef long long ll; int const MAXN = 100010; struct Tree{ int l,r; ll v,add; }tree[MAXN<<2]; inline int Max(int a,int b){ return a>b?a:b; } inline void PushUp(int rt){ tree[rt].v = tree[rt<<1].v + tree[rt<<1|1].v; } inline void PushDown(int rt,int m){ if(tree[rt].add){ tree[rt<<1].add += tree[rt].add; tree[rt<<1|1].add += tree[rt].add; tree[rt<<1|1].v += tree[rt].add * (m>>1); tree[rt<<1].v += tree[rt].add * (m - (m>>1)); tree[rt].add = 0; } } void Build(int l,int r,int rt){ tree[rt].add = 0; if(l == r){ scanf("%lld",&tree[rt].v); return ; } int m = (l + r)>>1; Build(Lson); Build(Rson); PushUp(rt); } void Update(int L,int R,ll c,int l,int r,int rt){ if(L <= l && r <= R){ tree[rt].add += c; tree[rt].v += c * (r - l + 1); return ; } PushDown(rt,r - l + 1); int m = (l + r)>>1; if(L <= m) Update(L,R,c,Lson); if(R > m) Update(L,R,c,Rson); PushUp(rt); } ll Query(int L,int R,int l,int r,int rt){ if(L <= l && r <= R){ return tree[rt].v; } PushDown(rt,r - l + 1); int m = (l + r)>>1; ll ret = 0; if(L <= m) ret += Query(L,R,Lson); if(R > m) ret += Query(L,R,Rson); return ret; } int main(){ int n,q; while(~scanf("%d%d",&n,&q)){ Build(1,n,1); for(int i = 1;i <= q;i++){ char str[3]; scanf("%s",str); if(str[0] == 'Q'){ int x,y; scanf("%d%d",&x,&y); printf("%lld\n",Query(x,y,1,n,1)); } else{ int x,y; ll c; scanf("%d%d%lld",&x,&y,&c); Update(x,y,c,1,n,1); } } } return 0; }