Algorithm
problem link- https://www.spoj.com/problems/RACETIME/
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.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
const int MAXN = 1e5+5;
int a[MAXN];
vector<int> b[320];
int main(){
io;
int n, q;
cin >> n >> q;
int sqrtn = sqrt(n);
for(int i = 0;i < n; i++){
cin >> a[i];
b[i/sqrtn].push_back(a[i]);
}
int numBlocks = ceil((double)n/sqrtn);
for(int i = 0;i < numBlocks; i++)
sort(b[i].begin(), b[i].end());
while(q--){
char c;
cin >> c;
if(c == 'M'){
int idx, newVal;
cin >> idx >> newVal;
--idx;
int block = idx/sqrtn;
int initVal = a[idx];
// search initVal in block
int lo = 0, hi = sqrtn-1;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if(b[block][mid] == initVal){
b[block][mid] = newVal;
break;
}else if(b[block][mid] < initVal){
lo = mid + 1;
}else{
hi = mid - 1;
}
}
a[idx] = newVal;
sort(b[block].begin(), b[block].end());
}else{
int l, r, x;
cin >> l >> r >> x;
--l;--r;
int leftBlock = l/sqrtn;
int rightBlock = r/sqrtn;
int ans = 0;
if(leftBlock == rightBlock){
for(int i = l;i <= r; i++){
if(a[i] <= x)
ans++;
}
cout << ans << endl;
}else{
if(l%sqrtn != 0)
leftBlock++;
int i;
for(i = l;i < leftBlock*sqrtn; i++)
if(a[i] <= x)
ans++;
while(i+sqrtn-1 <= r){
int bb = i/sqrtn;
ans += upper_bound(b[bb].begin(), b[bb].end(), x) - b[bb].begin();
i += sqrtn;
}
while(i <= r){
if(a[i] <= x)
ans++;
i++;
}
cout << ans << endl;
}
}
}
return 0;
}Input
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
3
4
2
Demonstration
SPOJ Solution-Race Against Time-Solution in C, C++, Java, Python