#380160 (C++14) No.925 紲星 Extra

提出ソース
結果

問題	No.925 紲星 Extra
ユーザー	lumc_
提出日時	2019-09-17 19:17:43
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	12,510 bytes
コンパイル時間	1,645 ms
コンパイル使用メモリ	122,476 KB
実行使用メモリ	814,592 KB
最終ジャッジ日時	2024-09-15 05:46:55
合計ジャッジ時間	5,265 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	3 ms 6,940 KB
testcase_03	AC	90 ms 39,808 KB
testcase_04	AC	93 ms 35,436 KB
testcase_05	MLE	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#if 0

たぶん想定 MLE もしくは TLE
メモリでたぶん落ちると思われる
2^17 * 40 * 40 * 8 byte ~ 1600 MB ぐらい？ 実際はこの数倍必要なはず

dynamic seg on dynamic seg + 二分探索

たぶん

space  : O((N + Q) lg^2 A)
time   : O(N lg^2 N + Q lg^3 N)

#endif
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

constexpr ll inf = 1ll << 40;

// - scalable
//    DynamicSegmentTree([ <initial> ])
// - fixed-range
//    DynamicSegmentTree(L, R [, <initial> ])
//    DynamicSegmentTree(size [, <initial> ])
// === initial values ===
// <initial> := one value or function
// when you feed initial-one-value : O(log^2 N) time / query
// when you feed initial-function
//    : O(timeof(f(l, r)) log N) time / query
// === --- ===
// NOTE : one value is recommended rather than O(log SIZE) function
// NOTE : better to use fixed-range
/// --- Dynamic SegmentTree {{{ ///
#include <cassert>
#include <functional>
#include <memory>
template < class Monoid >
struct DynamicSegmentTreeNode {
public:
  using T = typename Monoid::T;
  using node_type = DynamicSegmentTreeNode;
  using pointer = node_type *;
  T value;
  pointer l = 0, r = 0;
  DynamicSegmentTreeNode(T value = Monoid::identity()) : value(value) {}
  DynamicSegmentTreeNode(pointer l, pointer r) : l(l), r(r) {}
};

template < class Monoid,
         class Allocator = std::allocator< DynamicSegmentTreeNode< Monoid > > >
         struct DynamicSegmentTree {
         public:
           using T = typename Monoid::T;
           using size_type = long long;
           using node_type = DynamicSegmentTreeNode< Monoid >;
           using pointer = node_type *;
           using func_type = std::function< T(size_type l, size_type r) >;

         private:
           static Allocator alc;
           pointer top = 0;
           // it should be only given positive length ranges
           func_type get_initial = [](...) { return Monoid::identity(); };
           const bool range_fixed;
           size_type L, R;

           void expand(size_type t) {
             assert(!range_fixed);
             while(t < L || R <= t) {
               if(R == static_cast< size_type >(0))
                 R = 1;
               else {
                 R <<= 1;
                 if(top) {
                   pointer new_l = 0, new_r = 0;
                   if(top->l)
                     std::allocator_traits< Allocator >::construct(
                         alc, new_l = alc.allocate(1), nullptr, top->l);
                   if(top->r)
                     std::allocator_traits< Allocator >::construct(
                         alc, new_r = alc.allocate(1), top->r, nullptr);
                   top->l = new_l, top->r = new_r;
                   if(new_l) update(new_l, -R, 0);
                   if(new_r) update(new_r, 0, R);
                   update(top, -R, R);
                 }
               }
               L = -R;
             }
           }

           void update(pointer node, size_type l, size_type r) {
             assert(node && r - l >= 2);
             node->value = Monoid::op(node->l ? node->l->value : get_initial(l, (l + r) / 2),
                 node->r ? node->r->value : get_initial((l + r) / 2, r));
           }

         public:
           // scalable
           DynamicSegmentTree() : range_fixed(0), L(0), R(0) {}
           DynamicSegmentTree(const T &initial) : DynamicSegmentTree() { set_initial(initial); }
           DynamicSegmentTree(const func_type &get_initial) : DynamicSegmentTree() {
             this->get_initial = get_initial;
           }
           // [L, R)
           DynamicSegmentTree(size_type L, size_type R) : range_fixed(1), L(L), R(R) {
             assert(L < R);
           }
           DynamicSegmentTree(size_type L, size_type R, const T &initial)
             : DynamicSegmentTree(L, R) {
               set_initial(initial);
             }
           DynamicSegmentTree(size_type L, size_type R, const func_type &get_initial)
             : DynamicSegmentTree(L, R) {
               this->get_initial = get_initial;
             }
           // [0, R)
           DynamicSegmentTree(size_type R) : DynamicSegmentTree(0, R) {}
           DynamicSegmentTree(size_type R, const T &initial) : DynamicSegmentTree(R) {
             set_initial(initial);
           }
           DynamicSegmentTree(size_type R, const func_type &get_initial) : DynamicSegmentTree(R) {
             this->get_initial = get_initial;
           }

           void set_initial(const T &initial) {
             get_initial = [initial](size_type l, size_type r) {
               size_type n = r - l;
               n--;
               T u = initial, v = initial;
               while(n) {
                 if(n & 1) u = Monoid::op(u, v);
                 n >>= 1;
                 if(n) v = Monoid::op(v, v);
               }
               return u;
             };
           }

           void set(size_type i, const T &val) {
             if(!range_fixed)
               expand(i);
             else
               assert(L <= i && i < R);
             if(!top)
               std::allocator_traits< Allocator >::construct(
                   alc, top = alc.allocate(1), get_initial(L, R));
             set(i, val, L, R, top);
           }

         private:
           void set(size_type i, const T &val, size_type l, size_type r, pointer node) {
             assert(node);
             if(r - l == 1) {
               node->value = val;
               return;
             }
             size_type m = (l + r) / 2;
             if(i < m) {
               if(!node->l)
                 std::allocator_traits< Allocator >::construct(
                     alc, node->l = alc.allocate(1), get_initial(l, m));
               set(i, val, l, m, node->l);
             } else {
               if(!node->r)
                 std::allocator_traits< Allocator >::construct(
                     alc, node->r = alc.allocate(1), get_initial(m, r));
               set(i, val, m, r, node->r);
             }
             update(node, l, r);
           }

         public:
           T fold(size_type l, size_type r) {
             if(range_fixed) {
               if(l < L) l = L;
               if(R < r) r = R;
             }
             if(l >= r) return Monoid::identity();
             if(!range_fixed) {
               if(r < L || R < l) return get_initial(l, r);
               if(l < L) return Monoid::op(get_initial(l, L), fold(L, r));
               if(R < r) return Monoid::op(fold(l, R), get_initial(R, r));
             }
             return fold(l, r, L, R, top);
           }
           T get(size_type i) {
             if(range_fixed) assert(L <= i && i < R);
             return fold(i, i + 1);
           }

         private:
           T fold(size_type a, size_type b, size_type l, size_type r, pointer node) {
             if(b <= l || r <= a) return Monoid::identity();
             if(!node)
               return get_initial(std::max< size_type >(a, l), std::min< size_type >(b, r));
             if(a <= l && r <= b) return node->value;
             return Monoid::op(
                 fold(a, b, l, (l + r) / 2, node->l), fold(a, b, (l + r) / 2, r, node->r));
           }
         };
template < class Monoid, class Allocator >
Allocator DynamicSegmentTree< Monoid, Allocator >::alc;
/// }}}--- ///

/// --- Monoid examples {{{ ///
constexpr long long inf_monoid = 1e18 + 100;
#include <algorithm>
struct Nothing {
  using T = char;
  using Monoid = Nothing;
  using M = T;
  static constexpr T op(const T &, const T &) { return T(); }
  static constexpr T identity() { return T(); }
  template < class X >
    static constexpr X actInto(const M &, long long, const X &x) {
      return x;
    }
};

template < class U = long long >
struct RangeMin {
  using T = U;
  static T op(const T &a, const T &b) { return std::min< T >(a, b); }
  static constexpr T identity() { return T(inf_monoid); }
};

template < class U = long long >
struct RangeMax {
  using T = U;
  static T op(const T &a, const T &b) { return std::max< T >(a, b); }
  static constexpr T identity() { return T(-inf_monoid); }
};

template < class U = long long >
struct RangeSum {
  using T = U;
  static T op(const T &a, const T &b) { return T(a.first + b.first, a.second + b.second); }
  static constexpr T identity() { return T(0, 0); }
};

template < class U >
struct RangeProd {
  using T = U;
  static T op(const T &a, const T &b) { return a * b; }
  static constexpr T identity() { return T(1); }
};

template < class U = long long >
struct RangeOr {
  using T = U;
  static T op(const T &a, const T &b) { return a | b; }
  static constexpr T identity() { return T(0); }
};

#include <bitset>

template < class U = long long >
struct RangeAnd {
  using T = U;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return T(-1); }
};

template < size_t N >
struct RangeAnd< std::bitset< N > > {
  using T = std::bitset< N >;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return std::bitset< N >().set(); }
};

/// }}}--- ///

using Seg = DynamicSegmentTree< RangeSum<pair<ll, ll>> >;

using P = pair<ll, ll>;

P op(P a, P b) {
  a.first += b.first;
  a.second += b.second;
  return a;
}

template<class T = long long, class Index = long long>
struct DynamicSegmentTree2D {
  Index L, R;
  struct Node {
    Seg seg;
    Node *l = 0, *r = 0;
    Node() {}
  };
  Node *p = 0;
  DynamicSegmentTree2D(Index L, Index R): L(L), R(R) { }

  void upd(Seg& seg, Index x, T v) {
    auto w = seg.get(x);
    w.first += v.first;
    w.second += v.second;
    seg.set(x, w);
  }

public:
  void add(Index y, Index x, T v) {
    assert(L <= y && y < R);
    add(p, L, R, y, x, v);
  }
private:
  void add(Node*& t, Index a, Index b, Index y, Index x, T v) {
    if(!t) t = new Node;
    upd(t->seg, x, v);
    if(a == y && y + 1 == b) return;
    Index mid = (a + b) / 2;
    if(y < mid) add(t->l, a, mid, y, x, v);
    else add(t->r, mid, b, y, x, v);
  }
public:
  T fold(Index yl, Index yr, Index xl, Index xr) {
    if(yl < L) yl = L;
    if(yr > R) yl = R;
    if(yl >= yr) return T();
    if(xl >= xr) return T();
    return fold(p, L, R, yl, yr, xl, xr);
  }
private:
  T fold(Node* k, Index a, Index b, Index yl, Index yr, Index xl, Index xr) {
    if(!k) return T(0, 0);
    if(yr <= a || b <= yl) return T(0, 0);
    if(yl <= a && b <= yr) return k->seg.fold(xl, xr);
    Index mid = (a + b) / 2;
    return op(
        fold(k->l, a, mid, yl, yr, xl, xr),
        fold(k->r, mid, b, yl, yr, xl, xr)
        );
  }
};

constexpr int Q = 1 << 16;

int n, q;
ll t[Q], l[Q], r[Q];
ll med[Q], smaller[Q], bigger[Q];

using P = pair<ll, ll>;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n >> q;

  DynamicSegmentTree2D<P> dseg(0, inf);

  vector<ll> v(n);
  for(auto &e: v) cin >> e;
  for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i];

  for(int i = 0; i < n; i++) dseg.add(v[i], i, P(v[i], 1));

  ll sum16 = 0;
  ll sum40 = 0;

  for(int i = 0; i < q; i++) {
    if(t[i] == 1) { // update
      l[i] ^= sum16;
      r[i] ^= sum40;

      l[i]--;

      dseg.add(v[l[i]], l[i], P(-v[l[i]], -1));
      dseg.add(r[i], l[i], P(r[i], 1));
      v[l[i]] = r[i];
    } else { // query
      l[i] ^= sum16;
      r[i] ^= sum16;

      if(l[i] > r[i]) swap(l[i], r[i]);
      l[i]--;
 
      int len = r[i] - l[i];

      ll ok = inf - 1, ng = -1;
      while(abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        auto f1 = dseg.fold(mid + 1, inf, l[i], r[i]);
        if(f1.second <= len / 2) ok = mid; else ng = mid;
      }

      med[i] = ok;
      smaller[i] = dseg.fold(0, med[i], l[i], r[i]).second;
      bigger[i] = dseg.fold(med[i] + 1, inf, l[i], r[i]).second;

      ll z = -dseg.fold(0, med[i], l[i], r[i]).first + dseg.fold(med[i] + 1, inf, l[i], r[i]).first;

      z -= ll(len / 2 - smaller[i]) * med[i];
      z += ll((len - len / 2) - bigger[i]) * med[i];

      if(len % 2 == 0) {
      } else {
        z -= med[i];
      }

      sum16 ^= z % Q;
      sum40 ^= z % (1ll << 40);

      cout << z << "\n";
    }
  }
  return 0;
}
yukicoder

結果

テストケース

ソースコード
