RACETIME - Race Against Time( in l to r fingd number of numbers <=X ) sqrt decompossition

RACETIME - Race Against Time

As another one of their crazy antics, the N (1 ≤ N ≤ 100,000) cows want Farmer John to race against the clock to answer some of their pressing questions.

The cows are lined up in a row from 1 to N, and each one is holding a sign representing a number, Ai (1 ≤ Ai ≤ 1,000,000,000). The cows need FJ to perform Q (1 ≤ Q ≤ 50,000) operations, which can be either of the following:

• Modify cow i's number to X (1 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter M followed by the space-separated numbers i and X.
• Count how many cows in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have Ai ≤ X (0 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter C followed by the space-separated numbers P, Q, and X.

Of course, FJ would like your help.

Input

The first line gives the integers N and Q, and the next N lines give the initial values of Ai. Finally, the next Q lines each contain a query of the form "M i X" or "C P Q X".

Output

Print the answer to each 'C' query, one per line.

Example

Input:
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

Output:
2
3
4
2

FJ has 4 cows, whose initial numbers are 3, 4, 1, and 7. The cows then give him 6 operations; the first asks him to count the how many of the last three cows have a number at most 4, the second asks him to change the fourth cow's number to 1, etc.

===================================editorial=====================================

divide the array in sqrt part and each part contain a sorted vector , now iterate  block wise , if a block completely inside   the range than count using b'search ( since content of block is sorted)  else if a block is partially in the range than iterate , in that  block,,

 for update ,  replace and sort the vector of the block ....

================================code===============================================#include<bits/stdc++.h>

using namespace std;

 vector<int> block[1000];

 int arr[1000000];

int main()

 {

  int n,q;

   scanf("%d %d",&n,&q);

       int sq=317;

        int b_size=317;

     if(sqrt(n)*sqrt(n)!=n)

   {

  sq++;

  b_size++;

} 

       for(int  i=0;i<n;i++)

         {

             int a;

            scanf("%d",&a);

            arr[i]=a;

            block[i/b_size].push_back(a);

}

for(int i=0;i<sq;i++)

{

sort(block[i].begin(),block[i].end());

}

for(int i=0;i<q;i++)

{

char type;

 cin>>type;

   if(type=='C')

     {

         int l,r,val;

 scanf("%d %d %d",&l,&r,&val);

 

 int ans=0;

 l--;

 r--;

 for(int i=0;i<sq;i++)

  {

   int bs=i*b_size;

   int be=bs+b_size-1;

   if(l<=bs && r>=be)

       {  

        int count=upper_bound(block[i].begin(),block[i].end(),val)-block[i].begin();

        ans+=count;

 }

 else 

   {

    for( int j = max(bs,l) ; j <= min(be,r);j++ ) // if range have some portion in this block

                                            ans += (arr[j]<=val) ;

}

  }

 

  printf("%d\n",ans);

 }

 else

 {

   int idx;int val;

   scanf("%d %d",&idx,&val);

   idx--;

    int bnum=idx/b_size;

    int remove=arr[idx];

   // int f=0;

    for(int i=0;i<b_size;i++)

       {

      if(block[bnum][i]==remove)

         { 

           block[bnum][i]=val;

           arr[idx]=val;

           break;

}

 }

  sort(block[bnum].begin(),block[bnum].end());

 }

}

 }