题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3212
题意：序列区间加，区间求和。
BZOJ 居然有这种裸题... 然而被英语杀，WA 了一发...
HINT 的意思是可能超过 32-bit int... 理解成了保证用 int 就行...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[N]; char opt[5]; ll sum[N<<2]; int add[N<<2],L,R; void pushup(int x) {sum[x]=sum[x<<1]+sum[x<<1|1];} void pushdown(int x,int l,int r) { if(add[x]) { int mid=(l+r)>>1; add[x<<1]+=add[x],add[x<<1|1]+=add[x]; sum[x<<1]+=add[x]*(mid-l+1); sum[x<<1|1]+=add[x]*(r-mid); add[x]=0; } } void build(int x,int l,int r) { if(l==r) { sum[x]=a[l]; return ; } int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); pushup(x); } void updata(int x,int l,int r,int val) { if(l>=L&&r<=R) { add[x]+=val; sum[x]+=(r-l+1)*val; return ; } pushdown(x,l,r); int mid=(l+r)>>1; if(L<=mid)updata(x<<1,l,mid,val); if(R>mid)updata(x<<1|1,mid+1,r,val); pushup(x); } ll query(int x,int l,int r) { if(l>=L&&r<=R) return sum[x]; pushdown(x,l,r); int mid=(l+r)>>1; ll ret=0; if(L<=mid)ret+=query(x<<1,l,mid); if(R>mid)ret+=query(x<<1|1,mid+1,r); return ret; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%s",opt); L=read(),R=read(); if(opt[0]=='Q') printf("%lld\n",query(1,1,n)); else { int x=read(); updata(1,1,n,x); } } } |
Comments | NOTHING