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

提出ソース
結果

問題	No.1270 Range Arrange Query
ユーザー	polylogK
提出日時	2020-10-24 00:32:39
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,207 ms / 7,000 ms
コード長	14,817 bytes
コンパイル時間	2,857 ms
コンパイル使用メモリ	220,800 KB
実行使用メモリ	6,708 KB
最終ジャッジ日時	2024-07-21 14:24:27
合計ジャッジ時間	8,946 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	10 ms 5,632 KB
testcase_01	AC	11 ms 5,632 KB
testcase_02	AC	10 ms 5,632 KB
testcase_03	AC	11 ms 5,888 KB
testcase_04	AC	10 ms 5,760 KB
testcase_05	AC	11 ms 5,760 KB
testcase_06	AC	91 ms 5,760 KB
testcase_07	AC	697 ms 6,152 KB
testcase_08	AC	117 ms 5,816 KB
testcase_09	AC	473 ms 6,128 KB
testcase_10	AC	509 ms 6,120 KB
testcase_11	AC	1,207 ms 6,708 KB
testcase_12	AC	1,206 ms 6,580 KB
testcase_13	AC	1,206 ms 6,708 KB
testcase_14	AC	25 ms 6,200 KB
testcase_15	AC	64 ms 6,708 KB
testcase_16	AC	57 ms 6,456 KB
testcase_17	AC	55 ms 6,580 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
}
yukicoder

結果

テストケース

ソースコード
