KQUERY -K-query
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 i, j, k representing a k-query (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109).
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
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
Output
2
0
3
-----------------------------------------------------code------------------------------------------------------------------
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
int readInt () {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
typedef int lli;
typedef tree<
pair<int, int>,
null_type,
less<pair<int, int> >,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
ordered_set st;
// int ans=*st.find_by_order(n);
// int a=st.order_of_key(n);
const int bck_sz=448;
int ix=0;
struct node
{
lli x,y,idx;
};
node q[200005];
int a[30005];
int re[200005];
bool cmp(node a,node b)
{
lli i,j;
i=a.x/bck_sz;
j=b.x/bck_sz;
if(i==j)
{
if(a.y<b.y)
return 1;
else
return 0;
}
else{
if(i<j)
return 1;
else
return 0;
}
}
int val;
void add(int n)
{
// cout<<"insert "<<n<<endl;
st.insert({n,ix++});
}
void removex(int n)
{
// cout<<"delete "<<n<<endl;
st.erase(st.lower_bound({n,0}));
}
int rx[30005];
int main()
{
int i,j,k,n,m;
n=readInt ();
for(i=0;i<n;i++)
a[i]=readInt ();
m=readInt ();
for(i=0;i<m;i++)
{
int x,y;
x=readInt ();
y=readInt ();
k=readInt ();
rx[i]=k;
x--;
y--;
// cout<<x<<" "<<y<<endl;
q[i].x=x;
q[i].y=y;
q[i].idx=i;
}
sort(q,q+m,cmp);
int l=0,r=-1;
for(i=0;i<m;i++)
{
int lf=q[i].x;
int rf=q[i].y;
int idx=q[i].idx;
val=rx[idx];
// cout<<lf<<" query "<<rf<<endl;
while(r<rf)
{
r++;
// cout<<"rr "<<r<<endl;
// cout<<"a[r] "<<a[r]<<endl;
add(a[r]);
}
while(r>rf)
{
removex(a[r]);
r--;
}
while(l<lf)
{
removex(a[l]);
l++;
}
while(l>lf)
{
l--;
add(a[l]);
}
// cout<<"query "<<lf<<" "<<rf<<endl;
// int ans=*st.find_by_order(val);
int ar=st.order_of_key({val+1,0});
// cout<<"find by order "<<ans<<" order by key "<<ar<<endl;
/*for(auto it=st.begin();it!=st.end();it++)
{
// cout<<it->first<<endl;
}
*/
if(st.size() && st.lower_bound({(val+1),0})!=st.end())
{
//cout<<"order ";
// cout<<ar<<endl;
re[idx]=st.size()-ar;
}
}
for(i=0;i<m;i++)
printf("%d\n",re[i]);
return 0;
}
