結果
| 問題 | No.1270 Range Arrange Query |
| ユーザー |
 kimiyuki
|
| 提出日時 | 2020-10-23 23:17:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3,239 ms / 7,000 ms |
| コード長 | 13,958 bytes |
| コンパイル時間 | 3,364 ms |
| コンパイル使用メモリ | 227,896 KB |
| 最終ジャッジ日時 | 2025-01-15 14:00:44 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
ソースコード
#line 1 "main.cpp"#include <bits/stdc++.h>#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-basedassert (0 <= i and i < n);a[i + n - 1] = b;for (i = (i + n) / 2; i > 0; i /= 2) { // 1-baseda[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 recursionif (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-basedassert (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-baseda[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-basedassert (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-baseda[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-baseda[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 commutativerange_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 recursionif (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 4 "/home/user/Library/monoids/min.hpp"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 8 "main.cpp"using namespace std;// 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 queriesint sq_n = sqrt(n);std::vector<int> order(m);iota(ALL(order), 0);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 make_pair(l_i / sq_n, r_i) < make_pair(l_j / sq_n, r_j);});// compute queriesvector<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;}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;// inputint n;const vector<int64_t>& a;// staticunordered_map<int64_t, int> compress;int k;vector<int64_t> dp_l;vector<int64_t> dp_r;// dynamicint 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 compressvector<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 leftdp_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 rightdp_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);}// dynamicl = 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];ans += dp_r[r];ans += value_lr;ans += (int64_t)(r - l) * segtree_m.range_get(0, k);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;}