#860431 (C++17) No.1270 Range Arrange Query

提出ソース
結果

問題	No.1270 Range Arrange Query
ユーザー	hashiryo
提出日時	2023-04-17 13:34:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,037 ms / 7,000 ms
コード長	13,712 bytes
コンパイル時間	3,964 ms
コンパイル使用メモリ	251,520 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-12 15:05:32
合計ジャッジ時間	9,740 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	65 ms 5,248 KB
testcase_07	AC	591 ms 5,248 KB
testcase_08	AC	88 ms 5,248 KB
testcase_09	AC	396 ms 5,248 KB
testcase_10	AC	415 ms 5,248 KB
testcase_11	AC	1,037 ms 5,248 KB
testcase_12	AC	1,034 ms 6,816 KB
testcase_13	AC	1,034 ms 6,820 KB
testcase_14	AC	23 ms 6,816 KB
testcase_15	AC	41 ms 6,816 KB
testcase_16	AC	44 ms 6,816 KB
testcase_17	AC	53 ms 6,816 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}

#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on

template <typename M> struct SegmentTree_Beats {
 using T= typename M::T;
 using E= typename M::E;
 SegmentTree_Beats() {}
 SegmentTree_Beats(int n_): n(n_), height(n == 1 ? 0 : std::__lg(n - 1) + 1), dat(n * 2, M::ti()), laz(n, {E(), false}) {}
 SegmentTree_Beats(int n_, T v1): SegmentTree_Beats(n_) {
  for (int i= n; i--;) dat[i + n]= v1;
  for (int i= n; --i;) update(i);
 }
 SegmentTree_Beats(const std::vector<T> &v): SegmentTree_Beats(v.size()) {
  for (int i= n; i--;) dat[i + n]= v[i];
  for (int i= n; --i;) update(i);
 }
 void unsafe_set(int k, T x) { dat[k + n]= x; }
 void rebuild() {
  for (int i= n; i--;) laz[i].flg= false;
  for (int i= n; --i;) update(i);
 }
 void apply(int a, int b, E x) {
  a+= n, b+= n;
  for (int i= height; i; i--)
   if (((a >> i) << i) != a) eval(a >> i);
  for (int i= height; i; i--)
   if (((b >> i) << i) != b) eval((b - 1) >> i);
  for (int l= a, r= b; l < r; l>>= 1, r>>= 1) {
   if (l & 1) propagate(l++, x);
   if (r & 1) propagate(--r, x);
  }
  for (int i= 1; a >> i; i++)
   if (((a >> i) << i) != a) update(a >> i);
  for (int i= 1; b >> i; i++)
   if (((b >> i) << i) != b) update((b - 1) >> i);
 }
 void set(int k, T x) {
  int i= height;
  for (k+= n; i; i--) eval(k >> i);
  for (dat[k]= x, i= 1; k >> i; i++) update(k >> i);
 }
 T fold(int a, int b) {  //[a,b)
  a+= n, b+= n;
  for (int i= height; i; i--)
   if (((a >> i) << i) != a) eval(a >> i);
  for (int i= height; i; i--)
   if (((b >> i) << i) != b) eval(b >> i);
  T vl= M::ti(), vr= M::ti();
  for (int l= a, r= b; l < r; l>>= 1, r>>= 1) {
   if (l & 1) vl= M::op(vl, dat[l++]);
   if (r & 1) vr= M::op(dat[--r], vr);
  }
  return M::op(vl, vr);
 }
 T operator[](const int k) { return fold(k, k + 1); }
private:
 const int n, height;
 struct Lazy {
  E val;
  bool flg;
 };
 std::vector<T> dat;
 std::vector<Lazy> laz;
 inline void eval(int k) {
  if (!laz[k].flg) return;
  propagate(k << 1 | 0, laz[k].val), propagate(k << 1 | 1, laz[k].val);
  laz[k].flg= false;
 }
 inline void propagate(int k, const E &x) {
  if (bool success= M::mapping(dat[k], x); k < n) {
   laz[k].flg ? (M::composition(laz[k].val, x), x) : laz[k].val= x;
   if (laz[k].flg= true; !success) eval(k), update(k);
  }
 }
 inline void update(int k) { dat[k]= M::op(dat[k << 1 | 0], dat[k << 1 | 1]); }
};
template <class T> auto compress(std::vector<T> &v) {
 return std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end()), [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}
template <typename T> class BinaryIndexedTree {
 std::vector<T> dat;
public:
 BinaryIndexedTree(int n): dat(n + 1, T()) {}
 BinaryIndexedTree(int n, T a): BinaryIndexedTree(std::vector<T>(n, a)) {}
 BinaryIndexedTree(const std::vector<T> &y): dat(y.size() + 1, 0) {
  for (int i= y.size(); i--;) dat[i + 1]= y[i];
  for (int i= 1, e= dat.size(), j; i < e; ++i)
   if ((j= i + (i & -i)) < e) dat[j]+= dat[i];
 }
 void add(int i, T a= 1) {
  for (++i; i < (int)dat.size(); i+= i & -i) dat[i]+= a;
 }
 T sum(int i) const {  // sum [0,i)
  T s= 0;
  for (; i; i&= i - 1) s+= dat[i];
  return s;
 }
 T sum(int l, int r) const { return sum(r) - sum(l); }  // sum [l,r)
 T operator[](int k) const { return sum(k + 1) - sum(k); }
 int find(T k) const {  // min { i : sum(i+1) > k } -> kth element(0-indexed)
  int i= 0;
  for (int p= 1 << (std::__lg(dat.size() - 1) + 1), e= dat.size(); p; p>>= 1)
   if (i + p < e && dat[i + p] <= k) k-= dat[i+= p];
  return i + 1 == (int)dat.size() ? -1 : i;  // -1 -> no solutions
 }
};
// struct Mo {
//  std::vector<int> L, R;
//  Mo() {}
//  void query(int l, int r) { L.push_back(l), R.push_back(r); } /* [l, r) */
//  template <typename AL, typename AR, typename EL, typename ER, typename O> void run(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
//   int q= L.size(), n= *std::max_element(R.begin(), R.end()), bs= n / std::min<int>(n, std::sqrt(q));
//   std::vector<int> ord(q);
//   std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int a, int b) {
//    int ablk= L[a] / bs, bblk= L[b] / bs;
//    return ablk != bblk ? ablk < bblk : (ablk & 1) ? R[a] > R[b] : R[a] < R[b];
//   });
//   int l= 0, r= 0;
//   for (auto i: ord) {
//    while (l > L[i]) add_left(--l);
//    while (r < R[i]) add_right(r++);
//    while (l < L[i]) erase_left(l++);
//    while (r > R[i]) erase_right(--r);
//    out(i);
//   }
//  }
//  template <typename A, typename E, typename O> void run(const A &add, const E &erase, const O &out) { run(add, add, erase, erase, out); }
// };
// struct Mo {
//  std::vector<int> L, R;
//  Mo() {}
//  void query(int l, int r) { L.push_back(l), R.push_back(r); } /* [l, r) */
//  template <typename AL, typename AR, typename EL, typename ER, typename O> void run(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
//   int q= L.size(), n= *std::max_element(R.begin(), R.end()), bs= n / std::min<int>(n, std::sqrt(2 * q));
//   std::vector<int> ord(q);
//   std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int a, int b) {
//    int ablk= L[a] / bs, bblk= L[b] / bs;
//    return ablk != bblk ? ablk < bblk : (ablk & 1) ? R[a] > R[b] : R[a] < R[b];
//   });
//   int l= 0, r= 0;
//   for (auto i: ord) {
//    while (l > L[i]) add_left(--l);
//    while (r < R[i]) add_right(r++);
//    while (l < L[i]) erase_left(l++);
//    while (r > R[i]) erase_right(--r);
//    out(i);
//   }
//  }
//  template <typename A, typename E, typename O> void run(const A &add, const E &erase, const O &out) { run(add, add, erase, erase, out); }
// };
struct Mo {
 std::vector<int> L, R;
 Mo() {}
 void query(int l, int r) { L.push_back(l), R.push_back(r); } /* [l, r) */
 template <typename AL, typename AR, typename EL, typename ER, typename O> void run(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
  int q= L.size(), n= *std::max_element(R.begin(), R.end()), bs= n / std::min<int>(n, std::sqrt(q)), bs2= bs / 2;
  std::vector<int> ord1(q), ord2(q);
  std::iota(ord1.begin(), ord1.end(), 0), std::iota(ord2.begin(), ord2.end(), 0);
  std::sort(ord1.begin(), ord1.end(), [&](int a, int b) {
   int ablk= L[a] / bs, bblk= L[b] / bs;
   return ablk != bblk ? ablk < bblk : (ablk & 1) ? R[a] > R[b] : R[a] < R[b];
  });
  std::sort(ord2.begin(), ord2.end(), [&](int a, int b) {
   int ablk= (L[a] + bs2) / bs, bblk= (L[b] + bs2) / bs;
   return ablk != bblk ? ablk < bblk : (ablk & 1) ? R[a] > R[b] : R[a] < R[b];
  });
  int l= 0, r= 0, dist1= 0, dist2= 0;
  for (auto i: ord1) dist1+= std::abs(L[i] - l) + std::abs(R[i] - r), l= L[i], r= R[i];
  l= r= 0;
  for (auto i: ord2) dist2+= std::abs(L[i] - l) + std::abs(R[i] - r), l= L[i], r= R[i];
  l= r= 0;
  debug(dist1);
  debug(dist2);
  if (dist1 < dist2)
   for (auto i: ord1) {
    while (l > L[i]) add_left(--l);
    while (r < R[i]) add_right(r++);
    while (l < L[i]) erase_left(l++);
    while (r > R[i]) erase_right(--r);
    out(i);
   }
  else
   for (auto i: ord2) {
    while (l > L[i]) add_left(--l);
    while (r < R[i]) add_right(r++);
    while (l < L[i]) erase_left(l++);
    while (r > R[i]) erase_right(--r);
    out(i);
   }
 }
 template <typename A, typename E, typename O> void run(const A &add, const E &erase, const O &out) { run(add, add, erase, erase, out); }
};
using namespace std;
namespace AOJ0425 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, K, Q;
 cin >> N >> K >> Q;
 int a[K], b[K];
 for (int k= 0; k < K; k++) cin >> a[k] >> b[k], a[k]--, b[k]--;
 Mo mo;
 int op[Q], x[Q];
 for (int q= 0; q < Q; q++) {
  int s, t;
  cin >> op[q] >> s >> t >> x[q], x[q]--;
  mo.query(--s, t);
 }
 int ord[N], pos[N];
 iota(ord, ord + N, 0), iota(pos, pos + N, 0);
 auto mover= [&](int k) { swap(ord[a[k]], ord[b[k]]), swap(pos[ord[a[k]]], pos[ord[b[k]]]); };
 auto movel= [&](int k) { swap(pos[a[k]], pos[b[k]]), swap(ord[pos[a[k]]], ord[pos[b[k]]]); };
 int ans[Q];
 auto out= [&](int q) { ans[q]= (op[q] == 1 ? ord[x[q]] : pos[x[q]]) + 1; };
 mo.run(movel, mover, movel, mover, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << "\n";
 return 0;
}
}
namespace yosupo_range_inversion {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 int A[N];
 for (int i= 0; i < N; i++) cin >> A[i];
 vector<int> v(A, A + N);
 auto id= compress(v);
 for (int i= 0; i < N; i++) A[i]= id(A[i]);
 Mo mo;
 for (int q= 0; q < Q; q++) {
  int l, r;
  cin >> l >> r;
  mo.query(l, r);
 }
 BinaryIndexedTree<long long> bit(N + 1);
 long long inv= 0, total= 0;
 auto addl= [&](int i) { inv+= bit.sum(A[i]), bit.add(A[i], 1), total++; };
 auto addr= [&](int i) { inv+= total - bit.sum(A[i] + 1), bit.add(A[i], 1), total++; };
 auto erasel= [&](int i) { inv-= bit.sum(A[i]), bit.add(A[i], -1), total--; };
 auto eraser= [&](int i) { inv-= total - bit.sum(A[i] + 1), bit.add(A[i], -1), total--; };
 long long ans[Q];
 auto out= [&](int q) { ans[q]= inv; };
 mo.run(addl, addr, erasel, eraser, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << "\n";
 return 0;
}
}
namespace yukicoder1270 {
struct RmQRaQ {
 using T= int;
 using E= int;
 static T ti() { return 1 << 30; }
 static T op(T l, T r) { return min(l, r); }
 static bool mapping(T &v, E x) {
  if (v != ti()) v+= x;
  return true;
 }
 static void composition(E &p, E s) { p+= s; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<int> a(N);
 for (int i= 0; i < N; ++i) cin >> a[i], --a[i];
 BinaryIndexedTree<int> bitl(N), bitr(N);
 SegmentTree_Beats<RmQRaQ> seg(N, 0);
 int sum= 0, sz= 0;
 for (auto x: a) {
  sum+= bitr.sum(x + 1, N);
  bitr.add(x, 1);
  seg.apply(x + 1, N, 1);
 }
 Mo mo;
 for (int q= 0; q < Q; ++q) {
  int l, r;
  cin >> l >> r;
  mo.query(--l, r);
 }
 auto addl= [&](int i) {
  int x= a[i];
  sum-= bitl.sum(x + 1, N) + bitr.sum(0, x);
  bitl.add(x, -1);
  seg.apply(0, x, -1);
  ++sz;
 };
 auto addr= [&](int i) {
  int x= a[i];
  sum-= bitr.sum(0, x) + bitl.sum(x + 1, N);
  bitr.add(x, -1);
  seg.apply(x + 1, N, -1);
  ++sz;
 };
 auto erasel= [&](int i) {
  int x= a[i];
  sum+= bitl.sum(x + 1, N) + bitr.sum(0, x);
  bitl.add(x, 1);
  seg.apply(0, x, 1);
  --sz;
 };
 auto eraser= [&](int i) {
  int x= a[i];
  sum+= bitr.sum(0, x) + bitl.sum(x + 1, N);
  bitr.add(x, 1);
  seg.apply(x + 1, N, 1);
  --sz;
 };
 vector<int> ans(Q);
 auto out= [&](int q) { ans[q]= sum + seg.fold(0, N) * sz; };
 mo.run(addl, addr, erasel, eraser, out);
 for (auto x: ans) cout << x << '\n';
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // AOJ0425::main();
 // yosupo_range_inversion::main();
 yukicoder1270::main();
 return 0;
}