1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| using namespace std;
using range_t = std::pair<size_t, size_t>;
template<class T>
using op_t = T(const T&, const T&);
template<class T>
struct Seg {
long long mi, ma;
T x;
Seg<T> *left, *right;
Seg<T> (vector<T>& A, long long l, long long r, op_t<T> op) : mi(l), ma(r), left(nullptr), right(nullptr) {
if(l != r) {
long long m = l + (r - l) / 2;
left = new Seg<T>(A,l,m,op);
right = new Seg<T>(A,m+1,r,op);
x = op(left->x, right->x);
} else x = A[l];
}
bool inc(long long l, long long r) {
return l <= mi and ma <= r;
}
bool exc(long long l, long long r) {
return r < mi or l > ma;
}
T query(long long l, long long r, op_t<T> op) {
if(inc(l,r)) return x;
if(left->exc(l,r)) return right->query(l,r,op);
if(right->exc(l,r)) return left->query(l,r,op);
return op(left->query(l,r,op), right->query(l,r,op));
}
};
template<class T>
std::vector<T> computeRanges(std::vector<T> arr, op_t<T> op, std::vector<range_t> ranges) {
return {};
}
|
