Algorithm
Problem link- https://www.spoj.com/problems/KQUERYO/
KQUERYO - K-Query Online
Given a sequence of n numbers a1, a2, ..., an and a number of k-queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ..., aj.
Input
- Line 1: n (1 ≤ n ≤ 30000).
- Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 109).
- Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
- In the next q lines, each line contains 3 numbers a, b, c representing a k-query. You should do the following:
- i = a xor last_ans
- j = b xor last_ans
- k = c xor last_ans
Where last_ans = the answer to the last query (for the first query it's 0).
Output
For each k-query (i, j, k), print the number of elements greater than k in the subsequence ai, ai+1, ..., aj in a single line.
Example
Input: 6 8 9 3 5 1 9 5 2 3 5 3 3 7 0 0 11 0 0 2 3 7 4 Output: 1 1 0 0 2
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);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e5+5;
int a[MAXN];
vector<int> b[320];
int main(){
io;
int n;
cin >> n;
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());
int q;
cin >> q;
int answer = 0;
while(q--){
int l, r, x;
cin >> l >> r >> x;
l ^= answer;
r ^= answer;
x ^= answer;
if(l < 1)
l = 1;
if(r > n)
r = n;
l--;r--;
answer = 0;
if(r >= l){
int leftBlock = l/sqrtn;
int rightBlock = r/sqrtn;
if(leftBlock == rightBlock){
for(int i = l; i <= r; i++){
if(a[i] > x)
answer++;
}
}else{
if(l%sqrtn != 0){
leftBlock++;
}
int i;
for(i = l; i < leftBlock*sqrtn; i++){
if(a[i] > x)
answer++;
}
while(i+sqrtn-1 <= r){
int bb = i/sqrtn;
answer += b[bb].end() - upper_bound(b[bb].begin(), b[bb].end(), x);
i += sqrtn;
}
while(i <= r){
if(a[i] > x)
answer++;
i++;
}
}
}
cout << answer << endl;
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
8 9 3 5 1 9
5
2 3 5
3 3 7
0 0 11
0 0 2
3 7 4
Output
1
0
0
2
Demonstration
SPOJ Solution-K-Query Online-Solution in C, C++, Java, Python