KQUERY -K-query

KQUERY -K-query 

no tags 

English

Vietnamese

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 

 Submit solution!

---

hide comments

-----------------------------------------------------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; }