fork download 
  1. #include <bits/stdc++.h>
  2. #define loop(a,b) for(int i=a;i<b;i++)
  3. #define loop2(a,b) for(int j=a;j<b;j++)
  4. #define revloop(a,b) for(int k=a;k>=b;k--)
  5. #define mod 1000000000
  6. #define lli long long int
  7. using namespace std;
  8.  
  9.  
  10. struct node{
  11. int count[40];
  12. };
  13.  
  14. lli factorial[40];
  15.  
  16. void BuildSegTree(int arr[], node seg[], int lazy[], int low, int high, int pos)
  17. {
  18.     loop(1,40)
  19.     {
  20.         seg[pos].count[i] = 0;
  21.     }
  22.  
  23.     if(low == high)
  24.     {
  25.  
  26.         if(arr[low]<40)
  27.             seg[pos].count[arr[low]]=1;
  28.  
  29.     }
  30.     else
  31.     {
  32.         int mid = (low+high)/2;
  33.         BuildSegTree(arr,seg,lazy,low,mid,2*pos+1);
  34.         BuildSegTree(arr,seg,lazy,mid+1,high,2*pos+2);
  35.         loop(1,40)
  36.         {
  37.             seg[pos].count[i] = seg[2*pos+1].count[i] + seg[2*pos+2].count[i];
  38.         }
  39.  
  40.     }
  41.  
  42. }
  43.  
  44. void UpdateSegTree(int arr[], node seg[], int lazy[], int low, int high, int pos, int l, int r, int val, int choice)
  45. {
  46.     if(lazy[pos]!=0)
  47.     {
  48.         revloop(39,1)
  49.         {
  50.             if(k+lazy[pos]<40)
  51.             {
  52.                 seg[pos].count[k+lazy[pos]] = seg[pos].count[k];
  53.             }
  54.             seg[pos].count[k] = 0;
  55.         }
  56.         if(low!=high)
  57.         {
  58.             lazy[2*pos+1] = lazy[pos];
  59.             lazy[2*pos+2] = lazy[pos];
  60.         }
  61.         lazy[pos] = 0;
  62.     }
  63.  
  64.     if(l>high || r<low)
  65.         return;
  66.     if(l<= low && r>=high)
  67.     {
  68.         if(choice==3)
  69.         {
  70.                 loop(1,40)
  71.                 {
  72.                     if(i==val)
  73.                         seg[pos].count[val] = 1;
  74.                     else
  75.                         seg[pos].count[i] = 0;
  76.                 }
  77.  
  78.         }
  79.         else
  80.         {
  81.             revloop(39,2)
  82.             {
  83.                 seg[pos].count[k] = seg[pos].count[k-1];
  84.             }
  85.             seg[pos].count[1] = 0 ;
  86.         }
  87.  
  88.         if(low!=high)
  89.         {
  90.             lazy[2*pos+1] += val;
  91.             lazy[2*pos+2] += val;
  92.         }
  93.  
  94.         return;
  95.     }
  96.  
  97.     int mid = (low+high)/2;
  98.     UpdateSegTree(arr,seg,lazy,low,mid,2*pos+1,l,r,val,choice);
  99.     UpdateSegTree(arr,seg,lazy,mid+1,high,2*pos+2,l,r,val,choice);
  100.     loop(1,40)
  101.     {
  102.         seg[pos].count[i] = seg[2*pos+1].count[i] + seg[2*pos+2].count[i];
  103.     }
  104.  
  105. }
  106.  
  107.  
  108. lli RangeQuerySegTree(int arr[], node seg[], int lazy[], int low, int high, int pos, int l, int r)
  109. {
  110.     if(lazy[pos]!=0)
  111.     {
  112.         revloop(39,1)
  113.         {
  114.             if(k+lazy[pos]<40)
  115.             {
  116.                 seg[pos].count[k+lazy[pos]] = seg[pos].count[k];
  117.             }
  118.             seg[pos].count[k] = 0;
  119.         }
  120.         if(low!=high)
  121.         {
  122.             lazy[2*pos+1] = lazy[pos];
  123.             lazy[2*pos+2] = lazy[pos];
  124.         }
  125.         lazy[pos] = 0;
  126.     }
  127.     if(l>high || r<low)
  128.     return 0;
  129.     if(l<= low && r>=high)
  130.     {
  131.         lli sum = 0;
  132.  
  133.         loop(1,40)
  134.         {
  135.  
  136.             sum += (seg[pos].count[i]*factorial[i]) % mod;
  137.         }
  138.  
  139.         return sum;
  140.     }
  141.     int mid = (low+high)/2;
  142.     return RangeQuerySegTree(arr,seg,lazy,low,mid,2*pos+1,l,r) + RangeQuerySegTree(arr,seg,lazy,mid+1,high,2*pos+2,l,r);
  143.  
  144.  
  145. }
  146.  
  147.  
  148.  
  149. int main()
  150. {
  151.     int n,m;
  152.     cin>>n>>m;
  153.  
  154.     factorial[0] = factorial[1] = 1;
  155.     loop(2,40)
  156.         factorial[i] = (factorial[i-1]*i )% mod;
  157.  
  158.     int n2=n,n1 = n, exp=0;
  159.     while(n1)
  160.     {
  161.         n1/=2;
  162.         exp++;
  163.     }
  164.     exp--;
  165.  
  166.     int seg_size;
  167.  
  168.     if(pow(2,exp)  == n)
  169.             seg_size = 2*n-1;
  170.     else
  171.         seg_size = 2*pow(2,exp+1) - 1;
  172.  
  173.  
  174.     int arr[n];
  175.     loop(0,n)
  176.         cin>>arr[i];
  177.  
  178.     node seg[seg_size];
  179.     int lazy[seg_size];
  180.     int low = 0, high = n-1, pos = 0;
  181.      loop(0,seg_size)
  182.     {
  183.  
  184.         loop2(1,40)
  185.         {
  186.             seg[i].count[j]=0;
  187.         }
  188.     }
  189.     BuildSegTree(arr,seg,lazy,low,high,pos);
  190.  
  191.     memset(lazy,0,sizeof(lazy));
  192.  
  193.     loop(0,m)
  194.     {
  195.  
  196.         int n1, l, r;
  197.         cin>>n1>>l>>r;
  198.         l--;
  199.  
  200.         if(n1 == 1)
  201.         {
  202.             r--;
  203.             UpdateSegTree(arr,seg,lazy,0,n-1,0,l,r,1,1);
  204.  
  205.         }
  206.         else if(n1==2)
  207.         {
  208.             r--;
  209.             cout<<RangeQuerySegTree(arr,seg,lazy,0,n-1,0,l,r)<<"\n";
  210.         }
  211.         else
  212.             {
  213.             UpdateSegTree(arr,seg,lazy,0,n-1,0,l,l,r,3);
  214.  
  215.             }
  216.     }
  217. }
  218.  
Runtime error #stdin #stdout 0s 4512KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/EGxBdK
language:
C++14 (clang 8.0)
created:
7 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!