#include <vector>
#include <functional>
#include <numeric>
template<typename T> constexpr T my_add(T a, T b) { return a + b; }
template<typename T, auto f = my_add<T> >
class persistent_segment_tree {
static_assert(std::is_convertible_v<decltype(f), std::function<T(T, T)> >);
private:
unsigned int n, root;
std::vector<T> st;
std::vector<unsigned int> lc, rc;
unsigned int build(unsigned int cl, unsigned int cr, const std::vector<T> &a) {
if (cl + 1 == cr) {
st.push_back(a[cl]); lc.push_back(0); rc.push_back(0);
return st.size() - 1;
}
unsigned int cm = (cl + cr) >> 1;
unsigned int tmp_l = build(cl, cm, a), tmp_r = build(cm, cr, a);
lc.push_back(tmp_l); rc.push_back(tmp_r);
st.push_back(f(st[tmp_l], st[tmp_r]));
return st.size() - 1;
}
T query(unsigned int idx, unsigned int cl, unsigned int cr, unsigned int l, unsigned int r) const {
if (l <= cl && cr <= r) return st[idx];
unsigned int cm = (cl + cr) >> 1;
if (r <= cm) return query(lc[idx], cl, cm, l, r);
if (l >= cm) return query(rc[idx], cm, cr, l, r);
return f(query(lc[idx], cl, cm, l, r), query(rc[idx], cm, cr, l, r));
}
unsigned int update(unsigned int idx, unsigned int cl, unsigned int cr, unsigned int pos, const T &val) {
if (cl + 1 == cr) {
st.push_back(val); lc.push_back(0); rc.push_back(0);
return st.size() - 1;
}
unsigned int cm = (cl + cr) >> 1;
unsigned int tmp_l = lc[idx], tmp_r = rc[idx];
if (pos < cm) tmp_l = update(lc[idx], cl, cm, pos, val);
else tmp_r = update(rc[idx], cm, cr, pos, val);
lc.push_back(tmp_l); rc.push_back(tmp_r);
st.push_back(f(st[tmp_l], st[tmp_r]));
return st.size() - 1;
}
public:
// Note: hasn't been tested yet
persistent_segment_tree() : n(0) {}
explicit persistent_segment_tree(const std::vector<T> &a) : n(a.size()) { root = build(0, n, a); }
// Note: hasn't been tested yet
explicit persistent_segment_tree(size_t _n) : persistent_segment_tree(std::vector<T>(_n)) {}
persistent_segment_tree(size_t _n, const T &x) : persistent_segment_tree(std::vector<T>(_n, x)) {}
unsigned int original_root() const { return root; }
T query(unsigned int idx, unsigned int l, unsigned int r) const { return query(idx, 0, n, l, r); }
// Note: hasn't been tested yet
T query(unsigned int idx, unsigned int l) const { return query(idx, l, l + 1); }
unsigned int update(unsigned int idx, unsigned int pos, const T &val) { return update(idx, 0, n, pos, val); }
// Note: hasn't been tested yet
size_t size() const { return n; }
};
#include <iostream>
#include <map>
#include <algorithm>
const int INF = 0x3f3f3f3f;
int main() {
std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
int n, q; std::cin >> n >> q;
std::vector<int> p(n + 1);
std::vector< std::vector<int> > mp((int) 2e5 + 5);
for (int i = 1; i <= n; i++) std::cin >> p[i], mp[p[i]].push_back(i);
persistent_segment_tree<int> st(n + 1, 0);
std::vector<int> roots((int) 2e5 + 5); roots[(int) 2e5 + 1] = st.original_root();
for (int i = (int) 2e5; i >= 0; i--) {
roots[i] = roots[i + 1];
for (auto &idx : mp[i]) roots[i] = st.update(roots[i], idx, 1);
}
while (q--) {
int l, r; std::cin >> l >> r;
int lo = 1, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (st.query(roots[mid], l, r + 1) >= mid) {
lo = mid;
} else {
hi = mid - 1;
}
}
std::cout << lo << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5980 KB |
Output is correct |
2 |
Correct |
3 ms |
6236 KB |
Output is correct |
3 |
Correct |
3 ms |
6236 KB |
Output is correct |
4 |
Correct |
3 ms |
6236 KB |
Output is correct |
5 |
Correct |
3 ms |
6236 KB |
Output is correct |
6 |
Correct |
4 ms |
5980 KB |
Output is correct |
7 |
Correct |
4 ms |
6060 KB |
Output is correct |
8 |
Correct |
3 ms |
6096 KB |
Output is correct |
9 |
Correct |
3 ms |
6236 KB |
Output is correct |
10 |
Correct |
3 ms |
6236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5980 KB |
Output is correct |
2 |
Correct |
3 ms |
6236 KB |
Output is correct |
3 |
Correct |
3 ms |
6236 KB |
Output is correct |
4 |
Correct |
3 ms |
6236 KB |
Output is correct |
5 |
Correct |
3 ms |
6236 KB |
Output is correct |
6 |
Correct |
4 ms |
5980 KB |
Output is correct |
7 |
Correct |
4 ms |
6060 KB |
Output is correct |
8 |
Correct |
3 ms |
6096 KB |
Output is correct |
9 |
Correct |
3 ms |
6236 KB |
Output is correct |
10 |
Correct |
3 ms |
6236 KB |
Output is correct |
11 |
Correct |
134 ms |
19512 KB |
Output is correct |
12 |
Correct |
121 ms |
20360 KB |
Output is correct |
13 |
Correct |
124 ms |
19320 KB |
Output is correct |
14 |
Correct |
120 ms |
19324 KB |
Output is correct |
15 |
Correct |
126 ms |
19464 KB |
Output is correct |
16 |
Correct |
120 ms |
20568 KB |
Output is correct |
17 |
Correct |
127 ms |
19424 KB |
Output is correct |
18 |
Correct |
125 ms |
19396 KB |
Output is correct |
19 |
Correct |
123 ms |
20100 KB |
Output is correct |
20 |
Correct |
131 ms |
19572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5980 KB |
Output is correct |
2 |
Correct |
3 ms |
6236 KB |
Output is correct |
3 |
Correct |
3 ms |
6236 KB |
Output is correct |
4 |
Correct |
3 ms |
6236 KB |
Output is correct |
5 |
Correct |
3 ms |
6236 KB |
Output is correct |
6 |
Correct |
4 ms |
5980 KB |
Output is correct |
7 |
Correct |
4 ms |
6060 KB |
Output is correct |
8 |
Correct |
3 ms |
6096 KB |
Output is correct |
9 |
Correct |
3 ms |
6236 KB |
Output is correct |
10 |
Correct |
3 ms |
6236 KB |
Output is correct |
11 |
Correct |
134 ms |
19512 KB |
Output is correct |
12 |
Correct |
121 ms |
20360 KB |
Output is correct |
13 |
Correct |
124 ms |
19320 KB |
Output is correct |
14 |
Correct |
120 ms |
19324 KB |
Output is correct |
15 |
Correct |
126 ms |
19464 KB |
Output is correct |
16 |
Correct |
120 ms |
20568 KB |
Output is correct |
17 |
Correct |
127 ms |
19424 KB |
Output is correct |
18 |
Correct |
125 ms |
19396 KB |
Output is correct |
19 |
Correct |
123 ms |
20100 KB |
Output is correct |
20 |
Correct |
131 ms |
19572 KB |
Output is correct |
21 |
Correct |
803 ms |
64848 KB |
Output is correct |
22 |
Correct |
790 ms |
64488 KB |
Output is correct |
23 |
Correct |
845 ms |
64260 KB |
Output is correct |
24 |
Correct |
830 ms |
64272 KB |
Output is correct |
25 |
Correct |
825 ms |
64416 KB |
Output is correct |
26 |
Correct |
886 ms |
64048 KB |
Output is correct |
27 |
Correct |
850 ms |
64004 KB |
Output is correct |
28 |
Correct |
799 ms |
64092 KB |
Output is correct |
29 |
Correct |
822 ms |
64244 KB |
Output is correct |
30 |
Correct |
787 ms |
64424 KB |
Output is correct |