fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. #define ll long long
  5. class node
  6. {
  7. public:
  8.         int left_r,right_r;
  9.         ll sum,count;
  10.         node *left,*right;
  11.         node() {
  12.                 left_r=right_r=0;
  13.                 sum=count=0;
  14.                 left=right=NULL;
  15.         }
  16. };
  17. void maketree(int lower,int higher,node *current)
  18. {
  19.         current->left_r=lower;
  20.         current->right_r=higher;
  21.         if(lower!=higher) {
  22.                 node *leftt=new node();
  23.                 node *rightt=new node();
  24.                 current->left=leftt;
  25.                 current->right=rightt;
  26.                 maketree(lower,(lower+higher)/2,current->left);
  27.                 maketree((lower+higher)/2+1,higher,current->right);
  28.         }
  29.        // cout<<"heloo\n";
  30. }
  31. void add_up(node *current,node *left,node *right)
  32. {
  33.         current->sum=(current->left->sum+current->left->count*(current->left->right_r - current->left->left_r+1)) ;
  34.         current->sum=current->sum + (current->right->sum+current->right->count*(current->right->right_r-current->right->left_r+1));
  35. }
  36. ll countRMQ(int low,int high,node *current)
  37. {
  38.         if(current->count!=0) {
  39.                 current->sum+=(current->right_r-current->left_r+1)*current->count;
  40.                 if(current->left!=NULL) {
  41.                         current->left->count+=current->count;
  42.                         current->right->count+=current->count;
  43.                 }
  44.                 current->count=0;
  45.         }
  46.         if(low==current->left_r&&high==current->right_r) {
  47.                 return current->sum+current->count*(current->right_r-current->left_r+1);
  48.         }
  49.         int mid=(current->left_r+current->right_r)/2;
  50.         if(low>mid) {
  51.                 return countRMQ(low,high,current->right);
  52.         } else if(mid>=high) {
  53.                 return countRMQ(low,high,current->left);
  54.         } else {
  55.                 return (countRMQ(low,mid,current->left)+countRMQ(mid+1,high,current->right));
  56.         }
  57. }
  58. void updateRMQ(int low,int high,node *current,int add)
  59. {
  60.         if(current->count!=0) {
  61.                 current->sum=current->sum+(current->right_r-current->left_r+1)*current->count;
  62.                 if(current->left!=NULL) {
  63.                         current->left->count+=current->count;
  64.                         current->right->count+=current->count;
  65.                 }
  66.                 current->count=0;
  67.         }
  68.         if(low==current->left_r&&high==current->right_r) {
  69.                 current->sum=current->sum+(current->right_r-current->left_r+1)*add;
  70.                 current->count=0;
  71.                 if(current->left!=NULL) {
  72.                         current->left->count+=add;
  73.                         current->right->count+=add;
  74.                 }
  75.                 return ;
  76.         } else {
  77.                 int mid=(current->left_r+current->right_r)/2;
  78.                 if(low>mid) {
  79.                         updateRMQ(low,high,current->right,add);
  80.                 } else if(mid>=high) {
  81.                         updateRMQ(low,high,current->left,add);
  82.                 } else {
  83.                         updateRMQ(low,mid,current->left,add);
  84.                         updateRMQ(mid+1,high,current->right,add);
  85.                 }
  86.                 add_up(current,current->left,current->right);
  87.         }
  88. }
  89. int main()
  90. {
  91.         int tst;
  92.         scanf("%d",&tst);
  93.         while(tst--) {
  94.                 int N,Q;
  95.                 scanf("%d%d",&N,&Q);
  96.                 node *top=new node();
  97.                 maketree(0,N-1,top);
  98.          //       printf("pankaj\n");
  99.                 while(Q--) {
  100.                         int q,low,high,add;
  101.                         scanf("%d%d%d",&q,&low,&high);
  102.                         if(q) {
  103.                                 printf("%lld\n",countRMQ(low-1,high-1,top));
  104.                         } else {
  105.                                 scanf("%d",&add);
  106.                                 updateRMQ(low-1,high-1,top,add);
  107.                         }
  108.                 }
  109.         }
  110.         return 0;
  111. }
  112.  
Success #stdin #stdout 0s 2988KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
508
https://ideone.com/0IICRF
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

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!