首先求出区间前$k$大数中奇数的个数和偶数的个数。

如果都是偶数，那么答案就是前$k$大数的和。

否则，要么去掉最小的偶数，加上最大的奇数，要么去掉最小的奇数，加上最大的偶数。

主席树维护即可。

时间复杂度$O((n+m)\log n)$。

 

#include
     
      #include
      
       using namespace std;const int N=300010,M=6000000;int n,m,i,x,y,k,a[N],b[N],tot,T[N],l[M],r[M],vc[M][2],c[2];long long v[M],sum,ans;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline int lower(int x){  int l=1,r=n,mid,t;  while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;  return t;}int ins(int x,int a,int b,int c,int d){  int y=++tot;  vc[y][0]=vc[x][0],vc[y][1]=vc[x][1];  vc[y][d&1]++,v[y]=v[x]+d;  if(a==b)return y;  int mid=(a+b)>>1;  if(c<=mid)l[y]=ins(l[x],a,mid,c,d),r[y]=r[x];else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c,d);  return y;}inline void ask(int x,int y,int k){  int a=1,b=n,mid,t;  c[0]=c[1]=sum=0;  while(a
       
        >1,t=vc[r[x]][0]+vc[r[x]][1]-vc[r[y]][0]-vc[r[y]][1];    if(k<=t)a=mid+1,x=r[x],y=r[y];    else{      k-=t;      c[0]+=vc[r[x]][0]-vc[r[y]][0];      c[1]+=vc[r[x]][1]-vc[r[y]][1];      sum+=v[r[x]]-v[r[y]];      b=mid,x=l[x],y=l[y];    }  }  c[::b[a]&1]+=k,sum+=1LL*::b[a]*k;}inline int kth(int x,int y,int k,int p){  int a=1,b=n,mid,t;  while(a
        
         >1,t=vc[r[x]][p]-vc[r[y]][p];    if(k<=t)a=mid+1,x=r[x],y=r[y];else k-=t,b=mid,x=l[x],y=l[y];  }  return ::b[a];}int main(){  for(read(n),i=1;i<=n;i++)read(a[i]),b[i]=a[i];  for(sort(b+1,b+n+1),i=1;i<=n;i++)T[i]=ins(T[i-1],1,n,lower(a[i]),a[i]);  read(m);  while(m--){    read(x),read(y),read(k);    if(k>y-x+1){puts("-1");continue;}    ask(T[y],T[x-1],k);    if(c[0]%2==0){printf("%lld\n",sum);continue;}    for(ans=-1,i=0;i<2;i++)      if(c[i]&&c[i^1]