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

提出ソース
結果

問題	No.925 紲星 Extra
ユーザー	lumc_
提出日時	2019-09-15 05:37:38
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE (最新) AC (最初)
実行時間	-
コード長	12,719 bytes
コンパイル時間	2,302 ms
コンパイル使用メモリ	160,120 KB
実行使用メモリ	111,304 KB
最終ジャッジ日時	2023-10-13 08:27:10
合計ジャッジ時間	8,821 ms
ジャッジサーバーID （参考情報）	judge11 / judge15
このコードへのチャレンジ
（要ログイン）
テストケース

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

raw source code
#if 0

想定TLEにしたい

seg on seg + 二分探索

直接二分探索みたいなのが存在するのかどうか，というのが気になる

#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;

#define DEBUG_OUT std::cerr

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <array>
#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
template < int n, class... T >
typename std::enable_if< (n >= sizeof...(T)) >::type __output_tuple(
    std::ostream &, std::tuple< T... > const &) {}
template < int n, class... T >
typename std::enable_if< (n < sizeof...(T)) >::type __output_tuple(
    std::ostream &os, std::tuple< T... > const &t) {
  os << (n == 0 ? "" : ", ") << std::get< n >(t);
  __output_tuple< n + 1 >(os, t);
}
template < class... T >
std::ostream &operator<<(std::ostream &os, std::tuple< T... > const &t) {
  os << "(";
  __output_tuple< 0 >(os, t);
  os << ")";
  return os;
}
template < class T, class U >
std::ostream &operator<<(std::ostream &os, std::pair< T, U > const &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template < class T >
std::ostream &operator<<(std::ostream &os, const std::stack< T > &a) {
  os << "{";
  for(auto tmp = a; tmp.size(); tmp.pop())
    os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  os << "}";
  return os;
}
template < class T, class Container, class Compare >
std::ostream &operator<<(std::ostream &os,
    std::priority_queue< T, Container, Compare > a) {
  os << "{ (top) ";
  while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template < class T, class Container >
std::ostream &operator<<(std::ostream &os, std::queue< T, Container > a) {
  os << "{ ";
  while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT std::cerr
#endif
#define dump(...)                                                                \
  [&]() {                                                                        \
    auto __debug_tap = std::make_tuple(__VA_ARGS__);                             \
    DEBUG_OUT << "[" << __LINE__ << "] " << #__VA_ARGS__ << " = " << __debug_tap \
    << std::endl;                                                      \
  }()
template < class T >
inline void dump2D(T &d, size_t sizey, size_t sizex) {
  for(size_t i = 0; i < sizey; i++) {
    DEBUG_OUT << "\t";
    for(size_t j = 0; j < sizex; j++)
      DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t");
    DEBUG_OUT << std::endl;
  }
}
template < class T >
inline void dump1D(T &d, size_t sizey) {
  for(size_t i = 0; i < sizey; i++) {
    DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " ");
  }
  DEBUG_OUT << std::endl;
}
template <
class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type,
      class = typename std::enable_if< !std::is_same< T, std::string >::value >::type >
      std::ostream &operator<<(std::ostream &os, const T &a) {
        os << "{";
        for(auto ite = begin(a); ite != end(a); ++ite)
          os << (ite == begin(a) ? "" : ", ") << *ite;
        os << "}";
        return os;
      }
#else
#define dump(...) ((void) 42)
#define dump2D(...) ((void) 42)
#define dump1D(...) ((void) 42)
template <
class T, class = typename std::iterator_traits< decltype(begin(T())) >::value_type,
      class = typename std::enable_if< !std::is_same< T, std::string >::value >::type >
      std::ostream &operator<<(std::ostream &os, const T &a) {
        for(auto ite = begin(a); ite != end(a); ++ite)
          os << (ite == begin(a) ? "" : " ") << *ite;
        return os;
      }
#endif
// }}}


// .add(i, v)   : bit[i] += v
// .get(i)      : bit[i]
// .sum(i)      : bit[0] + ... + bit[i]
// .range(l, r) : bit[l] + ... + bit[r]
// .lower_bound(T v) : min i that satisfies .sum(i) >= v
//    - use only when bit[i] >= 0 for all i > 0
/// --- Binary Indexed Tree {{{ ///
#include <cassert>
#include <vector>
template < class T = long long >
struct BinaryIndexedTree {
  using size_type = std::size_t;
  size_type n, m;
  T identity;
  std::vector< T > data;
  BinaryIndexedTree() : n(0) {}
  BinaryIndexedTree(size_type n, T identity = T())
    : n(n), identity(identity), data(n, identity) {
      m = 1;
      while(m < n) m <<= 1;
    }
  void add(size_type i, T x) {
    assert(i < n);
    i++;
    while(i <= n) {
      data[i - 1] = data[i - 1] + x;
      i += i & -i;
    }
  }
  T sum(int i) {
    if(i < 0) return identity;
    if(i >= static_cast<int>(n)) i = n - 1;
    i++;
    T s = identity;
    while(i > 0) {
      s = s + data[i - 1];
      i -= i & -i;
    }
    return s;
  }
  T get(int i) { return sum(i) - sum(i - 1); }
  T range(int a, int b) { return sum(b) - sum(a - 1); }
  size_type lower_bound(T w) {
    size_type i = 0;
    for(size_type k = m; k > 0; k >>= 1) {
      if(i + k <= n && data[i + k - 1] < w) w -= data[(i += k) - 1];
    }
    return i;
  }
};
/// }}}--- ///

template < class T = long long >
using BIT = BinaryIndexedTree< T >;



// FractionalCascadingSegmentTree
// < Under, Data [, yCompress = 1 [, Index] ] >(H, ...)
// .index(y, x)
// === init(doUnique) ===
// .set(y, x, val)         // index(y, x) must be done
// .fold(yl, yr, xl, xr)
// .fold(y, x)
// === --- ===
// only offline
/// --- Fractional Cascading SegmentTree {{{ ///
#include <algorithm>
#include <cassert>
#include <functional>
#include <map>
#include <vector>

template < class T, class U, bool yCompress = true, class Index = ll >
struct FractionalCascadingSegmentTree {
  size_t h;
  vector< T > dat;
  vector< vector< Index > > indices;
  vector< vector< size_t > > L, R;
  U identity;
  function< void(T &, int x, const U &) > setX;
  function< void(T &, vector< Index > &) > initX;
  function< U(T &, int x1, int x2) > foldX;
  function< U(const U &, const U &) > mergeY;
  FractionalCascadingSegmentTree() {}
  FractionalCascadingSegmentTree(size_t tempH, //
      const function< void(T &, int, const U &) > &setX,
      const function< void(T &, vector< Index > &) > &initX,
      const function< U(T &, int, int) > &foldX,
      const function< U(const U &, const U &) > &mergeY,
      U identity = U(), T initial = T())
    : identity(identity), setX(setX), initX(initX), foldX(foldX), mergeY(mergeY) {
      h = 1;
      while(h < tempH) h <<= 1;
      dat = vector< T >(2 * h, initial);
      indices = vector< vector< Index > >(2 * h);
      L = R = vector< vector< size_t > >(2 * h);
    }
  vector< Index > ys;
  map< Index, int > ymap;
  vector< pair< Index, Index > > pre_indecies;
  void index(Index i, Index j) {
    if(yCompress) {
      ys.push_back(i);
      pre_indecies.emplace_back(i, j);
    } else {
      size_t i2 = i;
      assert(i2 < h);
      indices[i2 + h].push_back(j);
    }
  }
  void init(bool doUnique) {
    if(yCompress) {
      sort(begin(ys), end(ys));
      ys.erase(unique(begin(ys), end(ys)), end(ys));
      {
        size_t i = 0;
        for(Index &y : ys) ymap[y] = i++;
      }
      for(pair< Index, Index > idx : pre_indecies) {
        indices[ymap[idx.first] + h].push_back(idx.second);
      }
    }
    for(size_t i = h; i < h * 2; i++) {
      sort(begin(indices[i]), end(indices[i]));
      if(doUnique)
        indices[i].erase(unique(begin(indices[i]), end(indices[i])), end(indices[i]));
      initX(dat[i], indices[i]);
    }
    for(size_t i = h - 1; i >= 1; i--) {
      size_t lsz = indices[i * 2].size();
      size_t rsz = indices[i * 2 + 1].size();
      size_t nsz = lsz + rsz;
      indices[i].resize(nsz);
      L[i].resize(nsz + 1, lsz);
      R[i].resize(nsz + 1, rsz);
      size_t p1 = 0, p2 = 0;
      while(p1 < lsz || p2 < rsz) {
        L[i][p1 + p2] = p1;
        R[i][p1 + p2] = p2;
        if(p1 < lsz && (p2 == rsz || indices[i * 2][p1] <= indices[i * 2 + 1][p2])) {
          indices[i][p1 + p2] = indices[i * 2][p1];
          p1++;
        } else {
          indices[i][p1 + p2] = indices[i * 2 + 1][p2];
          p2++;
        }
      }
      initX(dat[i], indices[i]);
    }
  }

public:
  void set(Index y, Index x, const U &val) {
    if(yCompress) {
      assert(ymap.count(y));
      _set(ymap[y], x, val);
    } else {
      size_t y2 = y;
      assert(y2 < h);
      _set(y2, x, val);
    }
  }

private:
  void _set(size_t y, Index x, const U &val) {
    size_t lower = lower_bound(begin(indices[1]), end(indices[1]), x) - begin(indices[1]);
    assert(lower < indices.size());
    size_t k = 1, l = 0, r = h;
    while(k != y + h) {
      setX(dat[k], lower, val);
      size_t mid = (l + r) >> 1;
      if(y < mid) {
        lower = L[k][lower];
        k = k * 2;
        r = mid;
      } else {
        lower = R[k][lower];
        k = k * 2 + 1;
        l = mid;
      }
    }
    setX(dat[k], lower, val);
    assert(indices[k][lower] == x);
  }

public:
  U fold(Index y, Index x) { return fold(y, y + Index(1), x, x + Index(1)); }
  U fold(Index a, Index b, Index l, Index r) {
    if(a >= b || l >= r) return identity;
    size_t lower = lower_bound(begin(indices[1]), end(indices[1]), l) - begin(indices[1]);
    size_t upper = lower_bound(begin(indices[1]), end(indices[1]), r) - begin(indices[1]);
    size_t a2, b2;
    if(yCompress) {
      a2 = lower_bound(begin(ys), end(ys), a) - begin(ys);
      b2 = lower_bound(begin(ys), end(ys), b) - begin(ys);
    } else {
      a2 = a, b2 = b;
      assert(a2 < h && b2 <= h);
    }
    return fold(a2, b2, lower, upper, 0, h, 1);
  }

private:
  U fold(size_t a, size_t b, size_t lower, size_t upper, size_t l, size_t r, size_t k) {
    if(lower == upper) return identity;
    if(b <= l || r <= a) return identity;
    if(a <= l && r <= b) return foldX(dat[k], lower, upper);
    return mergeY(fold(a, b, L[k][lower], L[k][upper], l, (l + r) >> 1, k * 2),
        fold(a, b, R[k][lower], R[k][upper], (l + r) >> 1, r, k * 2 + 1));
  }
};

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


constexpr int N = 4e5;
constexpr int Q = 4e5;


using Under = pair<BIT<>, BIT<int>>;
using Value = ll;
using Data = pair<ll, int>;



constexpr int inf = 1e9;

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

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

FractionalCascadingSegmentTree< Under, Data, 1 > ecas(
    n + q + 1,
    // set x
    [](Under &dat, int x, const Data &val) -> void {
    // dat.add(x, -dat.get(x) + val);
    dat.first.add(x, val.first);
    dat.second.add(x, val.second);
    },
    // init x
    [](Under &dat, const vector< ll > &indices) -> void {
    dat = Under(BIT<>(indices.size()), BIT<int>(indices.size())); // serve initial?
    },
    // fold [l, r) // l < r
    [](Under &dat, int l, int r) -> Data { return Data(dat.first.range(l, r - 1), dat.second.range(l, r - 1)); },
    // merge y-direction
    [](Data a, Data b) -> Data { return Data(a.first + b.first, a.second + b.second); }
    // optional identity
    // , identity
    );

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

  for(int i = 0; i < n; i++) ecas.index(v[i], i);

  auto w = v;

  for(int i = 0; i < q; i++) {
    if(t[i] == 1) { // update
      ecas.index(r[i], l[i]);
    } else { // query
    }
  }

  dump(3);
  ecas.init(1);

  dump(4);

  for(int i = 0; i < n; i++) ecas.set(v[i], i, Data(v[i], 1));

  dump(5);

  for(int i = 0; i < q; i++) {
    if(t[i] == 1) { // update
      ecas.set(v[l[i]], l[i], Data(-v[l[i]], -1));
      ecas.set(r[i], l[i], Data(r[i], 1));
      v[l[i]] = r[i];
    } else { // query
      int len = r[i] - l[i];

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

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

      ll z = -ecas.fold(-inf, med[i], l[i], r[i]).first + ecas.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];
      }
      cout << z << "\n";
    }
  }

  return 0;
}
yukicoder

結果

テストケース

ソースコード
