結果
| 問題 | No.1270 Range Arrange Query |
| ユーザー |
 kimiyuki
|
| 提出日時 | 2020-10-23 23:22:09 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 3,053 ms / 7,000 ms |
| コード長 | 14,542 bytes |
| コンパイル時間 | 2,198 ms |
| コンパイル使用メモリ | 137,880 KB |
| 実行使用メモリ | 6,116 KB |
| 最終ジャッジ日時 | 2024-07-21 13:16:13 |
| 合計ジャッジ時間 | 16,776 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 188 ms
5,376 KB |
| testcase_07 | AC | 1,746 ms
5,376 KB |
| testcase_08 | AC | 238 ms
5,376 KB |
| testcase_09 | AC | 1,050 ms
5,376 KB |
| testcase_10 | AC | 1,040 ms
5,376 KB |
| testcase_11 | AC | 3,053 ms
5,376 KB |
| testcase_12 | AC | 3,020 ms
5,376 KB |
| testcase_13 | AC | 2,993 ms
5,376 KB |
| testcase_14 | AC | 82 ms
6,116 KB |
| testcase_15 | AC | 94 ms
6,116 KB |
| testcase_16 | AC | 105 ms
6,116 KB |
| testcase_17 | AC | 105 ms
5,376 KB |
ソースコード
#line 1 "main.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1270"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
#line 2 "/home/user/Library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 6 "/home/user/Library/data_structure/segment_tree.hpp"
/**
* @brief Segment Tree / セグメント木 (monoids, 完全二分木)
* @docs data_structure/segment_tree.md
* @tparam Monoid (commutativity is not required)
*/
template <class Monoid>
struct segment_tree {
typedef typename Monoid::value_type value_type;
Monoid mon;
int n;
std::vector<value_type> a;
segment_tree() = default;
segment_tree(int n_, const Monoid & mon_ = Monoid()) : mon(mon_) {
n = 1; while (n < n_) n *= 2;
a.resize(2 * n - 1, mon.unit());
}
void point_set(int i, value_type b) { // 0-based
assert (0 <= i and i < n);
a[i + n - 1] = b;
for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
a[i - 1] = mon.mult(a[2 * i - 1], a[2 * i]);
}
}
value_type range_get(int l, int r) { // 0-based, [l, r)
assert (0 <= l and l <= r and r <= n);
value_type lacc = mon.unit(), racc = mon.unit();
for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
if (l % 2 == 1) lacc = mon.mult(lacc, a[(l ++) - 1]);
if (r % 2 == 1) racc = mon.mult(a[(-- r) - 1], racc);
}
return mon.mult(lacc, racc);
}
value_type point_get(int i) { // 0-based
assert (0 <= i and i < n);
return a[i + n - 1];
}
/**
* @note O(min(n, (r - l) log n))
*/
void range_set(int l, int r, value_type b) {
assert (0 <= l and l <= r and r <= n);
range_set(0, 0, n, l, r, b);
}
void range_set(int i, int il, int ir, int l, int r, value_type b) {
if (l <= il and ir <= r and ir - il == 1) { // 0-based
a[i] = b;
} else if (ir <= l or r <= il) {
// nop
} else {
range_set(2 * i + 1, il, (il + ir) / 2, l, r, b);
range_set(2 * i + 2, (il + ir) / 2, ir, l, r, b);
a[i] = mon.mult(a[2 * i + 1], a[2 * i + 2]);
}
}
/**
* @brief a fast & semigroup-friendly version constructor
* @note $O(n)$
*/
template <class InputIterator>
segment_tree(InputIterator first, InputIterator last, const Monoid & mon_ = Monoid()) : mon(mon_) {
int size = std::distance(first, last);
n = 1; while (n < size) n *= 2;
a.resize(2 * n - 1, mon.unit());
std::copy(first, last, a.begin() + (n - 1));
unsafe_rebuild();
}
/**
* @brief update a leaf node without updating ancestors
* @note $O(1)$
*/
void unsafe_point_set(int i, value_type b) { // 0-based
assert (0 <= i and i < n);
a[i + n - 1] = b;
}
/**
* @brief re-build non-leaf nodes from leaf nodes
* @note $O(n)$
*/
void unsafe_rebuild() {
REP_R (i, n - 1) {
a[i] = mon.mult(a[2 * i + 1], a[2 * i + 2]);
}
}
};
#line 4 "/home/user/Library/data_structure/lazy_propagation_segment_tree.hpp"
#include <type_traits>
#line 7 "/home/user/Library/data_structure/lazy_propagation_segment_tree.hpp"
/**
* @brief Lazy Propagation Segment Tree / 遅延伝播セグメント木 (monoids, 完全二分木)
* @docs data_structure/lazy_propagation_segment_tree.md
* @tparam MonoidX is a monoid
* @tparam MonoidF is a monoid
* @tparam Action is a function phi : F * X -> X where the partial applied phi(f, -) : X -> X is a homomorphism on X
*/
template <class MonoidX, class MonoidF, class Action>
struct lazy_propagation_segment_tree {
static_assert (std::is_invocable_r<typename MonoidX::value_type, Action, typename MonoidF::value_type, typename MonoidX::value_type>::value, "");
typedef typename MonoidX::value_type value_type;
typedef typename MonoidF::value_type operator_type;
MonoidX mon_x;
MonoidF mon_f;
Action act;
int n;
std::vector<value_type> a;
std::vector<operator_type> f;
lazy_propagation_segment_tree() = default;
lazy_propagation_segment_tree(int n_, const MonoidX & mon_x_ = MonoidX(), const MonoidF & mon_f_ = MonoidF(), const Action & act_ = Action())
: mon_x(mon_x_), mon_f(mon_f_), act(act_) {
n = 1; while (n < n_) n *= 2;
a.resize(2 * n - 1, mon_x.unit());
f.resize(n - 1, mon_f.unit());
}
template <class InputIterator>
lazy_propagation_segment_tree(InputIterator first, InputIterator last, const MonoidX & mon_x_ = MonoidX(), const MonoidF & mon_f_ = MonoidF(), const Action & act_ = Action())
: mon_x(mon_x_), mon_f(mon_f_), act(act_) {
int size = std::distance(first, last);
n = 1; while (n < size) n *= 2;
a.resize(2 * n - 1, mon_x.unit());
f.resize(n - 1, mon_f.unit());
std::copy(first, last, a.begin() + (n - 1));
REP_R (i, n - 1) {
a[i] = mon_x.mult(a[2 * i + 1], a[2 * i + 2]);
}
}
void point_set(int i, value_type b) {
range_set(i, i + 1, b);
}
/**
* @note O(min(n, (r - l) log n))
*/
void range_set(int l, int r, value_type b) {
assert (0 <= l and l <= r and r <= n);
range_set(0, 0, n, l, r, b);
}
void range_set(int i, int il, int ir, int l, int r, value_type b) {
if (l <= il and ir <= r and ir - il == 1) { // 0-based
a[i] = b;
} else if (ir <= l or r <= il) {
// nop
} else {
range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
f[i] = mon_f.unit();
range_set(2 * i + 1, il, (il + ir) / 2, l, r, b);
range_set(2 * i + 2, (il + ir) / 2, ir, l, r, b);
a[i] = mon_x.mult(a[2 * i + 1], a[2 * i + 2]);
}
}
void point_apply(int i, operator_type g) {
range_apply(i, i + 1, g);
}
void range_apply(int l, int r, operator_type g) {
assert (0 <= l and l <= r and r <= n);
range_apply(0, 0, n, l, r, g);
}
void range_apply(int i, int il, int ir, int l, int r, operator_type g) {
if (l <= il and ir <= r) { // 0-based
a[i] = act(g, a[i]);
if (i < f.size()) f[i] = mon_f.mult(g, f[i]);
} else if (ir <= l or r <= il) {
// nop
} else {
range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
f[i] = mon_f.unit(); // unnecessary if the oprator monoid is commutative
range_apply(2 * i + 1, il, (il + ir) / 2, l, r, g);
range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, g);
a[i] = mon_x.mult(a[2 * i + 1], a[2 * i + 2]);
}
}
value_type point_get(int i) {
return range_get(i, i + 1);
}
value_type range_get(int l, int r) {
assert (0 <= l and l <= r and r <= n);
if (l == 0 and r == n) return a[0];
value_type lacc = mon_x.unit(), racc = mon_x.unit();
for (int l1 = (l += n), r1 = (r += n) - 1; l1 > 1; l /= 2, r /= 2, l1 /= 2, r1 /= 2) { // 1-based loop, 2x faster than recursion
if (l < r) {
if (l % 2 == 1) lacc = mon_x.mult(lacc, a[(l ++) - 1]);
if (r % 2 == 1) racc = mon_x.mult(a[(-- r) - 1], racc);
}
lacc = act(f[l1 / 2 - 1], lacc);
racc = act(f[r1 / 2 - 1], racc);
}
return mon_x.mult(lacc, racc);
}
};
#line 3 "/home/user/Library/monoids/min.hpp"
#include <limits>
template <class T>
struct min_monoid {
typedef T value_type;
value_type unit() const { return std::numeric_limits<T>::max(); }
value_type mult(value_type a, value_type b) const { return std::min(a, b); }
};
#line 2 "/home/user/Library/monoids/plus.hpp"
template <class T>
struct plus_monoid {
typedef T value_type;
value_type unit() const { return value_type(); }
value_type mult(value_type a, value_type b) const { return a + b; }
};
#line 4 "/home/user/Library/monoids/plus_min_action.hpp"
template <class T>
struct plus_min_action {
typename min_monoid<T>::value_type operator () (typename plus_monoid<T>::value_type f, typename min_monoid<T>::value_type x) const {
return (x == min_monoid<T>().unit() ? x : f + x);
}
};
#line 3 "/home/user/Library/utils/mo_algorithm.hpp"
#include <cmath>
#include <numeric>
#include <tuple>
#line 8 "/home/user/Library/utils/mo_algorithm.hpp"
// struct mo_struct {
// typedef int64_t value_type;
// typedef int64_t result_type;
// void add_right(int nr, value_type x_r) {
// }
// void add_left(int nl, value_type x_nl) {
// }
// void remove_right(int nr, value_type x_nr) {
// }
// void remove_left(int nl, value_type x_l) {
// }
// result_type query() {
// return 0;
// }
// };
template <class Mo>
std::vector<typename Mo::result_type> run_mo_algorithm(Mo mo, const std::vector<typename Mo::value_type>& values, const std::vector<std::pair<int, int> >& queries) {
int n = values.size();
int m = queries.size();
// sort queries
int sq_n = std::sqrt(n);
std::vector<int> order(m);
std::iota(ALL(order), 0);
std::sort(ALL(order), [&](int i, int j) {
int l_i, r_i; std::tie(l_i, r_i) = queries[i];
int l_j, r_j; std::tie(l_j, r_j) = queries[j];
return std::make_pair(l_i / sq_n, r_i) < std::make_pair(l_j / sq_n, r_j);
});
// compute queries
std::vector<typename Mo::result_type> ans(m);
int l = 0;
int r = 0;
for (int j : order) {
int nl, nr; std::tie(nl, nr) = queries[j];
for (; r < nr; ++ r) mo.add_right(r + 1, values[r]);
for (; nl < l; -- l) mo.add_left(l - 1, values[l - 1]);
for (; nr < r; -- r) mo.remove_right(r - 1, values[r - 1]);
for (; l < nl; ++ l) mo.remove_left(l + 1, values[l]);
ans[j] = mo.query();
}
return ans;
}
#line 15 "main.cpp"
using namespace std;
struct mo_struct {
typedef int64_t value_type;
typedef int64_t result_type;
private:
typedef segment_tree<plus_monoid<int> > plus_segtree_type;
typedef lazy_propagation_segment_tree<min_monoid<int64_t>, plus_monoid<int64_t>, plus_min_action<int64_t> > plus_min_segtree_type;
// input
int n;
const vector<int64_t>& a;
// static
unordered_map<int64_t, int> compress;
int k;
vector<int64_t> dp_l;
vector<int64_t> dp_r;
// dynamic
int l;
int r;
int64_t value_lr;
plus_segtree_type segtree_l;
plus_min_segtree_type segtree_m;
plus_segtree_type segtree_r;
public:
mo_struct(const vector<int64_t>& a_)
: n(a_.size())
, a(a_) {
// static compress
vector<int64_t> sorted_a = a;
sort(ALL(sorted_a));
for (int64_t a_i : sorted_a) {
compress.emplace(a_i, compress.size());
}
k = compress.size();
// static left
dp_l.resize(n + 1);
segtree_l = plus_segtree_type(k);
segtree_l.range_set(0, k, 0);
REP (i, n) {
dp_l[i + 1] = dp_l[i] + segtree_l.range_get(compress[a[i]] + 1, k);
segtree_l.point_set(compress[a[i]], segtree_l.point_get(compress[a[i]]) + 1);
}
segtree_l = plus_segtree_type(k);
segtree_l.range_set(0, k, 0);
// static right
dp_r.resize(n + 1);
segtree_r = plus_segtree_type(k);
segtree_r.range_set(0, k, 0);
REP_R (i, n) {
dp_r[i] = dp_r[i + 1] + segtree_r.range_get(0, compress[a[i]]);
segtree_r.point_set(compress[a[i]], segtree_r.point_get(compress[a[i]]) + 1);
}
// dynamic
l = 0;
r = 0;
value_lr = 0;
segtree_m = plus_min_segtree_type(k);
segtree_m.range_set(0, k, 0);
REP (i, n) {
segtree_m.range_apply(compress[a[i]] + 1, k, 1);
}
}
void add_right(int nr, int64_t x_r) {
assert (nr == r + 1);
int y = compress[x_r];
value_lr -= segtree_l.range_get(y + 1, k);
segtree_m.range_apply(y + 1, k, -1);
segtree_r.point_set(y, segtree_r.point_get(y) - 1);
r = nr;
}
void add_left(int nl, int64_t x_nl) {
assert (nl == l - 1);
int y = compress[x_nl];
value_lr -= segtree_r.range_get(0, y);
segtree_l.point_set(y, segtree_l.point_get(y) - 1);
segtree_m.range_apply(0, y, -1);
l = nl;
}
void remove_right(int nr, int64_t x_nr) {
assert (nr == r - 1);
int y = compress[x_nr];
value_lr += segtree_l.range_get(y + 1, k);
segtree_m.range_apply(y + 1, k, 1);
segtree_r.point_set(y, segtree_r.point_get(y) + 1);
r = nr;
}
void remove_left(int nl, int64_t x_l) {
assert (nl == l + 1);
int y = compress[x_l];
value_lr += segtree_r.range_get(0, y);
segtree_l.point_set(y, segtree_l.point_get(y) + 1);
segtree_m.range_apply(0, y, 1);
l = nl;
}
int64_t query() {
int64_t ans = 0;
ans += dp_l[l]; // the inversion number in [0, l)
ans += dp_r[r]; // the inversion number in [r, n)
ans += value_lr; // the inversion number between [0, l) and [r, n)
ans += (int64_t)(r - l) * segtree_m.range_get(0, k); // the inversion number between [0, l) and [l, r) plus the inversion number between [l, r) and [r, n)
return ans;
}
};
vector<int64_t> solve(int n, int q, const vector<int64_t>& a, const vector<pair<int, int> >& queries) {
return run_mo_algorithm(mo_struct(a), a, queries);
}
int main() {
int n, q; cin >> n >> q;
vector<int64_t> a(n);
REP (i, n) {
cin >> a[i];
}
vector<pair<int, int> > queries(q);
REP (i, q) {
int l, r; cin >> l >> r;
-- l;
queries[i] = make_pair(l, r);
}
auto ans = solve(n, q, a, queries);
REP (i, q) {
cout << ans[i] << endl;
}
return 0;
}