結果
| 問題 | No.1270 Range Arrange Query |
| ユーザー |
 polylogK
|
| 提出日時 | 2020-10-24 00:32:39 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,395 ms / 7,000 ms |
| コード長 | 14,817 bytes |
| コンパイル時間 | 2,667 ms |
| コンパイル使用メモリ | 214,916 KB |
| 最終ジャッジ日時 | 2025-01-15 14:45:51 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
コンパイルメッセージ
005.cpp: In function ‘int main()’:
005.cpp:138:35: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘i64*’ {aka ‘long int*’} [-Wformat=]
005.cpp:150:9: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘i64*’ {aka ‘long int*’} [-Wformat=]
005.cpp:150:9: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘i64*’ {aka ‘long int*’} [-Wformat=]
005.cpp:158:36: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘i64’ {aka ‘long int’} [-Wformat=]
005.cpp:137:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
005.cpp:138:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
005.cpp:150:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
ソースコード
#line 1 "005.cpp"#include <bits/stdc++.h>using namespace std::literals::string_literals;using i64 = std::int_fast64_t;using std::cout;using std::cerr;using std::endl;using std::cin;template<typename T>std::vector<T> make_v(size_t a){return std::vector<T>(a);}template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}#line 2 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/lazy_segment_tree.hpp"#line 6 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/lazy_segment_tree.hpp"#line 2 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/monoid.hpp"#line 2 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/affine.hpp"#line 4 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/affine.hpp"namespace cplib {template<class T> struct affine {using value_type = T;value_type a;value_type b;constexpr affine(const value_type& a = 1, const value_type& b = 0): a(a), b(b) {}constexpr affine operator+(const affine& r) const { return affine{a + r.a, b + r.b}; }constexpr affine composite(const affine& r) const { return affine{a * r.a, a * r.b + b}; }constexpr value_type evaluate(const value_type& x) { return a * x + b; }};}#line 6 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/monoid.hpp"namespace cplib {template<class T, T id = T{}> struct add_monoid {using value_type = T;T a;constexpr add_monoid(T a): a(a) {}static constexpr add_monoid operation(const add_monoid& l, const add_monoid& r) { return add_monoid{l.a + r.a}; }static constexpr add_monoid identity() { return add_monoid{id}; };static constexpr add_monoid inverse(const add_monoid& x) { return add_monoid{-x.a}; }};template<class T, T id = T{1}> struct mul_monoid {using value_type = T;T a;constexpr mul_monoid(T a): a(a) {}static constexpr mul_monoid operation(const mul_monoid& l, const mul_monoid& r) { return mul_monoid{l.a * r.a}; }static constexpr mul_monoid identity() { return mul_monoid{id}; };};template<class T, T id = T{}> struct max_monoid {using value_type = T;T a;constexpr max_monoid(T a): a(a) {}static constexpr max_monoid operation(const max_monoid& l, const max_monoid& r) { return max_monoid{std::max(l.a, r.a)}; }static constexpr max_monoid identity() { return max_monoid{id}; };};template<class T, T id = std::numeric_limits<T>::max()> struct min_monoid {using value_type = T;T a;constexpr min_monoid(T a): a(a) {}static constexpr min_monoid operation(const min_monoid& l, const min_monoid& r) { return min_monoid{std::min(l.a, r.a)}; }static constexpr min_monoid identity() { return min_monoid{id}; };};template<class T, T& id> struct monoid {using value_type = T;T a;constexpr monoid(T a): a(a) {}static constexpr monoid operation(const monoid& l, const monoid& r) { return monoid{l.a + r.a}; }static constexpr monoid identity() { return monoid{id}; }static constexpr monoid inverse(const monoid& x) { return monoid{x.a.inverse()}; }};template<class A, class B> struct cartesian_product_monoid {using value_type = std::pair<typename A::value_type, typename B::value_type>;value_type a;constexpr cartesian_product_monoid(const value_type& a): a(a) {}static constexpr cartesian_product_monoid operation(const cartesian_product_monoid& l, const cartesian_product_monoid& r) {return cartesian_product_monoid{{A::operation(l.a.first, r.a.first).a, B::operation(l.a.second, r.a.second).a}};}static constexpr cartesian_product_monoid identity() { return cartesian_product_monoid{{A::identity().a, B::identity().a}}; }static constexpr cartesian_product_monoid inverse(const cartesian_product_monoid& x) {return cartesian_product_monoid{{A::inverse(x.a.first).a, B::inverse(x.a.second).a}};}};template<class T> struct affine_composite_monoid {using value_type = cplib::affine<T>;value_type a;constexpr affine_composite_monoid(const value_type& a): a(a) {}static constexpr affine_composite_monoid operation(const affine_composite_monoid& l,const affine_composite_monoid& r) {return affine_composite_monoid{r.a.composite(l.a)};}static constexpr affine_composite_monoid identity() {return affine_composite_monoid{value_type()};}};}#line 8 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/lazy_segment_tree.hpp"namespace cplib {template<class M, class E, class operation> class lazy_segment_tree {public:using value_type = M;using T = typename value_type::value_type;using operator_type = E;using usize = std::uint_fast32_t;struct node_type {value_type value;operator_type lazy;node_type(const value_type& value, const operator_type& lazy): value(value), lazy(lazy) {}};private:std::vector<node_type> data;value_type value(const node_type& x) const { return value_type{operation()(x.value.a, x.lazy.a)}; }usize countr_zeros(usize x) const { return __builtin_ctzll(x); }void add(operator_type& l, const operator_type& r) { l = operator_type::operation(l, r); }void propagate(usize idx) {add(data[idx * 2 + 0].lazy, data[idx].lazy);add(data[idx * 2 + 1].lazy, data[idx].lazy);data[idx].lazy = operator_type::identity();}void propagate_bound(usize idx) {if(idx == 0) return;std::stack<usize> order;idx >>= countr_zeros(idx);while(idx >>= 1) order.push(idx);while(!order.empty()){propagate(order.top());order.pop();}}void recalc(usize idx) { data[idx].value = value_type::operation(value(data[idx * 2 + 0]), value(data[idx * 2 + 1])); }void recalc_bound(usize idx) {if(idx == 0) return;idx >>= countr_zeros(idx);while(idx >>= 1) recalc(idx);}public:lazy_segment_tree() = default;explicit lazy_segment_tree(usize n): data(n << 1, node_type(value_type::identity(), operator_type::identity())) {}template<class InputIt> explicit lazy_segment_tree(InputIt first, InputIt last): lazy_segment_tree(std::distance(first, last)) {for(int index = 0; first != last; first++, index++) set(index, *first);build();}usize size() { return data.size() >> 1; }bool empty() { return size() == 0; }void clear() { data.clear(); }void swap(lazy_segment_tree& r) { data.swap(r.data); }T get(usize i) { return fold(i, i + 1).value.a; }void set(usize i, const value_type& x) { data[i + size()].value = x; };void build() { for(usize i = size() - 1; i > 0; i--) recalc(i); }void change(usize i, const value_type& x) {i += size();propagate_bound(((i >> 1) << 1) + 1);data[i] = node_type(x, operator_type::identity());recalc_bound(((i >> 1) << 1) + 1);}void update(usize i, const value_type& x) {i += size();propagate_bound(((i >> 1) << 1) + 1);data[i] = node_type(value_type::operation(value(data[i]), x), operator_type::identity());recalc_bound(((i >> 1) << 1) + 1);}T fold(usize first, usize last) {first += size();last += size();propagate_bound(first);recalc_bound(first);propagate_bound(last);recalc_bound(last);value_type lval = value_type::identity();value_type rval = value_type::identity();while(first != last) {if(first & 1) {lval = value_type::operation(lval, value(data[first]));first++;}if(last & 1) {last--;rval = value_type::operation(value(data[last]), rval);}first >>= 1;last >>= 1;}return value_type::operation(lval, rval).a;}void update(usize first, usize last, const operator_type& x) {first += size();last += size();usize first_tmp = first;usize last_tmp = last;propagate_bound(first);propagate_bound(last);while(first != last) {if(first & 1) {add(data[first].lazy, x);first++;}if(last & 1) {last--;add(data[last].lazy, x);}first >>= 1;last >>= 1;}recalc_bound(first_tmp);recalc_bound(last_tmp);}};}#line 18 "005.cpp"struct Mo {const int width;int q = 0;std::vector< int > le, ri, order;int nl = 0, nr = 0;Mo(int n, int q, double k = 1): width(int(k* n / sqrt(q) + 1.0)), le(q), ri(q), order(q) {}inline void insert(int l, int r) {le[q] = l;ri[q] = r;order[q] = q;q++;}inline void build() {sort(begin(order), begin(order) + q, [&](int a, int b) {const int ab = le[a] / width, bb = le[b] / width;return ab != bb ? ab < bb : ab & 1 ? ri[a] < ri[b] : ri[b] < ri[a];});nl = le[order[0]];nr = ri[order[0]];init(nl, nr);for(int i = 0; i < q; i++) {const int id = order[i];while(nl > le[id]) add(--nl, 0);while(nl < le[id]) rem(nl++, 0);while(nr < ri[id]) add(nr++, 1);while(nr > ri[id]) rem(--nr, 1);next(id);}}inline void init(int l, int r);inline void next(int i);inline void add(int i, int d);inline void rem(int i, int d);};const int N = 20010;struct operation {int operator()(int a, int b) { return a + b; }};cplib::lazy_segment_tree<cplib::min_monoid<int, 0>, cplib::add_monoid<int>, operation> seg(N);#line 2 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/segment_tree.hpp"#line 5 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/segment_tree.hpp"#line 7 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/segment_tree.hpp"namespace cplib {template<class Monoid> class segment_tree {public:using value_type = Monoid;using T = typename value_type::value_type;using usize = std::uint_fast32_t;private:int n;std::vector<value_type> data;private:usize base() const { return data.size() >> 1; }public:segment_tree() = default;explicit segment_tree(usize n): n(n) {usize size = 1;while(size <= n) size <<= 1;data.assign(size << 1, value_type::identity());}template<class InputIt> explicit segment_tree(InputIt first, InputIt last): segment_tree(std::distance(first, last)) {for(int index = 0; first != last; first++, index++) set(index, *first);build();}usize size() const { return n; }bool empty() const { return size() == 0; }void clear() {n = 0;data.clear();}void swap(segment_tree& r) {std::swap(n, r.n);data.swap(r.data);}T get(usize i) const { return data[i + base()].a; }void set(usize i, const value_type& x) { data[i + base()] = x; }void build() {for(usize i = (int)base() - 1; i > 0; i--)data[i] = value_type::operation(data[i * 2 + 0], data[i * 2 + 1]);}void change(usize i, const value_type& x) {data[i += base()] = x;while(i >>= 1) data[i] = value_type::operation(data[i * 2 + 0], data[i * 2 + 1]);}void update(usize i, const value_type& x) { change(i, value_type::operation(get(i), x)); }T fold(usize first, usize last) const {first += base();last += base();value_type lval = value_type::identity();value_type rval = value_type::identity();while(first != last) {if(first & 1) lval = value_type::operation(lval, data[first++]);if(last & 1) rval = value_type::operation(data[--last], rval);first >>= 1;last >>= 1;}return value_type::operation(lval, rval).a;}T fold_all() const { return data[1].a; }// return max{r | f(fold(l, r - 1)) = true}template<class F> usize search_right(int l, const F& f) const {if(l == size()) return base();l += base();value_type acc = value_type::identity();do {while(l % 2 == 0) l >>= 1;if(!f(value_type::operation(acc, data[l]).a)) {while(l < base()) {l = l << 1;if(f(value_type::operation(acc, data[l]).a)) {acc = value_type::operation(acc, data[l]);l += 1;}}return l - base();}acc = value_type::operation(acc, data[l]);l += 1;} while((l & -l) != l);return size();}// return min{l | f(fold(l, r - 1) = true}template<class F> usize search_left(int r, const F& f) const {if(r == 0) return 0;r += base();value_type acc = value_type::identity();do {r--;while(r > 1 and (r % 2)) r >>= 1;if(!f(value_type::operation(data[r], acc).a)) {while(r < base()) {r = r * 2 + 1;if(f(value_type::operation(data[r], acc).a)) {acc = value_type::operation(data[r], acc);r -= 1;}}return r + 1 - base();}acc = value_type::operation(data[r], acc);} while((r & -r) == r);return 0;}};}// @docs docs/segment_tree.md#line 62 "005.cpp"cplib::segment_tree<cplib::add_monoid<i64>> A(N), B(N), C(N);int n;i64 CNT = 0, L[N], R[N], cnt[N], a[N], l[N], r[N], ans[N];inline void Mo::init(int l, int r) {for(int i = 0; i < l; i++) L[a[i]]++;for(int i = r; i < n; i++) R[a[i]]++;for(int i = 0; i < N - 1; i++) cnt[i] = R[i] - L[i + 1];for(int i = 0; i < N; i++) seg.update(i, N, cnt[i]);for(int i = r; i < n; i++) C.update(a[i], 1);for(int i = l; i < r; i++) B.update(a[i], 1);for(int i = r; i < n; i++) CNT += B.fold(a[i] + 1, N);}inline void Mo::next(int i) {// int offset = n - (r[i] - l[i]);// cout << i << "(" << l[i] << ", " << r[i] << "): ";// for(int i = 0; i < 10; i++) cout << seg.fold(i, i + 1) << " "; cout << endl;// for(int i = 0; i < 10; i++) cout << L[i] << " "; cout << endl;// for(int i = 0; i < 10; i++) cout << R[i] << " "; cout << endl;ans[i] += seg.fold(0, N) * (r[i] - l[i])+ A.fold(0, l[i]) + A.fold(r[i], n)- CNT;// cout << seg.fold(0, N) * (r[i] - l[i]) << " " << A.fold(0, l[i]) << " " << A.fold(r[i], n) << " " << B.fold(l[i], r[i]) << " " << CNT << endl;}inline void Mo::rem(int i, int d) {int v = a[i];if(!d) {L[v]++;int tmp = cnt[v - 1];cnt[v - 1] = R[v - 1] - L[v];tmp = cnt[v - 1] - tmp;seg.update(v - 1, N, tmp);CNT -= C.fold(0, a[i]);} else {R[v]++;int tmp = cnt[v];cnt[v] = R[v] - L[v + 1];tmp = cnt[v] - tmp;seg.update(v, N, tmp);C.update(a[i], 1);CNT -= C.fold(0, a[i]);CNT += B.fold(a[i] + 1, N);}B.update(a[i], -1);}inline void Mo::add(int i, int d) {int v = a[i];if(!d) {L[v]--;int tmp = cnt[v - 1];cnt[v - 1] = R[v - 1] - L[v];tmp = cnt[v - 1] - tmp;seg.update(v - 1, N, tmp);CNT += C.fold(0, a[i]);} else {R[v]--;int tmp = cnt[v];cnt[v] = R[v] - L[v + 1];tmp = cnt[v] - tmp;seg.update(v, N, tmp);C.update(a[i], -1);CNT += C.fold(0, a[i]);CNT -= B.fold(a[i] + 1, N);}B.update(a[i], 1);}int main() {int q; scanf("%d%d", &n, &q);for(int i = 0; i < n; i++) scanf("%lld", &a[i]);{cplib::segment_tree<cplib::add_monoid<i64>> cnt(N);for(int i = 0; i < n; i++) {cnt.update(a[i], 1);A.change(i, cnt.fold(a[i] + 1, N));}}Mo mo(n, q, 2);for(int i = 0; i < q; i++) {scanf("%lld%lld", &l[i], &r[i]);l[i]--;mo.insert(l[i], r[i]);ans[i] = l[i] * (r[i] - l[i]);}mo.build();for(int i = 0; i < q; i++) printf("%lld\n", ans[i]);return 0;}