mergesort tree, C++ (gcc)

mergesort tree

//g++  5.4.0

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int lb[100001]={0};
vector<int>tree[100001];
void build(int s,int st,int en)
{
    if(st==en)
    {
        tree[s].pb(lb[st]);
        return;
    }
    int mi=st+(en-st)/2;
    build(2*s,st,mi);
    build(2*s+1,mi+1,en);
    tree[s].resize(tree[2*s].size()+tree[2*s+1].size());
    merge(tree[2*s].begin(),tree[2*s].end(),tree[2*s+1].begin(),tree[2*s+1].end(),tree[s].begin());
}
int query(int s,int st,int en,int l,int r,int k)
{
    if(st>r || en<l)
        return 0;
    if(l<=st && r>=en)
    {
        int d=upper_bound(tree[s].begin(),tree[s].end(),k)-tree[s].begin();
        return tree[s].size()-d;
    }
    int mi=st+(en-st)/2;
    int p1=query(2*s,st,mi,l,r,k);
    int p2=query(2*s+1,mi+1,en,l,r,k);
    return p1+p2;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&lb[i]);
    build(1,0,n-1);
    int q;
    scanf("%d",&q);
    for(int i=0;i<q;++i)
    {
        int l,r,k;
        scanf("%d %d %d",&l,&r,&k);
        printf("%d\n",query(1,0,n-1,l-1,r-1,k));
    }
}


run \| edit \| history \| help	0