結果

問題 No.1270 Range Arrange Query
ユーザー hashiryohashiryo
提出日時 2023-04-17 14:26:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 13,705 bytes
コンパイル時間 3,229 ms
コンパイル使用メモリ 225,112 KB
最終ジャッジ日時 2025-02-12 09:31:59
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 1 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #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 - 1;
for (int i= height; i; --i) eval(a >> i);
for (int i= height; i; --i) eval(b >> i);
for (int l= a, r= b + 1; l < r; l>>= 1, r>>= 1) {
if (l & 1) propagate(l++, x);
if (r & 1) propagate(--r, x);
}
for (int i= 1; i <= height; ++i) update(a >> i);
for (int i= 1; i <= height; ++i) update(b >> 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 fold_all() const { return dat[1]; }
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 / 3));
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_all() * 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0