题号：P3372
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 | #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cassert> #include<vector> #include<list> #include<stack> #include<queue> struct node{ long long value; long long lazymark; }segment_tree[400005]; void build(int root, long long * arr, int start, int end){ segment_tree[root].lazymark = 0; if (start == end){ segment_tree[root].value = arr[start]; return; } int mid = (start + end) / 2; build(root * 2 + 1, arr, start, mid); build(root * 2 + 2, arr, mid + 1, end); segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value; } void pushdown(int root,int start,int end){ if (segment_tree[root].lazymark == 0)return; int mid = (start + end) / 2; segment_tree[root * 2 + 1].lazymark += segment_tree[root].lazymark; segment_tree[root * 2 + 2].lazymark += segment_tree[root].lazymark; segment_tree[root * 2 + 1].value += segment_tree[root].lazymark*(mid - start + 1); segment_tree[root * 2 + 2].value += segment_tree[root].lazymark*(end - mid); segment_tree[root].lazymark = 0; } long long query(int root, int cstart, int cend, int qstart, int qend){ if (qstart > cend || qend < cstart)return 0; if (qstart <= cstart&&cend <= qend)return segment_tree[root].value; pushdown(root,cstart,cend); int cmid = (cstart + cend) / 2; return query(root * 2 + 1, cstart, cmid, qstart, qend) + query(root * 2 + 2, cmid + 1, cend, qstart, qend); } void update(int root, int cstart, int cend, int ustart, int uend, long long addvalue){ if (cend < ustart || uend < cstart)return; if (ustart <= cstart&&cend <= uend){ segment_tree[root].value += addvalue*(cend - cstart + 1); segment_tree[root].lazymark += addvalue; return; } pushdown(root,cstart,cend); int cmid = (cstart + cend) / 2; update(root * 2 + 1, cstart, cmid, ustart, uend, addvalue); update(root * 2 + 2, cmid + 1, cend, ustart, uend, addvalue); segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value; } using namespace std; int n, m; long long arr[100005]; int main(){ ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++){ cin >> arr[i]; } build(1, arr, 1, n); while (m--){ int op; cin >> op; if (op == 1){ int x, y; long long z; cin >> x >> y >> z; update(1, 1, n, x, y, z); } else{//op==2 int x, y; cin >> x >> y; cout << query(1, 1, n, x, y) << endl; } } } |
zcysky标程：
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 | #include<bits/stdc++.h> const int N=100005; typedef long long ll; using namespace std; int a[N],n,m; inline ll read(){ ll f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } ll sumv[N<<2],addv[N<<2]; #define lson (o<<1) #define rson (o<<1|1) inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];} inline void pushdown(int o,int l,int r){ if(!addv[o])return; ll tag=addv[o];addv[o]=0;int mid=(l+r)>>1; addv[lson]+=tag;addv[rson]+=tag; sumv[lson]+=tag*1LL*(mid-l+1);sumv[rson]+=tag*1LL*(r-mid); } inline void build(int o,int l,int r){ if(l==r){sumv[o]=a[l];return;} int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(o); } inline void optadd(int o,int l,int r,int ql,int qr,ll v){ if(ql<=l&&r<=qr){sumv[o]+=v*1LL*(r-l+1);addv[o]+=v;return;} int mid=(l+r)>>1;pushdown(o,l,r); if(ql<=mid)optadd(lson,l,mid,ql,qr,v); if(qr>mid)optadd(rson,mid+1,r,ql,qr,v); pushup(o); } inline ll querysum(int o,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr)return sumv[o]; pushdown(o,l,r); int mid=(l+r)>>1;ll ans=0; if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr); if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr); return ans; } int main(){ n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); build(1,1,n); while(m--){ int opt=read(),l=read(),r=read(); if(opt==1){ ll k=read();optadd(1,1,n,l,r,k); } else printf("%lld\n",querysum(1,1,n,l,r)); } } |
20180816更新：
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 | #include<iostream> using namespace std; struct segmentTree{ typedef long long ll; const static ll MAX=100000; ll v[4*MAX],m[4*MAX]; inline static ll lson(ll r){return r*2+1;} inline static ll rson(ll r){return r*2+2;} void build(ll r,ll * a,ll s,ll e){ m[r]=0; if(s==e){v[r]=a[s];return;} ll md=(s+e)>>1; build(lson(r),a,s,md); build(rson(r),a,md+1,e); v[r]=v[lson(r)]+v[rson(r)]; } void pushDown(ll r,ll s,ll e){ if(m[r]==0)return; ll md=(s+e)>>1; m[lson(r)]+=m[r]; m[rson(r)]+=m[r]; v[lson(r)]+=m[r]*(md-s+1); v[rson(r)]+=m[r]*(e-md); m[r]=0; } ll query(ll r,ll cs, ll ce,ll qs,ll qe){ if(qe<cs||ce<qs)return 0; if(qs<=cs&&ce<=qe)return v[r]; pushDown(r,cs,ce); ll cmd=(cs+ce)/2; return query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe); } void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv){ if(ce<us||ue<cs)return; if(us<=cs&&ce<=ue){v[r]+=addv*(ce-cs+1);m[r]+=addv;return;} pushDown(r,cs,ce); ll cmd=(cs+ce)>>1; update(lson(r),cs,cmd,us,ue,addv); update(rson(r),cmd+1,ce,us,ue,addv); v[r]=v[lson(r)]+v[rson(r)]; } }ST; typedef long long ll; ll n,m; ll a[100005]; int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; ST.build(1,a,1,n); for(int i=1;i<=m;i++){ int op,x,y,k; cin>>op; if(op==1){ cin>>x>>y>>k; ST.update(1,1,n,x,y,k); }else{ cin>>x>>y; cout<<ST.query(1,1,n,x,y)<<endl; } } } |