Persistent Segment Tree와 비슷한 Persistent Indexed Tree(?)를 구현해서 통과했다.
vector로 내맘대로 구현했는데, lower_bound썼으면 좀 더 깔끔했을듯.. 시간복잡도는 O(Mlog²N)
자세한 설명은 다음에...
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#define MAXN 262150
#define INF 1987654321
using namespace std;
struct st{
int mx, cnt, idx;
};
vector <st> tree[MAXN];
int n, m, sz;
pair <int, int> arr[100004];
__inline int max(int a, int b){ return a > b ? a : b; }
void cand_add(vector<st> &v, int idx, int p){
int low = 0;
int hi = tree[idx].size() - 1;
st ret = { NULL };
while (low <= hi){
int mid = (low + hi) >> 1;
if (tree[idx][mid].idx > p)
hi = mid - 1;
else{
ret = tree[idx][mid];
low = mid + 1;
}
}
if (ret.cnt)
v.push_back(ret);
}
int main(){
scanf("%d%d", &n, &m);
for (sz = 1; sz < n; sz <<= 1);
sz--;
for (int i = 1; i <= n; i++){
scanf("%d", &arr[i].first);
arr[i].second = i;
}
sort(arr + 1, arr + n + 1);
for (int i = 1; i <= n; i++){
int p = sz + arr[i].second;
tree[p].push_back({ arr[i].first, 1, i });
p >>= 1;
while (p){
tree[p].push_back({
max(tree[p << 1].size() ? (tree[p << 1].end() - 1)->mx : -INF, tree[(p << 1) + 1].size() ? (tree[(p << 1) + 1].end() - 1)->mx : -INF),
(tree[p << 1].size() ? (tree[p << 1].end() - 1)->cnt : 0) + (tree[(p << 1) + 1].size() ? (tree[(p << 1) + 1].end() - 1)->cnt : 0),
i
});
p >>= 1;
}
}
for (int i = 1; i <= m; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
int t_low = 1;
int t_hi = n;
while (t_low <= t_hi){
vector <st> cand;
int t_mid = (t_low + t_hi) >> 1;
int low = sz + a;
int hi = sz + b;
while (low <= hi){
if (low & 1) cand_add(cand, low, t_mid);
if (!(hi & 1)) cand_add(cand, hi, t_mid);
low = (low + 1) >> 1;
hi = (hi - 1) >> 1;
}
int total = 0;
for (auto it : cand)
total += it.cnt;
if (total < c) t_low = t_mid + 1;
else if (total>c) t_hi = t_mid - 1;
else{
int ans = -INF;
for (auto it : cand)
ans = max(ans, it.mx);
printf("%d\n", ans);
break;
}
}
}
}
kth.zip(출처 : NEERC Subregional Contest)