线段树每个节点存一个 vector
。考虑二分答案,然后查询区间内小于 mid
的数的个数来进行 check
。
由于每个区间在线段树上最多定位到 $\log n$ 个节点,而在每个节点二分查询小于某个数的个数需要 $\log n$ 的时间,加上二分的时间复杂度,这个算法的时间复杂度就是 $O(m \log ^ 2 n \log V)$。
但是不知道为什么,跑得比主席树还快。
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
using namespace std;
const int N = 100010;
vector<int> vec[N << 2];
int n, m, a[N];
struct node {
int l, r;
}tr[N << 2];
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (tr[u].l + tr[u].r >> 1)
void build(int u, int l, int r) {
tr[u] = {l, r};
rep(i, l, r) vec[u].push_back(a[i]);
sort(all(vec[u]));
if (l == r) return;
build(ls, l, mid); build(rs, mid + 1, r);
}
int query(int u, int l, int r, int v) {
if (tr[u].l >= l and tr[u].r <= r) {
auto p = lower_bound(all(vec[u]), v);
if (p == vec[u].begin()) return 0;
return p - vec[u].begin();
} int s = 0;
if (l <= mid) s += query(ls, l, r, v);
if (r > mid) s += query(rs, l, r, v); return s;
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%d", &a[i]);
build(1, 1, n);
while (m -- ) {
int L, R, k;
scanf("%d%d%d", &L, &R, &k);
int l = (int)-1e9, r = (int)1e9;
while (l < r) {
int Mid = l + r + 1 >> 1;
if (query(1, L, R, Mid) >= k) r = Mid - 1;
else l = Mid;
} printf("%d\n", l);
} return 0;
}
可惜类似的代码经过卡常优化后在你谷只有八十分。