#include <vector>
#include <functional>
#include <optional>
#include <iostream>
#include <set>
#define FAST_ALLOCATOR_MEMORY (230*1024*1024)
#include "optimization.h"
using namespace std;
using ll = long long;
template<typename T>
struct Monoid;
template<typename Mon>
struct ValidMonoid : private Mon {
using value_type = typename Mon::value_type;
using T = typename Mon::value_type;
static_assert(std::is_same_v<decltype(Mon::compose(std::declval<T>(), std::declval<T>())), T>);
static_assert(std::is_same_v<decltype(Mon::identity()), T>);
using Mon::compose;
using Mon::identity;
};
template<typename T>
struct Updater : Updater<Monoid<T>> {
using valid = ValidMonoid<Monoid<T>>;
};
template<typename Upd>
struct ValidUpdater : private Upd {
using value_type = typename Upd::value_type;
using update_type = typename Upd::update_type;
using T = typename Upd::value_type;
using U = typename Upd::update_type;
using valid = ValidMonoid<Upd>;
static_assert(std::is_same_v<decltype(Upd::update(std::declval<T>(), std::declval<U>(),
std::declval<size_t>(), std::declval<size_t>())), T>);
using Upd::update;
using Upd::compose;
using Upd::identity;
};
template<typename T>
struct Updater<Monoid<T>> : Monoid<T> {
using M = Monoid<T>;
using valid = ValidMonoid<M>;
using value_type = typename M::value_type;
using update_type = typename M::value_type;
static value_type update(const value_type& a, const update_type& b, size_t l, size_t r) { return M::compose(a, b); }
};
template<typename T>
struct STOp {
using composer = ValidMonoid<Monoid<T>>;
using updater = ValidUpdater<Updater<T>>;
};
template<typename Op>
struct ValidSTOp : Op {
using compose_valid = ValidMonoid<typename Op::composer>;
using updater_valid = ValidUpdater<typename Op::updater>;
static_assert(std::is_same_v<typename Op::composer::value_type, typename Op::updater::value_type>);
using typename Op::composer;
using typename Op::updater;
};
template<typename Operation>
class SegmentTree {
public:
using Op = ValidSTOp<STOp<Operation>>;
using Cm = ValidMonoid<typename Op::composer>;
using Up = ValidUpdater<typename Op::updater>;
using T = typename Cm::value_type;
using U = typename Up::update_type;
explicit SegmentTree(size_t n) : n(n) {
data.resize(4 * n, Cm::identity());
updates.resize(data.size(), Up::identity());
}
explicit SegmentTree(int n) : SegmentTree(static_cast<size_t>(n)) {}
template<typename Cont>
explicit SegmentTree(const Cont& cont) : SegmentTree(cont.size()) {
build(cont, 1, 0, n);
}
T compute(size_t l, size_t r) {
return compute(1, 0, n, l, r);
}
void applyToLeaf(size_t i, std::function<T(const T&, size_t, size_t)> f) {
applyToLeaf(1, 0, n, i, std::move(f));
}
void applyToLeaf(size_t i, std::function<T(const T&)> f) {
applyToLeaf(i, [f](const T& t, size_t l, size_t r){ return f(t); });
}
void set(size_t i, T x) {
applyToLeaf(i, [&x](const T& y, size_t l, size_t r) { return x; });
}
void update(size_t i, U upd) {
applyToLeaf(i, [this, &upd](const T& x, size_t l, size_t r) { return Up::update(x, upd, l, r); });
}
void update(size_t l, size_t r, U upd) {
update(1, 0, n, l, r, upd);
}
private:
void check_bounds(size_t v, size_t vl, size_t vr, size_t l, size_t r) {
assert(v < data.size());
assert(vl <= n);
assert(vr <= n);
assert(l <= n);
assert(r <= n);
}
T compute(size_t v, size_t vl, size_t vr, size_t l, size_t r) {
check_bounds(v, vl, vr, l, r);
if (disjoint(vl, vr, l, r)) return Cm::identity();
if (embedded(vl, vr, l, r)) {
return data[v];
}
size_t vm = mid(vl, vr);
return Up::update(
Cm::compose(
compute(left(v), vl, vm, l, r),
compute(right(v), vm, vr, l, r)
),
updates[v], vl, vr
);
}
void update(size_t v, size_t vl, size_t vr, size_t l, size_t r, U upd) {
check_bounds(v, vl, vr, l, r);
recompute(v, vl, vr);
if (disjoint(vl, vr, l, r)) return;
if (embedded(vl, vr, l, r)) {
updates[v] = Up::compose(updates[v], upd);
recompute(v, vl, vr);
return;
}
size_t vm = mid(vl, vr);
push(v);
update(left(v), vl, vm, l, r, upd);
update(right(v), vm, vr, l, r, upd);
recompute(v, vl, vr);
}
void push(size_t v) {
assert(v < data.size());
updates[left(v)] = Up::compose(updates[left(v)], updates[v]);
updates[right(v)] = Up::compose(updates[right(v)], updates[v]);
updates[v] = Up::identity();
}
void applyToLeaf(size_t v, size_t vl, size_t vr, size_t i, std::function<T(const T&, size_t, size_t)> f) {
check_bounds(v, vl, vr, 0, 0);
if (vl == i && vr == i + 1) {
data[v] = f(data[v], vl, vr);
return;
}
size_t vm = mid(vl, vr);
if (i < vm) applyToLeaf(left(v), vl, vm, i, f);
else applyToLeaf(right(v), vm, vr, i, f);
recompute(v, vl, vr);
}
template<typename Cont>
void build(const Cont& cnt, size_t v, size_t vl, size_t vr) {
if(vl + 1 == vr) {
data[v] = cnt[vl];
return;
}
size_t vm = mid(vl, vr);
build(cnt, left(v), vl, vm);
build(cnt, right(v), vm, vr);
recompute(v, vl, vr);
}
bool disjoint(size_t vl, size_t vr, size_t l, size_t r) { return vr <= l || r <= vl; }
bool embedded(size_t vl, size_t vr, size_t l, size_t r) { return l <= vl && vr <= r; }
size_t mid(size_t vl, size_t vr) { return (vl + vr + 1) / 2; }
size_t left(size_t i) { return 2 * i; }
size_t right(size_t i) { return 2 * i + 1; }
void recompute(size_t i, size_t vl, size_t vr) {
check_bounds(i, vl, vr, 0, 0);
if(vl + 1 == vr) {
data[i] = Up::update(data[i], updates[i], vl, vr);
updates[i] = Up::identity();
} else {
data[i] = Up::update(
Cm::compose(data[left(i)], data[right(i)]),
updates[i], vl, vr
);
}
}
size_t n;
std::vector<T> data;
std::vector<U> updates;
};
template<typename T, T id = 0>
struct Sum {
};
template<typename T, T id>
struct Monoid<Sum<T, id>> {
using value_type = T;
static T identity() { return id; };
static T compose(T a, T b) {
return a + b;
}
};
template<typename T, T id>
struct Updater<Sum<T, id>> : Monoid<Sum<T, id>> {
using update_type = T;
static T update(T x, T up, size_t l, size_t r) {
return x + up * (r - l);
}
};
template<typename T, T id = std::numeric_limits<T>::max()>
struct Min {
};
template<typename T, T id>
struct Monoid<Min<T, id>> {
using value_type = T;
static T identity() { return id; };
static T compose(T a, T b) {
return min(a, b);
}
};
template<typename T, const T* id = &std::numeric_limits<T>::min()>
struct Max {
};
template<typename T, const T* id>
struct Monoid<Max<T, id>> {
using value_type = T;
static T identity() { return *id; };
static T compose(T a, T b) {
return max(a, b);
}
};
//template<typename T, T* id>
//struct Updater<Max<T, id>> : Monoid<Max<T, id>> {
//
// using value_type = T;
// using update_type = T;
//
// static value_type update(value_type a, update_type b, size_t l, size_t r) {
// return max(a, b);
// }
//
//};
template<typename T, T id = 0>
struct PureSum {
};
template<typename T, T id>
struct Updater<PureSum<T, id>> : Monoid<Sum<T, id>> {
using update_type = T;
static T update(const T& a, const T& b, size_t l, size_t r) { return a + b; }
};
struct CountSegments {};
struct CSNode {
enum class Color {
BLACK,
WHITE
};
Color beg, end;
size_t black_cnt, len;
};
std::string to_str(CSNode::Color c) {
return c == CSNode::Color::BLACK ? "B" : "W";
}
bool debug = false;
template<>
struct Monoid<CountSegments> {
using value_type = CSNode;
using Color = CSNode::Color;
static value_type identity() {
return {Color::WHITE, Color::WHITE, 0, 0};
}
static value_type compose(value_type a, value_type b) {
CSNode res = {a.beg, b.end, a.black_cnt + b.black_cnt - (a.end == Color::BLACK && b.beg == Color::BLACK), a.len + b.len};
if(debug)
std::cerr << "Composing "
<< to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
<< " with "
<< to_str(b.beg) << "[" << b.black_cnt << "]" << to_str(b.end)
<< " result "
<< to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
<< std::endl;
return res;
}
};
template<>
struct Updater<CountSegments> {
using value_type = CSNode;
using update_type = std::optional<CSNode::Color>;
static update_type identity() {
return std::optional<CSNode::Color>();
}
static update_type compose(update_type a, update_type b) {
if(!b.has_value()) return a;
return b;
}
static value_type update(value_type a, update_type u, size_t l, size_t r) {
if(!u.has_value()) return a;
CSNode res = {u.value(), u.value(), u.value() == CSNode::Color::BLACK, u.value() == CSNode::Color::BLACK ? (r - l) : 0};
if(debug)
std::cerr << "Updating "
<< to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
<< " to "
<< to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
<< std::endl;
return res;
}
};
struct RectUpdater;
template<>
struct Updater<RectUpdater> : Monoid<Sum<int>> {
using value_type = pair<int, int>;
using update_type = int;
static value_type update(value_type rect, update_type k, size_t l, size_t r) {
return {rect.first + k, rect.second};
}
};
struct CountDisting {};
template<>
struct Monoid<CountDisting> {
using value_type = set<int>;
static value_type identity() {
return set<int>();
}
static value_type compose(value_type a, value_type b) {
set<int> res;
res.insert(a.begin(), a.end());
res.insert(b.begin(), b.end());
return res;
}
};
template<typename T>
struct NoUpdates {};
template<typename T>
struct Updater<NoUpdates<T>> {
using value_type = T;
using update_type = char;
static update_type identity() {
return 0;
}
static update_type compose(update_type a, update_type b) {
return 0;
}
static value_type update(value_type a, update_type b, size_t l, size_t r) {
return a;
}
};
template<typename Op, typename Up>
struct ComplexOp {
};
template<typename Op, typename Up>
struct STOp<ComplexOp<Op, Up>> {
using composer = ValidMonoid<typename STOp<Op>::composer>;
using updater = ValidUpdater<typename STOp<Up>::updater>;
};
using sum_type = size_t;
constexpr pair<sum_type, int> identity{0, -1};
int main() {
int n = readInt();
std::vector<set<int>> data;
data.reserve(n);
for (int i = 0; i < n; ++i) {
data.push_back(set<int>{readInt()});
}
SegmentTree<ComplexOp<CountDisting, NoUpdates<set<int>>>> tree(data);
int k = readInt();
std::vector<std::tuple<int, int, int>> events;
for (int i = 0; i < k; ++i) {
int l = readInt(), r = readInt();
writeInt(tree.compute(l - 1, r).size(), '\n');
}
}
//int main() {
// int n = readInt();
// std::vector<std::tuple<int, int, int, int, int, int>> events;
// for (int i = 0; i < n; ++i) {
// int x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt(), k = readInt();
// events.emplace_back(x1, 0, y1, y2, k, i);
// events.emplace_back(x2, 2, y1, y2, k, i);
// }
// sort(events.begin(), events.end());
// std::vector<int> coords{(int) -2e9, (int) 2e9};
// for (auto [x, type, y1, y2, k, i] : events) {
// coords.push_back(y1 - 1);
// coords.push_back(y1 * 1);
// coords.push_back(y2 * 1);
// }
// sort(coords.begin(), coords.end());
// coords.erase(unique(coords.begin(), coords.end()), coords.end());
// std::vector<pair<sum_type, int>> rects(n);
// size_t N = coords.size();
// SegmentTree<Max<pair<sum_type, int>, &identity>> tree(N);
// for(auto [x, type, y1, y2, k, i] : events) {
// y1 = lower_bound(coords.begin(), coords.end(), y1) - coords.begin();
// y2 = lower_bound(coords.begin(), coords.end(), y2) - coords.begin();
// switch(type) {
// case 0: {
// rects[i] = tree.compute(y2, N); //y2_new < y1_old
// rects[i].first += k;
// break;
// }
// case 2: {
// tree.update(y1 - 1, y1, {rects[i].first, i});
// break;
// }
// }
// }
// int maxI = 0;
// for (int i = 0; i < n; ++i) {
// if(rects[i].first > rects[maxI].first) {
// maxI = i;
// }
// }
// std::vector<int> chain;
// for(int i = maxI; i != -1; i = rects[i].second) {
// chain.push_back(i);
// }
// std::reverse(chain.begin(), chain.end());
// writeInt(rects[maxI].first, '\n');
// for(int i : chain) {
// writeInt(i + 1, ' ');
// }
// writeChar('\n');
//}
// x1 y1 x2 y2
// a1 b1 a2 b2
// a1 > x2 && b2 < y1
//WWWWWWWWWWW
//WWWWWWWWWWW
//WWBBWWWWWWW
//WWBBBBWWWWW
//WWBBBBWWWWW
//WWBBBBWBBWW
//WWBWBBWBBWW
//WWWWWWWWWWW
//int main() {
// int n = readInt();
// int N = 1000002;
// SegmentTree<CountSegments> tree(N);
// for (int i = 0; i < n; ++i) {
// debug = i == 5;
// int color = readChar(), x = readInt(), l = readInt();
// x += 500000;
// tree.update(x, x+l, color == 'W' ? CSNode::Color::WHITE : CSNode::Color::BLACK);
// CSNode ans = tree.compute(0, N);
// writeInt(ans.black_cnt, ' ');
// writeInt(ans.len, '\n');
// }
//}
//int main() {
// int n = readInt(), q = readInt();
// vector<int> v;
// v.reserve(n);
// for (int i = 0; i < n; ++i) {
// v.push_back(readInt());
// }
// SegmentTree<ComplexOp<Max<ll, static_cast<ll>(-1e15)>, PureSum<ll>>> tree(v);
// for (int i = 0; i < q; ++i) {
// int cmd = readChar();
// readChar();
// readChar();
// int l = readInt() - 1, r = readInt();
// if (cmd == 'm') {
// writeInt(tree.compute(l, r), '\n');
// } else {
// int x = readInt();
// tree.update(l, r, x);
// }
// }
// return 0;
//}
Comments