Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define maxn 100010
- #define range(v) v.begin(),v.end()
- using namespace std;
- vector<int> st[4*maxn],a(maxn,0);
- void build(int s,int e,int index)
- {
- if(s==e)
- {
- st[index].push_back(a[s]);
- return;
- }
- int mid = (s+e)/2;
- int l=2*index+1;
- int r=2*index+2;
- build(s,mid,l);
- build(1+mid,e,r);
- merge(range(st[l]),range(st[r]),back_inserter(st[index]));
- return;
- }
- int query(int index,int s,int e,int qs,int qe,int k)
- {
- if(s>qe || e<qs)
- {
- return 0;
- }
- if(qs<=s && qe<=e)
- {
- return e-s+1-(lower_bound(st[index].begin(),st[index].end(),k)-st[index].begin());
- }
- int mid=(s+e)/2;
- return query(2*index+1,s,mid,qs,qe,k)+query(2*index+2,1+mid,e,qs,qe,k);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- int n;
- cin>>n;
- for(int i=0;i<n;i++)
- {
- cin>>a[i];
- }
- build(0,n-1,0);
- int q;
- cin>>q;
- while(q--)
- {
- int l,r,k;
- cin>>l>>r>>k;
- int ans = query(0,0,n-1,l-1,r-1,k);
- cout<<ans<<endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment