Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstring>
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <stack>
- #include <bitset>
- #include <algorithm>
- #include <functional>
- #include <numeric>
- #include <utility>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <ctime>
- #include <memory.h>
- #include <cassert>
- typedef long long ll;
- using namespace std;
- const int MAX_N = 10000;
- ll value[40000];
- ll delta[40000];
- ll default_delta = -1; // should be impossilbe value;
- void build_tree(int a[], int root, int tl, int tr){
- if(tl == tr){
- value[root] = a[tl];
- }else{
- int mid = (tl+tr)>>1;
- build_tree(a, root*2+1, tl, mid);
- build_tree(a, root*2+2, mid+1, tr);
- value[root] = value[root*2+1]+value[root*2+2];
- delta[root] = default_delta;
- }
- }
- ll acc(ll value, ll deltas, ll length) {
- if(deltas != default_delta)
- return value + deltas * length;
- return value;
- }
- ll joinDelta(ll was, ll deltas) {
- if(deltas != default_delta) //
- return deltas;
- return was;
- }
- ll joinValue(ll left, ll right) {
- return left + right;
- }
- void pushDown(int root, int left, int middle, int right) {
- value[2 * root + 1] = acc(value[2 * root + 1], delta[root], middle - left + 1);
- value[2 * root + 2] = acc(value[2 * root + 2], delta[root], right - middle);
- delta[2 * root + 1] = joinDelta(delta[2 * root + 1], delta[root]);
- delta[2 * root + 2] = joinDelta(delta[2 * root + 2], delta[root]);
- delta[root] = default_delta;
- }
- void updateFull(int root, int left, int right, int from, int to, ll deltas) {
- value[root] = acc(value[root], deltas, right - left + 1);
- delta[root] = joinDelta(delta[root], deltas);
- }
- void updatePreProcess(int root, int left, int right, int from, int to, ll deltas, int middle) {
- pushDown(root, left, middle, right);
- }
- void updatePostProcess(int root, int left, int right, int from, int to, ll deltas, int middle) {
- value[root] = joinValue(value[2 * root + 1], value[2 * root + 2]);
- }
- void update(int root, int left, int right, int from, int to, ll deltas) {
- if (left > to || right < from)
- return;
- if (left >= from && right <= to) {
- updateFull(root, left, right, from, to, deltas);
- return;
- }
- int middle = (left + right) >> 1;
- updatePreProcess(root, left, right, from, to, deltas, middle);
- update(2 * root + 1, left, middle, from, to, deltas);
- update(2 * root + 2, middle + 1, right, from, to, deltas);
- updatePostProcess(root, left, right, from, to, deltas, middle);
- }
- void queryPreProcess(int root, int left, int right, int from, int to, int middle) {
- pushDown(root, left, middle, right);
- }
- ll queryPostProcess(int root, int left, int right, int from, int to, int middle, ll leftResult, ll rightResult) {
- return joinValue(leftResult, rightResult);
- }
- ll queryFull(int root, int left, int right, int from, int to) {
- return value[root];
- }
- ll query(int root, int left, int right, int from, int to) {
- if (left > to || right < from)
- return 0;
- if (left >= from && right <= to)
- return queryFull(root, left, right, from, to);
- int middle = (left + right) >> 1;
- queryPreProcess(root, left, right, from, to, middle);
- ll leftResult = query(2 * root + 1, left, middle, from, to);
- ll rightResult = query(2 * root + 2, middle + 1, right, from, to);
- return queryPostProcess(root, left, right, from, to, middle, leftResult, rightResult);
- }
- int main(){
- int n;
- scanf("%d", &n);
- int a[n];
- for(int i = 0; i < n; i++) a[i] = 0;
- build_tree(a, 1, 0, n-1);
- int m;
- scanf("%d", &m);
- for(int i = 0; i < m; i++){
- int type;
- scanf("%d", &type); // 1 - sum [l, r], 2 - update [l, r] = x;
- if(type == 1){
- int l, r;
- scanf("%d %d", &l, &r);
- printf("%d \n", query(1, 0, n-1, l-1, r-1));
- }
- else{
- int l, r;
- ll x;
- scanf("%d %d %lld", &l, &r, &x);
- update(1, 0, n-1, l-1, r-1, x);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment