fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6. " when you are not practicing someone else is ,
  7.  and the day u meet them u will lose "
  8.  
  9. */
  10. #include<bits/stdc++.h>
  11. #include<stdio.h>
  12. using namespace std;
  13.  
  14. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15. #define MAX 300050
  16.  
  17. #define ll long long
  18. #define ld long double
  19. #define lli long long int
  20.  
  21. #define pb push_back
  22. #define INF 1000000000000
  23. #define mod 1000000007
  24.  
  25. // trignometric function always give value in Radians only
  26. #define PI acos(-1) //3.1415926535897932384626433832795028
  27. #define dsin(degree) sin(degree*(PI/180.0))
  28. #define dcos(degree) cos(degree*(PI/180.0))
  29. #define dtan(degree) tan(degree*(PI/180.0))
  30.  
  31. #define rsin(radian) sin(radian)
  32. #define rcos(radian) cos(radian)
  33. #define rtan(radian) tan(radian)
  34.  
  35. #define mem0(a) memset(a,0,sizeof(a))
  36. #define mem1(a) memset(a,-1,sizeof(a))
  37. #define memf(a) memset(a,false,sizeof(a))
  38.  
  39. #define loop(i,n)  for (lli i = 0; i < n; i++)
  40. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  41.  
  42. #define all(v) v.begin(),v.end()
  43. #define rall(v) v.rbegin(),v.rend()
  44. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  45. #define sz(x) int(x.size())
  46. #define F first
  47. #define S second
  48.  
  49. #define mii map<lli,lli>
  50.  
  51. #define pii pair<lli,lli>
  52.  
  53. #define vi vector<lli>
  54. #define vvi vector<vi>
  55. #define vpi vector<pii>
  56. #define vbool vector<bool>
  57.  
  58. #define seti set<lli>
  59.  
  60. #define gcd(a,b) __gcd((a),(b))
  61. #define lcm(a,b) (a/gcd(a,b))*b
  62. #define abs(x) ((x < 0)?-(x):x)
  63.  
  64. #define endl '\n'
  65.  
  66. template <typename Head>
  67. void print(Head&& head)
  68. {
  69.     cout<<head<<endl;
  70. }
  71. template <typename Head, typename... Tail>
  72. void print(Head&& head, Tail... tail)
  73. {
  74.     cout<<head<<" ";
  75.     print(tail...);
  76. }
  77.  
  78. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  79. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  80.  
  81. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  82. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  83.  
  84. #define FD(N) fixed<<setprecision(N)
  85.  
  86. #define deb(x) cout<<#x<<" "<<x<<endl;
  87.  
  88. /*
  89. 1D vector -  vi dp(n,value);
  90. 2D vector -  vvi dp(n,vi(n,value));
  91. */
  92.  
  93. // chandan1,2
  94. void chandan1(){int y=1;return;}
  95. void chandan2(){
  96.         loop(i,10){
  97.         lli x=1;
  98.     }
  99.     return(chandan1());
  100. }
  101.  
  102. //---------------------------------------------------SQRT_DECOMPO-------------------------------------------------------
  103.  
  104. lli n , a[MAX];
  105. vi block[600];
  106. lli blk_sz;
  107.  
  108. // clear all data
  109. void clear()
  110. {
  111.     mem0(a);
  112.     loop(i,600)
  113.         block[i].clear();
  114. }
  115.  
  116. // preprocess array to sqrt decomposition
  117. void preprocess(lli n)
  118. {
  119.     blk_sz = sqrt(n);
  120.  
  121.     lli blk_ind = -1;
  122.  
  123.     loop(i,n)
  124.     {
  125.         if(i % blk_sz == 0)
  126.             blk_ind++;
  127.  
  128.         block[blk_ind].pb(a[i]); //push elements of sqrt size each 
  129.     }
  130.  
  131.     loop(i,blk_sz+1)
  132.     {
  133.         sort(all(block[i]));
  134.     }
  135. }
  136.  
  137.  
  138. lli binarySearchCount(vi &arr, lli  key) 
  139. { 
  140.     lli left = 0; 
  141.     lli right = sz(arr) - 1; 
  142.  
  143.     lli count = 0; 
  144.  
  145.     while (left <= right) { 
  146.         lli mid = (right + left) / 2; 
  147.  
  148.         // Check if middle element is 
  149.         // less than or equal to key 
  150.         if (arr[mid] <= key) { 
  151.  
  152.             // At least (mid + 1) elements are there 
  153.             // whose values are less than 
  154.             // or equal to key 
  155.             count = mid + 1; 
  156.             left = mid + 1; 
  157.         } 
  158.  
  159.         // If key is smaller, ignore right half 
  160.         else
  161.             right = mid - 1; 
  162.     } 
  163.  
  164.     return count; 
  165. } 
  166.  
  167. // query to count total values from l to r which have greater value then or equal to  K
  168. lli query(lli l , lli r , lli k)
  169. {
  170.     lli left_block = l/blk_sz;
  171.  
  172.     lli right_block = r/blk_sz;
  173.  
  174.     lli cnt=0;
  175.  
  176.     if(left_block == right_block)
  177.     {
  178.         for(lli i=l;i<=r;i++)
  179.             cnt +=  (a[i]<=k);
  180.     }
  181.     else
  182.     {
  183.         for(lli i=l;i<blk_sz*(left_block+1);i++) // traversing first block in range 
  184.             cnt +=  (a[i]<=k);
  185.  
  186.         for(lli i=left_block+1;i<right_block;i++) // traversing completely overlapped blocks in range 
  187.         {
  188.  
  189.             cnt += binarySearchCount(block[i],k); //count how many elements in array which are less than equal to k
  190.         }
  191.  
  192.         for(lli i=blk_sz*right_block;i<=r;i++) // traversing last block in range 
  193.             cnt +=  (a[i]<=k);
  194.     }
  195.  
  196.     return cnt;
  197. }
  198.  
  199.  
  200.  
  201.  
  202. void change_val_binary_search(vi &vc, lli crval , lli val)
  203. {
  204.     lli l=0;
  205.     lli r = sz(vc)-1;
  206.     while(l<r)
  207.     {
  208.         lli mid = (l+r)/2;
  209.         if(vc[mid] == crval)
  210.         {
  211.             vc[mid] = val;
  212.             return ;
  213.         }
  214.         else if(vc[mid]>crval)
  215.         {
  216.             r = mid-1;
  217.         }
  218.         else
  219.             l = mid+1;
  220.     }
  221. }
  222.  
  223. void update(lli ind , lli val)
  224. {
  225.     lli block_number = ind / blk_sz; 
  226.  
  227.     lli start = block_number*blk_sz;
  228.  
  229.     lli endi = (block_number+1)*blk_sz;
  230.  
  231.     change_val_binary_search(block[block_number] , a[ind] , val);
  232.  
  233.     a[ind] = val; 
  234.  
  235.     sort(all(block[block_number]));
  236.  
  237. }
  238.  
  239. //---------------------------------------------------SQRT_DECOMPO-------------------------------------------------------
  240.  
  241. // find count how many values less than or equal to k in L to R  :https://w...content-available-to-author-only...j.com/problems/RACETIME/
  242.  
  243.  
  244. int main(){
  245. fastio
  246. chandan2();
  247. lli t=1;
  248. //cin>>t;
  249. while(t--)
  250. {
  251.     lli q;
  252.     cin>>n>>q;
  253.     loop(i,n)
  254.         cin>>a[i];
  255.  
  256.     preprocess(n);
  257.  
  258.     while(q--)
  259.     {
  260.         char type;
  261.         cin>>type;
  262.         if(type == 'C')
  263.         {
  264.             lli l,r,k;
  265.             cin>>l>>r>>k;
  266.             l--;
  267.             r--;
  268.             print(query(l,r,k));
  269.         }
  270.         else
  271.         {
  272.             lli ind,val;
  273.             cin>>ind>>val;
  274.             ind--;
  275.             update(ind,val);
  276.         }
  277.     }
  278.  
  279.     clear();
  280.  
  281. }
  282.  
  283. return 0;
  284. }
Success #stdin #stdout 0s 5960KB
comments (?)
stdin
copy 
4 6
3
4
1
7
C 2 4 4
M 4 1
C 2 4 4
C 1 4 5
M 2 10
C 1 3 9
stdout
copy 
2
3
4
2
https://ideone.com/Vor1sH
language:
C++14 (gcc 8.3)
created:
3 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!