DisjointSparseTable
概要
静的配列の区間に対するクエリに前計算$ O(NlogN)で$ O(1)で答えることができるデータ構造。
使用例
乗せる要素の型と演算をクラスで定義する。基本的にそこを書き換えれば動く。
code:cpp
template <class Semigroup> class disjoint_sparse_table {
public:
using value_structure = Semigroup;
using value_type = typename value_structure::value_type;
private:
using container_type = ::std::vector<::std::vector<value_type>>;
public:
using const_reference = typename container_type::value_type::const_reference;
using size_type = typename container_type::value_type::size_type;
protected:
static size_type msb(size_type c) {
return 31 - __builtin_clz(c);
::std::size_t ret = 0;
if (c >> 16)
c >>= 16, ret += 16;
if (c >> 8)
c >>= 8, ret += 8;
if (c >> 4)
c >>= 4, ret += 4;
if (c >> 2)
c >>= 2, ret += 2;
return ret + (c >> 1);
}
container_type table;
public:
disjoint_sparse_table() : table() {}
template <class InputIterator>
disjoint_sparse_table(InputIterator first, InputIterator last) : table() {
table.emplace_back(first, last);
const size_type size = table.front().size();
for (size_type i = 2; i < size; i <<= 1) {
typename container_type::value_type v;
v.reserve(size);
for (size_type j = i; j < size; j += i << 1) {
v.emplace_back(table.front()j - 1); for (size_type k = 2; k <= i; ++k)
v.emplace_back(
value_structure::operation(table.front()j - k, v.back())); v.emplace_back(table.front()j); for (size_type k = 1; k < i && j + k < size; ++k)
v.emplace_back(
value_structure::operation(v.back(), table.front()j + k)); }
table.emplace_back(::std::move(v));
}
}
size_type size() const { return table.empty() ? 0 : table.front().size(); }
bool empty() const { return size() == 0; }
value_type fold_closed(const size_type first, const size_type last) const {
assert(first <= last);
assert(last < size());
if (first == last) {
return table.front()first; } else {
const size_type p = msb(first ^ last);
return value_structure::operation(
}
}
const_reference operator[](const size_type index) const {
assert(index < size());
return table.front()index; }
};
template <class T> class min_semigroup {
public:
using value_type = T;
static value_type operation(const value_type &x, const value_type &y) {
return ::std::min(x, y);
}
};
bool solve(){
LL(n);
vector<ll>a(n);cin >> a;
disjoint_sparse_table<min_semigroup<ll>>dst(ALL(a));
ll ans{};
chmax(ans,max(a));
rep(i,n)rep(j,i+1,n){
chmax(ans,dst.fold_closed(i,j)*(j-i+1));
}
O(ans);
return 0;
}