观察到求出区间第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);
}
}