codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <bits/stdc++.h> using namespace std; typedef long long int i64; #define M 100009 i64 ara[M]; i64 tree[3*M]={0}; i64 lazy[3*M]={0}; void built_tree(i64 node, i64 a, i64 b) { if (a>b) return; if (a==b){ tree[node]=ara[a]; return; } built_tree(2*node, a, (a+b)/2); built_tree(2*node+1, 1+(a+b)/2, b); tree[node]=tree[2*node]+tree[2*node+1]; } void update_tree(i64 node, i64 a, i64 b, i64 i, i64 j, i64 value) { if (lazy[node]!=0){ tree[node]+=(b-a+1)*lazy[node]; if (a!=b){ lazy[2*node]+=lazy[node]; lazy[2*node+1]+=lazy[node]; } lazy[node]=0; } if (a>=i && b<=j){ tree[node]+=(b-a+1)*value; if (a!=b){ lazy[2*node]+=value; lazy[2*node+1]+=value; } return; } if (a>b || a>j || b<i) return; int mid=(a+b)/2; update_tree(2*node, a, mid, i, j, value); update_tree(2*node+1, mid+1, b, i, j, value); tree[node]=tree[2*node]+tree[2*node+1]; } int query_tree(i64 node, i64 a, i64 b, i64 i, i64 j) { if (lazy[node]!=0){ tree[node]+=(b-a+1)*lazy[node]; if (a!=b){ lazy[2*node]+=lazy[node]; lazy[2*node+1]+=lazy[node]; } lazy[node]=0; } if (a>=i && b<=j) return tree[node]; if (a>b || a>j || b<i) return 0; int mid=(a+b)/2; i64 q1=query_tree(2*node, a, mid, i, j); i64 q2=query_tree(2*node+1, mid+1, b, i, j); return q1+q2; } int main () { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); i64 T, n, c, i, j, ck, p, q, v, mx; scanf ("%lld", &T); while (T--){ scanf ("%lld%lld", &n, &c); memset(ara, 0, n); memset(lazy, 0, 3*n); built_tree(1, 0, n-1); for (i=0; i<c; i++){ scanf("%lld", &ck); if (ck==0){ scanf ("%lld%lld%lld", &p, &q, &v); update_tree(1, 0, n-1, p-1, q-1, v); } else { scanf ("%lld%lld", &p, &q); mx=query_tree(1, 0, n-1, p-1, q-1); printf ("%lld\n", mx); } } } return 0; }
Private
[
?
]
Run code
Submit