#377058 (C++14) No.924 紲星

• 問題: No.924 紲星
• ユーザー: lumc_
• 提出日時: 2019-09-07 09:06:28
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 573 ms / 4,000 ms
• コード長: 13,409 bytes
• コンパイル時間: 2,005 ms
• コンパイル使用メモリ: 149,980 KB
• 実行使用メモリ: 154,096 KB
• 最終ジャッジ日時: 2024-09-15 05:33:37
• 合計ジャッジ時間: 7,942 ms
• ジャッジサーバーID （参考情報）: judge5 / 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	3 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	570 ms; 154,092 KB
testcase_09	AC	567 ms; 153,844 KB
testcase_10	AC	572 ms; 154,096 KB
testcase_11	AC	571 ms; 154,096 KB
testcase_12	AC	573 ms; 153,972 KB
testcase_13	AC	215 ms; 62,080 KB
testcase_14	AC	166 ms; 38,880 KB
testcase_15	AC	177 ms; 43,844 KB
testcase_16	AC	385 ms; 135,236 KB
testcase_17	AC	276 ms; 64,560 KB
testcase_18	AC	2 ms; 5,376 KB

ソースコード

#if 0

RangeSelect with median of medians
O(N log Q + (N + Q) log N) * O(log N)

実装が微妙に正しくなかった

ちなみに，必要になったときだけ計算するようにすると，前計算が O(N log N) から O(N log Q) になり，
O(N log Q + Q log 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>
// }}}
#include<chrono>
using namespace std;
using ll = long long;

// #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(int 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 >= 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 >;

/// --- select {{{ ///
// median of medians
#include<cstddef>
#include<vector>
#include<functional>
template <class T>
T select(std::vector<T> a, std::size_t k) {
  assert(k < a.size());
  constexpr typename std::vector<T>::difference_type d = 5;
  using iterator = typename std::vector<T>::iterator;
  function<iterator(iterator, iterator, iterator)> select;
  function<iterator(iterator, iterator)> pivot;
  function<iterator(iterator, iterator, iterator, iterator)> partition;
  function<iterator(iterator, iterator)> partition_d;
  select = [&](iterator left, iterator right, iterator k) {
    while(1) {
      if(left == right) return left;
      assert(left < right);
      iterator pivotIndex = pivot(left, right);
      pivotIndex = partition(left, right, pivotIndex, k);
      if(k == pivotIndex) {
        return k;
      } else if(k < pivotIndex) {
        right = pivotIndex - 1;
      } else {
        left = pivotIndex + 1;
      }
    }
  };
  partition = [&](iterator left, iterator right, iterator pivotIndex, iterator k) {
    T pivotValue = *pivotIndex;
    swap(*pivotIndex, *right);
    iterator storeIndex = left;
    for(iterator i = left; i < right; ++i) {
      if(*i < pivotValue) {
        swap(*storeIndex, *i);
        ++storeIndex;
      }
    }
    iterator storeIndexEq = storeIndex;
    for(iterator i = storeIndex; i < right; ++i) {
      if(!(pivotValue < *i)) {
        swap(*storeIndexEq, *i);
        ++storeIndexEq;
      }
    }
    swap(*right, *storeIndexEq);
    if(k < storeIndex) return storeIndex;
    if(k <= storeIndexEq) return k;
    return storeIndexEq;
  };
  pivot = [&](iterator left, iterator right) {
    if(right - left < d) {
      return partition_d(left, right);
    }
    for(iterator i = left; i <= right; i += d) {
      iterator subRight = min(i + d - 1, right);
      iterator median_d = partition_d(i, subRight);
      swap(*median_d, *(left + (i - left) / d));
    }
    iterator mid = left + (right - left) / d / 2 + 1;
    return select(left, left + (right - left) / d, mid);
  };
  partition_d = [&](iterator left, iterator right) {
    // bubble sort
    for(iterator i = left + 1; i <= right; ++i) {
      for(iterator j = i; j >= left + 1; --j) {
        if(*j < *(j - 1)) {
          swap(*j, *(j-1));
        } else break;
      }
    }
    return left + (right - left) / 2;
  };

  return *select(a.begin(), a.end() - 1, a.begin() + k);
}
template <class T>
T median(std::vector<T> a, bool choose_bigger = 0) {
  return select(a, (a.size() - 1 + choose_bigger) / 2);
}
/// }}}--- ///
template <class T>
T select_greedy(std::vector<T> v, int k) {
  sort(begin(v), end(v));
  return v[k];
}
template <class T>
T median_greedy(std::vector<T> v, bool choose_bigger = 0) {
  sort(begin(v), end(v));
  return v[(v.size() - 1 + choose_bigger)/2];
}

// #define MEDIAN_GREEDY
/// --- RangeSelect {{{ ///
template<class T>
struct RangeSelect {
  using size_type = std::size_t;
  std::vector<std::vector<T>> a;
  std::vector<T> med;
  // fractional cascading
  std::vector<std::vector<int>> L, R;
  size_type n, _size;
  RangeSelect(): n(0) {}
  RangeSelect(size_type t): _size(t) {
    n = 1;
    while(n < t) n <<= 1;
    a.resize(n * 2 - 1);
    med.resize(n * 2 - 1);
    L.resize(n * 2 - 1);
    R.resize(n * 2 - 1);
    a[0].resize(t);
  }
  template<class InputIter, class = typename std::iterator_traits<InputIter>::value_type>
  RangeSelect(InputIter first, InputIter last): RangeSelect(std::distance(first, last)) {
    for(size_type i = 0; first != last; ++first, ++i) {
      a[0][i] = *first;
    }
    build();
  }
  bool built = 0;
  void build() {
    built = 1;
    for(size_type k = 0; k < n - 1; k++) {
      size_type sz = a[k].size();
      if(sz < 2) continue;
#ifdef MEDIAN_GREEDY
      std::vector<T> w = a[k];
      sort(w.begin(), w.end());
      med[k] = w[(w.size() - 1) / 2];
#else
      med[k] = median(a[k]);
#endif

      L[k].resize(sz + 1);
      R[k].resize(sz + 1);
      a[k * 2 + 1].reserve(sz / 2);
      a[k * 2 + 2].reserve(sz / 2);
      for(size_type i = 0; i < sz; i++) {
        T e = a[k][i];
        L[k][i] = a[k * 2 + 1].size();
        R[k][i] = a[k * 2 + 2].size();
        if(e < med[k]) a[k * 2 + 1].push_back(e);
        else if(med[k] < e) a[k * 2 + 2].push_back(e);
      }
      L[k].back() = a[k * 2 + 1].size();
      R[k].back() = a[k * 2 + 2].size();
    }
  }
  T range_select(int l, int r, size_type u) {
    if(l < 0) l = 0;
    if(r > static_cast<int>(_size)) r = _size;
    assert(l < r && u < static_cast<size_type>(r - l));
    size_type k = 0;
    while(1) {
      if(a[k].size() == 1) return a[k][0];
      size_type l_num = L[k][r] - L[k][l];
      size_type r_num = R[k][r] - R[k][l];
      size_type med_num = (r - l) - l_num - r_num;
      if(u < l_num) {
        l = L[k][l];
        r = L[k][r];
        k = k * 2 + 1;
      } else {
        u -= l_num;
        if(u < med_num) {
          return med[k];
        } else {
          u -= med_num;
          l = R[k][l];
          r = R[k][r];
          k = k * 2 + 2;
        }
      }
    }
  }
  T range_median(int l, int r, bool choose_bigger = 0) {
    if(l < 0) l = 0;
    if(r > static_cast<int>(_size)) r = _size;
    return range_select(l, r, (r - l - 1 + choose_bigger) / 2);
  }
};
/// }}}--- ///

void test() {
#ifndef DEBUG
  return;
#endif
  mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count());
  vector<int> v{0, 2, 1};
  // dump(median(v), median_greedy(v));
  assert(median(v) == median_greedy(v));
  v = vector<int>{1209, 1391, 5031, 1931, 942, 1931, 491, 42};
  // dump(median(v), median_greedy(v));
  assert(median(v) == median_greedy(v));
  for(int i = 0; i < 1000; i++) {
    int n = (mt() % 100) + 1;
    v = {};
    for(int j = 0; j < n; j++) v.push_back(mt() % 100000);
    int x = mt() % n;
    // dump(n, x, select_greedy(v, x));
    assert(select(v, x) == select_greedy(v, x));
  }
}

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

  vector<ll> a(n);
  vector<pair<ll, int>> v;
  for(int i = 0; i < n; i++) {
    cin >> a[i], v.emplace_back(a[i], i);
  }
  // O(N log N)
  RangeSelect<pair<ll, int>> rs(begin(v), end(v));
  vector<int> l(q), r(q);
  for(int i = 0; i < q; i++) {
    cin >> l[i] >> r[i];
    l[i]--, r[i]--;
  }

  vector<int> ok(q, n-1);

  // O(Q log N)
  for(int i= 0; i < q; i++) ok[i] = rs.range_select(l[i], r[i] + 1, (r[i] - l[i]) / 2).second;

  // vector<int> ng(q, -1);
  // if(n > 1) {
  //   vector<vector<int>> mid(n);
  //   mid[n/2].reserve(n);
  //   for(int i = 0; i < q; i++) mid[n/2].push_back(i);
  //   // パラサーチ O(Q log N) * O(log N)
  //   int rest = q;
  //   while(rest) {
  //     BIT<> bit(n);
  //     for(int i = 0; i < n; i++) {
  //       int id = v[i].second;
  //       bit.add(id, 1);
  //       for(int j : mid[i]) {
  //         if(bit.range(l[j], r[j]) >= (r[j] - l[j] + 2) / 2) ok[j] = i;
  //         else ng[j] = i;
  //         if(abs(ok[j] - ng[j]) > 1) {
  //           mid[(ok[j] + ng[j])/2].push_back(j);
  //         } else {
  //           rest--;
  //         }
  //       }
  //       mid[i].clear();
  //     }
  //   }
  // }

  vector<vector<int>> qs(n);
  for(int i = 0; i < q; i++) qs[ok[i]].push_back(i);
  dump(ok);

  sort(begin(v), end(v));
  BIT<> d1(n), d2(n);
  vector<ll> ans(q);
  // O(N log N)
  for(int i = 0; i < n; i++) d2.add(i, a[i]);
  // O(Q log N)
  for(int i = 0; i < n; i++) {
    int id = v[i].second;
    d2.add(id, -a[id]);
    d1.add(id, a[id]);

    for(auto j : qs[id]) {
      int len = r[j] - l[j] + 1;
      ans[j] = - d1.range(l[j], r[j]) + d2.range(l[j], r[j]);
      if(len % 2 == 1) ans[j] += a[id];
      // dump(j, len, a[id]);
    }

  }
  for(int i = 0; i < q; i++) cout << ans[i] << "\n";
  return 0;
}