讨论 / 二分+排序
ypfhd 2015-08-07 07:47:32
点我顶贴 收藏 删除
整体二分+排序
#1 ypfhd@2015-08-08 00:48:51
回复 删除
#include <cstdio>

#include <algorithm>

using namespace std;

int N, M;

int A[10004], S[10004], Q[2003], Res[2003], T[10004], C[2003], D[2003];

struct Query

{

int l, r, k;

}Qr[2003];

inline bool Cmp(int a, int b)

{

return A[a] < A[b];

}

inline bool Cmp3(int a, int b)

{

return a < b;

}

inline int E_Cnt(int N, int Q)

{

static int l, r, mid, L, R;

if (Qr[Q].l > T[N]) return false;

if (Qr[Q].r < T[1]) return false;

l = 0, r = N;

while (l + 1 < r)

{

mid = (l + r) >> 1;

(Qr[Q].l > T[mid]) ? (l = mid) : (r = mid);

}

L = l;

l = 1, r = N + 1;

while (l + 1 < r)

{

mid = (l + r) >> 1;

(Qr[Q].r < T[mid]) ? (r = mid) : (l = mid);

}

R = l;

if (R - L >= Qr[Q].k) return true;

else

{

Qr[Q].k -= R - L;

return false;

}

}

void C_Q(int *S, int N, int *Q, int M)

{

if (N == 1)

{

for (int i = 1; i <= M; i ++) Res[Q[i]] = A[S[1]];

return;

}

int Mid = (1 + N) >> 1;

for (int i = 1; i <= Mid; i ++) T[i] = S[i];

sort(T + 1, T + Mid + 1, Cmp3);

C[0] = D[0] = 0;

for (int i = 1; i <= M; i ++)

(E_Cnt(Mid, Q[i])) ? (C[++ C[0]] = Q[i]) : (D[ ++ D[0]] = Q[i]);

for (int i = 1; i <= C[0]; i ++) Q[i] = C[i];

for (int i = 1; i <= D[0]; i ++) Q[C[0] + i] = D[i];

int L = C[0], R = D[0];

if (L) C_Q(S, Mid, Q, L);

if (R) C_Q(S + Mid, N - Mid, Q + L, R);

}

int main()

{

scanf("%d%d", &N, &M);

for (int i = 1; i <= N; i ++) scanf("%d", &A[i]), S[i] = i;

for (int i = 1, l, r, k; i <= M; i ++)

scanf("%d%d%d", &l, &r, &k), Qr[i] = (Query){l, r, k}, Q[i] = i;

sort(S + 1, S + N + 1, Cmp);

C_Q(S, N, Q, M);

for (int i = 1; i <= M; i ++) printf("%d\n", Res[i]);

return 0;

}

查看更多回复
提交回复