KQUERY - SPOJ
Problem Statement: here
Solution:
I will be sharing 3 different Approaches. Starting from the one which will give TLE.
So, the statement in the question is quite simple, you just need to output the number of elements in the range which are greater then k.
o_set ped[4*30000 + 5];
int n;
int a[30005];
void update(int ind, int l, int r, int t, int val){
if (t < l || t > r){
return;
}
if (l == r){
ped[ind].insert(-1*val);
return;
}
int mid = (l+r)/2;
update(2*ind,l,mid,t,val);
update(2*ind+1,mid+1,r,t,val);
ped[ind].insert(-1*val);
}
int query(int ind, int l, int r, int qs, int qe, int k){
if (l > qe || r < qs){
return 0;
}
if (l >= qs and r<= qe){
return ped[ind].order_of_key(-1*k);
}
int mid = (l+r)/2;
return query(2*ind,l,mid,qs,qe,k) + query(2*ind+1,mid+1,r,qs,qe,k);
}
void solve()
{
cin >> n;
rep(i,0,n){
cin >> a[i];
update(1,0,n-1,i,a[i]);
}
int q;
cin >> q;
rep(p,0,q){
int i,j,k;
cin >> i >> j >> k;
cout << query(1,0,n-1,--i,--j,k) << endl;
}
}
I will be sharing 3 different Approaches. Starting from the one which will give TLE.
So, the statement in the question is quite simple, you just need to output the number of elements in the range which are greater then k.
First Approach - Using Ordered Set in Segment Trees
If you are not familiar with ordered sets, have a look here.
The only problem is how to create the build function as to how will we merge the two nodes. So, since the merging can be a problem, we can use the update function and we can update the tree by adding new elements each time. So, overall complexity of building the tree goes to O(N*logN*logN). Because, for each element, we have logN nodes for traversal, and at each node, it takes logN time to perform the insert operation. After that for each query, we have logN*logN complexity too. Because order of key function takes logN time to process.
So, the overall complexity is O((N+Q)*logN*logN). But still, it will throw TLE, maybe because the order of key may take more than logN time per query.
Implementation:
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
Second Approach - Processing Queries Offline
So, the idea is to store all queries and sort them on the basis of their k values. Also, sort the input array. Initially, we assume our k = 0. So, all the elements are greater than 0, so we build a segment tree wherein each leaf node which represents the array elements will be 1, denoting they are greater than k.
Now, we start to loop over the sorted queries, since for each query, the k value is greater than the previous query, we know for sure, that elements which are smaller than previous query k value will be smaller than our k value. Since the input array is also now sorted, we can loop over the input array to the point where it's elements are either less than or equal to our current k value. Again, we are sure that for all upcoming queries, all elements below this index will surely be smaller than our future k values.
Once we loop over the input array, we start to update the segment tree with that particular leaf node's value set equal to zero. Remember, we initially placed all bits set because our k was 0. But, once we loop over queries we get different k, once we loop over the array and check if array element is less than or equal to k, we simply update the segment tree and set the bit to zero. Once our array loop is terminated, we simply perform query over the required query range to get the sum of all set bits.
The code:
int sum[4*30000 + 5];
int n;
pair<int,int> a[30005];
pair<pair<int,int>,pair<int,int>> q[200005];
int ans[200005];
void build(int ind, int l, int r){
if (l == r){
sum[ind] = 1;
return;
}
int mid = (l+r)>>1;
build(2*ind,l,mid);
build(2*ind+1,mid+1,r);
sum[ind] = sum[2*ind] + sum[2*ind+1];
}
void update(int ind, int l, int r, int p){
if (p < l or p > r){
return;
}
if (l == r){
sum[ind] = 0;
return;
}
int mid = (l+r)/2;
update(2*ind,l,mid,p);
update(2*ind+1,mid+1,r,p);
sum[ind] = sum[2*ind] + sum[2*ind+1];
}
int get_sum(int ind, int l, int r, int qs, int qe){
if (l > qe || r < qs){
return 0;
}
if (l >= qs and r<= qe){
return sum[ind];
}
int mid = (l+r)/2;
return get_sum(2*ind,l,mid,qs,qe) + get_sum(2*ind+1,mid+1,r,qs,qe);
}
void solve()
{
cin >> n;
rep(i,0,n){
cin >> a[i].F;
a[i].S = i;
}
build(1,0,n-1);
int qr;
cin >> qr;
rep(i,0,qr){
cin >> q[i].S.F >> q[i].S.S >> q[i].F.F;
q[i].F.S = i;
}
sort(a,a+n);
sort(q,q+qr);
int pos = 0;
rep(i,0,qr){
int k = q[i].F.F;
while(pos < n and a[pos].F <= k){
update(1,0,n-1,a[pos].S);
pos++;
}
ans[q[i].F.S] = get_sum(1,0,n-1,--q[i].S.F,--q[i].S.S);
}
rep(i,0,qr) cout << ans[i] << endl;
}
Third Approach - Using Fenwick Trees
This approach becomes crucial when we have updates as well, we will look at this approach in the future problem of our series, namely this problem - https://www.spoj.com/problems/KQUERYO/
No comments:
Post a Comment