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 crval = a[ind];
  228.         a[ind] = val;
  229.  
  230.         lli it = lower_bound(all(block[block_number]) , crval )-block[block_number].begin();
  231.  
  232.         lli n = sz(block[block_number]);
  233.  
  234.         for(lli i=max(0LL,it-3);i<min(n,it+3);i++){
  235.             if(block[block_number][i] == crval){
  236.                 block[block_number][i] = val;
  237.                 break;
  238.             }  
  239.         }
  240.         sort(all(block[block_number]));
  241.  
  242.     }
  243.  
  244.     //---------------------------------------------------SQRT_DECOMPO-------------------------------------------------------
  245.  
  246.     // 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/
  247.  
  248.  
  249.     int main(){
  250.     fastio
  251.     chandan2();
  252.     lli t=1;
  253.     //cin>>t;
  254.     while(t--)
  255.     {
  256.         lli q;
  257.         cin>>n>>q;
  258.         loop(i,n)
  259.             cin>>a[i];
  260.  
  261.         preprocess(n);
  262.  
  263.         while(q--)
  264.         {
  265.             char type;
  266.             cin>>type;
  267.             if(type == 'C')
  268.             {
  269.                 lli l,r,k;
  270.                 cin>>l>>r>>k;
  271.                 l--;
  272.                 r--;
  273.                 print(query(l,r,k));
  274.             }
  275.             else
  276.             {
  277.                 lli ind,val;
  278.                 cin>>ind>>val;
  279.                 ind--;
  280.                 update(ind,val);
  281.             }
  282.         }
  283.  
  284.         clear();
  285.  
  286.     }
  287.  
  288.     return 0;
  289.     }
Success #stdin #stdout 0s 5968KB
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/GoBA9s
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!