fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. struct node {
  7.   int from, to;
  8.   long long value, lazy;
  9.   node *left, *right;
  10.   node() {
  11.     from=1;
  12.     to=1e5;
  13.     value=0;
  14.     lazy=0;
  15.     left=NULL;
  16.     right=NULL;
  17.   }
  18.   void extend() {
  19.     if(left==NULL) {
  20.       left=new node();
  21.       right=new node();
  22.       left->from=from;
  23.       left->to=(from+to)>>1;
  24.       right->from=((from+to)>>1)+1;
  25.       right->to=to;
  26.     }
  27.   }
  28. };
  29.  
  30. node *root;
  31. int tests,n,queries;
  32.  
  33. void update_tree(node *curr, int left, int right, long long value) {
  34.   if(curr->lazy) {
  35.     curr->value+=(curr->to-curr->from+1)*curr->lazy;
  36.     if(curr->from!=curr->to) {
  37.       curr->extend();
  38.       curr->left->lazy+=curr->lazy;
  39.       curr->right->lazy+=curr->lazy;
  40.     }
  41.     curr->lazy=0;
  42.   }
  43.   if((curr->from)>(curr->to) || (curr->from)>right || (curr->to)<left) return;
  44.   if(curr->from>=left && curr->to<=right) {
  45.     curr->value+=(curr->to-curr->from+1)*value;
  46.     if(curr->from!=curr->to) {
  47.       curr->extend();
  48.       curr->left->lazy+=value;
  49.       curr->right->lazy+=value;
  50.     }
  51.     return;
  52.   }
  53.   curr->extend();
  54.   update_tree(curr->left,left,right,value);
  55.   update_tree(curr->right,left,right,value);
  56.   curr->value=curr->left->value + curr->right->value;
  57. }
  58.  
  59. long long query_tree(node *curr, int left, int right) {
  60.   if((curr->from)>(curr->to) || (curr->from)>right || (curr->to)<left) return 0;
  61.   if(curr->lazy) {
  62.     curr->value+=(curr->to-curr->from+1)*curr->lazy;
  63.     curr->extend();
  64.     curr->left->lazy+=curr->lazy;
  65.     curr->right->lazy+=curr->lazy;
  66.     curr->lazy=0;
  67.   }
  68.   if(curr->from>=left && curr->to<=right) return curr->value;
  69.   long long q1,q2;
  70.   curr->extend();
  71.   q1=query_tree(curr->left,left,right);
  72.   q2=query_tree(curr->right,left,right);
  73.   return q1+q2;
  74. }
  75.  
  76. int main() {
  77.   //ios_base::sync_with_stdio(false);
  78.   //cin.tie(NULL);
  79.   //freopen("test.txt","r",stdin);
  80.   //freopen("taskname.in","r",stdin);
  81.   //freopen("taskname.out","w",stdout);
  82.   int type,p,q;
  83.   long long v;
  84.   int i;
  85.  
  86.   scanf("%d", &tests);
  87.   while(tests--) {
  88.     root=new node();
  89.     scanf("%d %d", &n, &queries);
  90.     for(i=1;i<=queries;i++) {
  91.       scanf("%d", &type);
  92.       if(type==0) {
  93.         scanf("%d %d %lld", &p, &q, &v);
  94.         if(p>q) swap(p,q);
  95.         update_tree(root,p,q,v);
  96.       } 
  97.       else {
  98.         scanf("%d %d", &p, &q);
  99.         if(p>q) swap(p,q);
  100.         printf("%lld\n", query_tree(root,p,q));
  101.       }
  102.     }
  103.   }
  104.  
  105.   return 0;
  106. }
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hdI5aX
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!