yjq_1999

观察到求出区间第K大，如果奇数个数和偶数个数都是偶数，则输出前K大的和，否则要么奇数多一个，要么偶数多一个，主席树SB题

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>
#include <cctype>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif

using namespace std;

int n;

void read(int &a) {
  a = 0;char c = getchar();
  while (isspace(c)) c = getchar();
  do a = a * 10 + c - '0',c = getchar();while (isdigit(c));
}
const int MAXN = 300010;
const int MAXM = 1000000000;

int a[MAXN];
struct Node {
  int ls,rs,lt,rt,siz;
  long long sum;
} seg[MAXN * 50];

int node_id = 0,root[MAXN];

struct Data {
  int lsum,rsum,v;
  long long sum;
  Data (long long a_ = 0,int b_ = 0,int c_ = 0,int d_ = 0) {
    sum = a_,lsum = b_,rsum = c_,v = d_;
  }
} ;

inline void update(int x) {
  int L = seg[x].ls,R=  seg[x].rs;
  seg[x].lt = seg[L].lt + seg[R].lt,seg[x].rt = seg[L].rt + seg[R].rt;
  seg[x].siz = seg[L].siz + seg[R].siz;
  seg[x].sum = seg[L].sum + seg[R].sum;
}

inline void Insert(int pre,int &x,int p,int l,int r) {
  if (!x) x = ++node_id;
  if (l == r) {
    seg[x].siz = seg[pre].siz + 1;
    seg[x].lt = seg[pre].lt + (p & 1);
    seg[x].rt = seg[pre].rt + ((p & 1) ^ 1);
    seg[x].sum = seg[pre].sum + p;
    return ;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) seg[x].rs = seg[pre].rs,Insert(seg[pre].ls,seg[x].ls,p,l,mid);
  else seg[x].ls = seg[pre].ls,Insert(seg[pre].rs,seg[x].rs,p,mid + 1,r);
  update(x);
}

void Init() {
  for (int i = 1;i <= n;i ++) {
    Insert(root[i - 1],root[i],a[i],0,MAXM);
  }
}

Data QueryData(int pre,int x) {
  return Data(0,seg[x].lt - seg[pre].lt,seg[x].rt - seg[pre].rt,0);
}

Data QueryKth(int pre,int x,int k,int l,int r) {
  if (l == r) return Data(1LL * l * k,k * (l & 1),k * ((l & 1) ^ 1),l);
  int mid = (l + r) >> 1;
  if (seg[seg[x].rs].siz - seg[seg[pre].rs].siz >= k) return QueryKth(seg[pre].rs,seg[x].rs,k,mid+  1,r);
  else {
    Data res = Data(seg[seg[x].rs].sum - seg[seg[pre].rs].sum,seg[seg[x].rs].lt - seg[seg[pre].rs].lt,seg[seg[x].rs].rt - seg[seg[pre].rs].rt,0);
    Data ano = QueryKth(seg[pre].ls,seg[x].ls,k - (seg[seg[x].rs].siz - seg[seg[pre].rs].siz),l,mid);
    res.sum += ano.sum,res.lsum += ano.lsum,res.rsum += ano.rsum,res.v = ano.v;
    return res;
  }
}

int QueryKthVL(int pre,int x,int k,int l,int r) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (seg[seg[x].rs].lt - seg[seg[pre].rs].lt >= k) return QueryKthVL(seg[pre].rs,seg[x].rs,k,mid + 1,r);
  else return QueryKthVL(seg[pre].ls,seg[x].ls,k - (seg[seg[x].rs].lt - seg[seg[pre].rs].lt),l,mid);
}

inline void update(long long &a,long long b) {
  if (a < b) a = b;
}

int QueryKthVR(int pre,int x,int k,int l,int r) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (seg[seg[x].rs].rt - seg[seg[pre].rs].rt >= k) return QueryKthVR(seg[pre].rs,seg[x].rs,k,mid + 1,r);
  else return QueryKthVR(seg[pre].ls,seg[x].ls,k - (seg[seg[x].rs].rt - seg[seg[pre].rs].rt),l,mid);
}
void Solve(int l,int r,int k) {
  Data t = QueryData(root[l - 1],root[r]);
  if (t.lsum / 2 + t.rsum / 2 < k / 2) {
    puts("-1");
    return ;
  }
  Data g = QueryKth(root[l - 1],root[r],k,0,MAXM);
  long long ans = -1;
  if (g.lsum & 1) {
    if (t.lsum - g.lsum) {
      int delta = QueryKthVL(root[l - 1],root[r],g.lsum + 1,0,MAXM) - QueryKthVR(root[l - 1],root[r],g.rsum,0,MAXM);
      update(ans,g.sum + delta);
    }
    if (t.rsum - g.rsum) {
      int delta = QueryKthVR(root[l - 1],root[r],g.rsum + 1,0,MAXM) - QueryKthVL(root[l - 1],root[r],g.lsum,0,MAXM);
      update(ans,g.sum + delta);
    }
  }
  else ans = g.sum;
  printf(LL "\n",ans);
}

int main() {
#ifdef YJQ_LOCAL
  freopen(".in","r",stdin);
#endif
  scanf("%d",&n);
  for (int i = 1;i <= n;i ++) read(a[i]);
  Init() ;
  int T;
  read(T);
  while (T --) {
    int L,R,K;
    read(L),read(R),read(K);
    Solve(L,R,K);
  }
}