fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #define M 1000000007
  8. #define sum(a,b) ((a)+(b))
  9.  
  10. #define gc getchar
  11. typedef long long int ll;
  12.  
  13. using namespace std;
  14.  
  15.  
  16. template<class T>
  17. class SegmentTree{
  18.  
  19.     ll *tree, *lazy;
  20.     int size;
  21.     //tree.resize(MAX);
  22.     //lazy.resize(MAX);
  23.     public:
  24.      SegmentTree(int N)
  25.      {
  26.           int x = (int)(ceil(log2(N)))+1;
  27.           size = 2*(int)pow(2,x);
  28.           tree = new ll[size];
  29.           lazy = new ll[size];
  30.           memset(tree,-1,sizeof(tree));
  31.           memset(lazy,0,sizeof(lazy));
  32.      }
  33.      void build_tree(int a, int b, int index, T *A) {
  34.  
  35.          //cout << "node: " << index << endl;
  36.  
  37.         if(a == b) {
  38.     	tree[index] = A[a];
  39. 		return;
  40.         }
  41.         int mid = (a+b)/2;
  42.         build_tree(a, mid, index*2+1, A);
  43.         build_tree(1+mid, b, index*2+2, A);
  44.  
  45.         tree[index] = sum(tree[index*2+1], tree[index*2+2]);
  46.        // cout << "value["<<index<<"] = " << tree[index] << endl;
  47.  
  48.     }
  49.  
  50.     int query_sum(int node, int a, int b, int i, int j) {
  51.  
  52.         //cout << "a = " << a << " b= " << b <<" i= " <<i << " j = " << j << endl;
  53.  
  54.         if(a > b || a > j || b < i) return 0;
  55.  
  56.         if(lazy[node] != 0) {
  57.             tree[node] += lazy[node];
  58.             tree[node] %= M;
  59.             if(a != b) {
  60.                 lazy[node*2+1] += lazy[node];
  61.                 lazy[node*2+2] += lazy[node];
  62.             }
  63.             lazy[node] = 0;
  64.         }
  65.  
  66.         if(a >= i && b <= j){
  67.            // cout << "now:  " << tree[node];
  68.             return tree[node];
  69.  
  70.         }
  71.  
  72.         int mid = (a+b)/2;
  73.  
  74.         int q1 = query_sum(node*2+1, a, mid, i, j);
  75.         int q2 = query_sum(node*2+2, 1+mid, b, i, j);
  76.  
  77.         int res = sum(q1,q2)%M;
  78.  
  79.         return res;
  80.     }
  81.  
  82.     void query_add_update(int node, int a, int b, int i, int j, int val) // 'val' is the difference here
  83.     {
  84.       //  cout << "NOW NODE: " << node << endl;
  85.         if(lazy[node] != 0)
  86.         {
  87.         // cout << "CHECK 1" << endl;
  88.         //tree[node] += lazy[node];
  89.  
  90.          //cout << "tree["<<node<<"] = " << tree[node] << endl;
  91. 		if(a!=b){
  92.             lazy[2*node+1] += lazy[node];
  93.             lazy[2*node+2] += lazy[node];
  94.            // cout << "lazy["<<2*node+1<<"] = " << lazy[node*2+1] << endl;
  95.             //cout << "lazy["<<2*node+2<<"] = " << lazy[node*2+2] << endl;
  96. 		}
  97.             lazy[node] = 0;
  98.         }
  99.  
  100.         if(a > b || a > j || b < i)
  101.             return;
  102.  
  103.         if(a >= i && b <= j)
  104.         {
  105.             //cout << "check 2" << endl;
  106.             //cout << "tree["<<node<<"] = " << tree[node] << endl;
  107.             tree[node] += val;
  108.              tree[node] %= M;
  109.             //cout << "tree["<<node<<"] = " << tree[node] << endl;
  110.  
  111.             if(a!=b)
  112.             {
  113.                 lazy[2*node+1] += val;
  114.                 lazy[2*node+2] += val;
  115.               //  cout << "lazy["<<2*node+1<<"] = " << lazy[node*2+1] << endl;
  116.                 //cout << "lazy["<<2*node+2<<"] = " << lazy[node*2+2] << endl;
  117.  
  118.             }
  119.             else
  120.             return;
  121.         }
  122.         int mid = (a+b)/2;
  123.         query_add_update(node*2+1, a, mid, i, j, val);
  124.         query_add_update(node*2+2, 1+mid, b, i, j, val);
  125.         tree[node] = sum(tree[node*2+1], tree[node*2+2]);
  126.     }
  127.  
  128.     void query_mul_update(int node, int a, int b, int i, int j, int val)
  129.     {
  130.         if(lazy[node]!=0)
  131.         {
  132.            // tree[node] *= lazy[node];
  133.             //tree[node] %= M;
  134.  
  135.             if(a!=b){
  136.                 lazy[2*node+1] += lazy[node];
  137.                 lazy[2*node+2] += lazy[node];
  138.             }
  139.             lazy[node] = 0;
  140.         }
  141.  
  142.         if(a > b || a > j || b < i)
  143.             return;
  144.  
  145.         if(a >= i && b <= j)
  146.         {
  147.             tree[node] *= val;
  148.             tree[node] %= M;
  149.  
  150.             if(a!=b)
  151.             {
  152.                 lazy[node*2+1] += val;
  153.                 lazy[node*2+2] += val;
  154.             }
  155.             else
  156.             return ;
  157.         }
  158.  
  159.         query_mul_update(node*2+1, a, (a+b)/2, i, j, val);
  160.         query_mul_update(node*2+2, 1+(a+b)/2, b, i, j, val);
  161.  
  162.         tree[node] = sum(tree[node*2+1], tree[node*2+2]);
  163.     }
  164.  
  165.     void query_setvalue(int node, int a, int b, int i, int j, int val)
  166.     {
  167.          if(lazy[node] != 0)
  168.         {
  169.         tree[node] += lazy[node];
  170.  
  171. 		if(a!=b){
  172.             lazy[2*node+1] += lazy[node];
  173.             lazy[2*node+2] += lazy[node];
  174. 		}
  175.             lazy[node] = 0;
  176.         }
  177.  
  178.         if(a > b || a > j || b < i)
  179.             return;
  180.  
  181.         if(a >= i && b <= j)
  182.         {
  183.             tree[node] = val;
  184.  
  185.             if(a!=b)
  186.             {
  187.                 lazy[2*node+1] = val;
  188.                 lazy[2*node+2] = val;
  189.             }
  190.         else
  191. 	  	return ;
  192.  
  193.         }
  194.  
  195.         query_setvalue(node*2+1, a, (a+b)/2, i, j, val);
  196.         query_setvalue(node*2+2, 1+(a+b)/2, b, i, j, val);
  197.  
  198.         tree[node] = sum(tree[node*2+1], tree[node*2+2]);
  199.     }
  200.  
  201.     //Additional Function
  202.     void print(int node, int a, int b)
  203.     {
  204.         if(a>b)
  205.             return;
  206.         if(a==b){
  207.             cout << tree[node] << "("<<node<<")"<<" " ;
  208.             return;
  209.         }
  210.         int mid = (a+b)/2;
  211.         print(2*node+1,a,mid);
  212.         print(2*node+2,mid+1,b);
  213.  
  214.     }
  215.  
  216.  
  217. };
  218. template <class T>
  219. class Input{
  220.  
  221.     public:
  222.    T read_int() {
  223.    char c = gc();
  224.    while(c<'0' || c>'9')
  225.     c = gc();
  226.    T ret = 0;
  227.  
  228.   while(c>='0' && c<='9') {
  229.     ret = 10 * ret + c - 48;
  230.     c = gc();
  231.     }
  232.   return ret;
  233. }
  234. };
  235.  
  236. int main(void)
  237. {
  238.     Input<ll>ip;
  239.     ll ans,x,y, v;
  240.     ll *ar, answer;
  241.     ll n = ip.read_int();
  242.     ll q = ip.read_int();
  243.     ar = (ll*)malloc(n*sizeof(ll));
  244.     for(int i=0;i<n;i++)
  245.         ar[i] = ip.read_int();
  246.  
  247.     SegmentTree<ll> st(n);
  248.     st.build_tree(0,n-1,0,ar);
  249.  
  250.     while(q--)
  251.     {
  252.         ans = ip.read_int();
  253.         x = ip.read_int();
  254.         y = ip.read_int();
  255.  
  256.         if(ans!=4)
  257.             v = ip.read_int();
  258.  
  259.         x -= 1;
  260.         y -= 1;
  261.  
  262.         if(ans==1)
  263.             st.query_add_update(0,0,n-1,x,y,v);
  264.         if(ans==2)
  265.             st.query_mul_update(0,0,n-1,x,y,v);
  266.         if(ans==3)
  267.             st.query_setvalue(0,0,n-1,x,y,v);
  268.         if(ans==4){
  269.             answer = (ll)st.query_sum(0,0,n-1,x,y);
  270.             cout << answer << endl;
  271.         }
  272.  
  273.        // st.print(0,0,n-1);
  274.         //cout << endl;
  275.  
  276.     }
  277.  
  278.  
  279.     return 0;
  280. }
  281.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
4 4
1 2 3 4
4 1 4
1 1 3 10
2 2 4 2
4 1 4
stdout
copy 
10
69
https://ideone.com/JBAB5E
language:
C++14 (gcc 8.3)
created:
8 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!