mergesort tree kth sum kth number find

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long ,ll>pll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define sf(a) scanf("%d",&a)

const int Max = 1e5 + 10;

pair<int,int> ara[Max+10];

vector<int>tree[5*Max];

vector<long long>Sum[5*Max];

long long cum[Max+10];

int value[Max+2];

void build_tree(ll l, ll r, ll node)
{
    if(l==r)
    {
        tree[node].pb(ara[l].S);

        Sum[node]={0,ara[l].F};

        return ;
    }

    ll mid=(l+r)/2;

    ll left=node*2,right=(node*2)+1;

    build_tree(l,mid,left);
    build_tree(mid+1,r,right);

    merge(tree[left].begin(),tree[left].end(),tree[right].begin(),tree[right].end(),back_inserter(tree[node]));

    long long i,sum=0;

    Sum[node].eb(0);

   for(auto x : tree[node])
   {
       sum+=value[x];

       Sum[node].eb(sum);

   }

}



pll kthNumberSum(int node, int b, int e, int l, int r, int k)
{
    if(b==e)
        return {Sum[node].back(),tree[node].back()};

    ll Left=node*2;
    ll Right=Left+1;
    ll mid=(b+e)/2;

    auto x=upper_bound(vll(tree[Left]),r)-tree[Left].begin();

    auto t=lower_bound(vll(tree[Left]),l)-tree[Left].begin();

    if(x-t>=k)
        return kthNumberSum(Left,b,mid,l,r,k);

    else
        {
            pll ret= kthNumberSum(Right,mid+1,e,l,r,k-x+t);

            ret.F+=Sum[Left][x]-Sum[Left][t];

            return ret;
        }
}

//find kth number with sum

//only kth number

/*
ll kthNumber(int node, int b, int e, int l, int r, int k)
{
    if(b==e)
        return tree[node].back();

    ll Left=node*2;
    ll Right=Left+1;
    ll mid=(b+e)/2;

    auto x=upper_bound(vll(tree[Left]),r)-lower_bound(vll(tree[Left]),l);

    if(x>=k)
        return kthNumber(Left,b,mid,l,r,k);

    else
        return kthNumber(Right,mid+1,e,l,r,k-x);
}

*/


int main()
{
    ll i,j,m,p,a,sum=0,k,t,b,c,d,cnt=0,l,r,ans=0;

    int n,q;
      sf(n);
      sf(q);

       for(i=1; i<=n; i++)
       {
           sf(ara[i].F);

          ara[i].S=i;

          value[i]=ara[i].F;

          cum[i]=cum[i-1]+value[i];
       }

     sort(ara+1,ara+n+1);

    build_tree(1,n,1);

    while(q--)
    {
        sf(l);
        sf(r);

       k=(r-l+1)/2;
       k++;

       ll total=r-l+1;

       pll ans=kthNumberSum(1,1,n,l,r,k);

       ans.S=value[ans.S];

       long long sum=cum[r]-cum[l-1];

       long long sum1=abs( (sum-ans.F)-(ans.S*(total-k)));

       long long sum2=abs(ans.F-(k*ans.S));

       printf("%lld\n",sum1+sum2);
    }


}