Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 注意二分的时候的边界就好

Posted by an_old_fresh at 2018-07-05 18:59:06 on Problem 2104
```我用归并树写的， 代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;
const int maxn = 100000 + 50;
const int depth = 25;

int merge_tree[depth][maxn];
int num[maxn];
int N, M;

void build_tree(int deep, int lp, int rp) {
if (lp == rp) {
merge_tree[deep][lp] = num[lp];
return;
}

int mid = (lp + rp) >> 1;
build_tree(deep + 1, lp, mid);
build_tree(deep + 1, mid + 1, rp);

int i = lp, j = mid + 1, ind = lp;
while (i <= mid || j <= rp) {
if (i > mid || (j <= rp && merge_tree[deep + 1][i] > merge_tree[deep + 1][j]))
merge_tree[deep][ind++] = merge_tree[deep + 1][j++];
else
merge_tree[deep][ind++] = merge_tree[deep + 1][i++];
}

}

int query(int layer, int lp, int rp, int q_lp, int q_rp, int val) {
if (lp > q_rp || rp < q_lp)
return 0;
if (q_lp <= lp && rp <= q_rp)
return lower_bound(merge_tree[layer] + lp, merge_tree[layer] + rp + 1, val) - (merge_tree[layer] + lp);

int mid = (lp + rp) >> 1;
return query(layer + 1, lp, mid, q_lp, q_rp, val) + query(layer + 1, mid + 1, rp, q_lp, q_rp, val);
}

int main()
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++)
scanf("%d", &num[i]);
build_tree(0, 0, N - 1);
for (int i = 0; i < M; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--; b--; c--;
int lp = 0, rp = N;
while (lp < rp) {
int mid = (lp + rp) >> 1;
int val = merge_tree[0][mid];
int cnt = query(0, 0, N - 1, a, b, val);
if (cnt <= c)
lp = mid + 1;
else
rp = mid;
}
printf("%d\n", merge_tree[0][rp - 1]);
}//for int i
return 0;
}```

Followed by: