#994504 (C++23) No.2809 Sort Query

提出ソース

結果

問題	No.2809 Sort Query
ユーザー	Aeren
提出日時	2024-07-12 22:52:01
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	909 ms / 2,000 ms
コード長	11,134 bytes
コンパイル時間	4,639 ms
コンパイル使用メモリ	296,352 KB
実行使用メモリ	73,344 KB
最終ジャッジ日時	2024-07-12 22:53:05
合計ジャッジ時間	57,334 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	667 ms 52,604 KB
testcase_02	AC	531 ms 54,332 KB
testcase_03	AC	498 ms 53,428 KB
testcase_04	AC	468 ms 52,948 KB
testcase_05	AC	538 ms 53,632 KB
testcase_06	AC	517 ms 54,012 KB
testcase_07	AC	516 ms 52,480 KB
testcase_08	AC	530 ms 54,392 KB
testcase_09	AC	506 ms 52,644 KB
testcase_10	AC	513 ms 52,528 KB
testcase_11	AC	842 ms 72,196 KB
testcase_12	AC	873 ms 72,824 KB
testcase_13	AC	835 ms 72,544 KB
testcase_14	AC	812 ms 72,244 KB
testcase_15	AC	769 ms 72,116 KB
testcase_16	AC	815 ms 73,252 KB
testcase_17	AC	762 ms 73,016 KB
testcase_18	AC	791 ms 72,840 KB
testcase_19	AC	846 ms 72,300 KB
testcase_20	AC	909 ms 72,516 KB
testcase_21	AC	861 ms 72,572 KB
testcase_22	AC	860 ms 73,132 KB
testcase_23	AC	869 ms 72,644 KB
testcase_24	AC	857 ms 72,288 KB
testcase_25	AC	826 ms 72,148 KB
testcase_26	AC	732 ms 53,188 KB
testcase_27	AC	702 ms 53,368 KB
testcase_28	AC	732 ms 53,296 KB
testcase_29	AC	703 ms 53,400 KB
testcase_30	AC	697 ms 53,308 KB
testcase_31	AC	682 ms 53,932 KB
testcase_32	AC	612 ms 54,268 KB
testcase_33	AC	621 ms 53,344 KB
testcase_34	AC	675 ms 53,360 KB
testcase_35	AC	655 ms 53,492 KB
testcase_36	AC	693 ms 72,688 KB
testcase_37	AC	678 ms 73,048 KB
testcase_38	AC	682 ms 72,416 KB
testcase_39	AC	717 ms 73,256 KB
testcase_40	AC	679 ms 73,344 KB
testcase_41	AC	535 ms 51,216 KB
testcase_42	AC	534 ms 51,988 KB
testcase_43	AC	503 ms 51,332 KB
testcase_44	AC	496 ms 51,604 KB
testcase_45	AC	522 ms 51,560 KB
testcase_46	AC	397 ms 51,380 KB
testcase_47	AC	430 ms 51,252 KB
testcase_48	AC	389 ms 51,096 KB
testcase_49	AC	390 ms 51,700 KB
testcase_50	AC	432 ms 52,064 KB
testcase_51	AC	816 ms 48,316 KB
testcase_52	AC	786 ms 48,432 KB
testcase_53	AC	747 ms 48,488 KB
testcase_54	AC	725 ms 47,956 KB
testcase_55	AC	688 ms 48,772 KB
testcase_56	AC	366 ms 32,568 KB
testcase_57	AC	288 ms 27,992 KB
testcase_58	AC	307 ms 28,684 KB
testcase_59	AC	297 ms 27,608 KB
testcase_60	AC	352 ms 42,760 KB
testcase_61	AC	450 ms 49,052 KB
testcase_62	AC	294 ms 28,676 KB
testcase_63	AC	428 ms 43,288 KB
testcase_64	AC	506 ms 50,928 KB
testcase_65	AC	297 ms 30,696 KB
testcase_66	AC	2 ms 6,944 KB
testcase_67	AC	2 ms 6,940 KB
testcase_68	AC	2 ms 6,944 KB
testcase_69	AC	2 ms 6,944 KB
testcase_70	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debugbin(...) 42
#endif

template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3>
struct segment_tree_base{
	static_assert(HAS_QUERY || HAS_UPDATE);
#define ifQ if constexpr(HAS_QUERY)
#define ifU if constexpr(HAS_UPDATE)
	int n, size, log;
	vector<T> data;
	vector<U> data_action;
	F1 TT; // monoid operation (always adjacent)
	T T_id; // monoid identity
	F2 UU; // monoid operation (superset, subset)
	U U_id; // monoid identity
	F3 UT; // action of U on T (superset, subset)
	// O(n)
	segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ }
	segment_tree_base &operator=(const segment_tree_base &seg){
		n = seg.n;
		size = seg.size;
		log = seg.log;
		data = seg.data;
		data_action = seg.data_action;
	}
	// O(1)
	friend void swap(segment_tree_base &x, segment_tree_base &y){
		swap(x.n, y.n);
		swap(x.size, y.size);
		swap(x.log, y.log);
		swap(x.data, y.data);
		swap(x.data_action, y.data_action);
	}
	// O(n)
	void build(int n){
		assert(n >= 0);
		this->n = n;
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		ifQ data.assign(size << 1, T_id);
		ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id);
	}
	// O(n)
	void build(int n, T x){
		static_assert(HAS_QUERY);
		assert(n >= 0);
		this->n = n;
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data.assign(size << 1, T_id);
		fill(data.begin() + size, data.begin() + size + n, x);
		for(auto i = size - 1; i >= 1; -- i) refresh(i);
		ifU data_action.assign(size, U_id);
	}
	// O(n)
	template<class V>
	void build(const vector<V> &a){
		static_assert(HAS_QUERY);
		n = (int)a.size();
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data.assign(size << 1, T_id);
		copy(a.begin(), a.end(), data.begin() + size);
		for(auto i = size - 1; i >= 1; -- i) refresh(i);
		ifU data_action.assign(size, U_id);
	}
	// O(n)
	void build_action(int n){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(n >= 0);
		build(n);
	}
	// O(n)
	void build_action(int n, U f){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(n >= 0);
		this->n = n;
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data_action.assign(size << 1, U_id);
		fill(data_action.begin() + size, data_action.begin() + size + n, f);
	}
	// O(n)
	template<class V>
	void build_action(const vector<V> &a){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		n = (int)a.size();
		size = 1;
		while(size < n) size <<= 1;
		log = __lg(size);
		data_action.assign(size << 1, U_id);
		copy(a.begin(), a.end(), data_action.begin() + size);
	}
	// O(1)
	void refresh(int u){
		static_assert(HAS_QUERY);
		data[u] = TT(data[u << 1], data[u << 1 | 1]);
	}
	// O(1)
	void apply(int u, U f){
		static_assert(HAS_UPDATE);
		ifQ data[u] = UT(f, data[u]);
		if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]);
	}
	// O(1)
	void push(int u){
		static_assert(HAS_UPDATE);
		apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]);
		data_action[u] = U_id;
	}
	// O(log(n)) if HAS_UPDATE, O(1) otherwise.
	T query(int p){
		static_assert(HAS_QUERY);
		assert(0 <= p && p < n);
		p += size;
		ifU for(auto i = log; i >= 1; -- i) push(p >> i);
		return data[p];
	}
	// O(log(n))
	U query_action(int p){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(0 <= p && p < n);
		p += size;
		ifU for(auto i = log; i >= 1; -- i) push(p >> i);
		return data_action[p];
	}
	// O(log(n))
	T query(int ql, int qr){
		static_assert(HAS_QUERY);
		assert(0 <= ql && ql <= qr && qr <= n);
		if(ql == qr) return T_id;
		ql += size, qr += size;
		ifU for(auto i = log; i >= 1; -- i){
			if(ql >> i << i != ql) push(ql >> i);
			if(qr >> i << i != qr) push(qr >> i);
		}
		T res_left = T_id, res_right = T_id;
		for(; ql < qr; ql >>= 1, qr >>= 1){
			if(ql & 1) res_left = TT(res_left, data[ql ++]);
			if(qr & 1) res_right = TT(data[-- qr], res_right);
		}
		return TT(res_left, res_right);
	}
	// O(1)
	T query_all() const{
		static_assert(HAS_QUERY);
		return data[1];
	}
	// O(n)
	vector<T> to_array(){
		static_assert(HAS_QUERY);
		ifU for(auto u = 1; u < size; ++ u) push(u);
		return vector<T>(data.begin() + size, data.begin() + size + n);
	}
	// O(n)
	vector<U> to_array_of_updates(){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		for(auto u = 1; u < size; ++ u) push(u);
		return vector<U>(data_action.begin() + size, data_action.begin() + size + n);
	}
	// O(log(n))
	void set(int p, T x){
		static_assert(HAS_QUERY);
		assert(0 <= p && p < n);
		p += size;
		ifU for(auto i = log; i >= 1; -- i) push(p >> i);
		data[p] = x;
		for(auto i = 1; i <= log; ++ i) refresh(p >> i);
	}
	// O(log(n))
	void set_action(int p, U f){
		static_assert(!HAS_QUERY && HAS_UPDATE);
		assert(0 <= p && p < n);
		p += size;
		for(auto i = log; i >= 1; -- i) push(p >> i);
		data_action[p] = f;
	}
	// O(log(n))
	void update(int p, U f){
		static_assert(HAS_UPDATE);
		assert(0 <= p && p < n);
		p += size;
		for(auto i = log; i >= 1; -- i) push(p >> i);
		ifQ{
			data[p] = UT(f, data[p]);
			for(auto i = 1; i <= log; ++ i) refresh(p >> i);
		}
		else data_action[p] = UU(f, data_action[p]);
	}
	// O(log(n))
	void update(int ql, int qr, U f){
		static_assert(HAS_UPDATE);
		assert(0 <= ql && ql <= qr && qr <= n);
		if(ql == qr) return;
		ql += size, qr += size;
		for(auto i = log; i >= 1; -- i){
			if(ql >> i << i != ql) push(ql >> i);
			if(qr >> i << i != qr) push(qr >> i);
		}
		int _ql = ql, _qr = qr;
		for(; ql < qr; ql >>= 1, qr >>= 1){
			if(ql & 1) apply(ql ++, f);
			if(qr & 1) apply(-- qr, f);
		}
		ql = _ql, qr = _qr;
		ifQ for(auto i = 1; i <= log; ++ i){
			if(ql >> i << i != ql) refresh(ql >> i);
			if(qr >> i << i != qr) refresh(qr >> i);
		}
	}
	void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
		static_assert(HAS_QUERY && HAS_UPDATE);
		assert(0 <= ql && ql <= qr && qr <= n);
		if(ql == qr) return;
		ql += size, qr += size;
		for(auto i = log; i >= 1; -- i){
			if(ql >> i << i != ql) push(ql >> i);
			if(qr >> i << i != qr) push(qr >> i);
		}
		auto recurse = [&](auto self, int u)->void{
			if(exit_rule(data[u])) return;
			if(enter_rule(data[u])){
				apply(u, update_rule(data[u]));
				return;
			}
			push(u);
			self(self, u << 1), self(self, u << 1 | 1);
			refresh(u);
		};
		int _ql = ql, _qr = qr;
		for(; ql < qr; ql >>= 1, qr >>= 1){
			if(ql & 1) recurse(recurse, ql ++);
			if(qr & 1) recurse(recurse, -- qr);
		}
		ql = _ql, qr = _qr;
		for(auto i = 1; i <= log; ++ i){
			if(ql >> i << i != ql) refresh(ql >> i);
			if(qr >> i << i != qr) refresh(qr >> i);
		}
	}
	// pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F
	// Returns max r with T
	// O(log(n))
	int max_pref(int ql, auto pred){
		static_assert(HAS_QUERY);
		assert(0 <= ql && ql <= n && pred(T_id));
		if(ql == n) return n;
		ql += size;
		ifU for(auto i = log; i >= 1; -- i) push(ql >> i);
		T sum = T_id;
		do{
			while(~ql & 1) ql >>= 1;
			if(!pred(TT(sum, data[ql]))){
				while(ql < size){
					ifU push(ql);
					ql = ql << 1;
					if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]);
				}
				return ql - size;
			}
			sum = TT(sum, data[ql]);
			++ ql;
		}while((ql & -ql) != ql);
		return n;
	}
	// pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T
	// Returns min l with T
	// O(log(n))
	int max_suff(int qr, auto pred){
		static_assert(HAS_QUERY);
		assert(0 <= qr && qr <= n && pred(T_id));
		if(qr == 0) return 0;
		qr += size;
		ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i);
		T sum = T_id;
		do{
			-- qr;
			while(qr > 1 && qr & 1) qr >>= 1;
			if(!pred(TT(data[qr], sum))){
				while(qr < size){
					ifU push(qr);
					qr = qr << 1 | 1;
					if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum);
				}
				return qr + 1 - size;
			}
			sum = TT(data[qr], sum);
		}while((qr & -qr) != qr);
		return 0;
	}
	template<class output_stream>
	friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){
		out << "{";
		for(auto i = 0; i < seg.n; ++ i){
			ifQ out << seg.query(i);
			else out << seg.query_action(i);
			if(i != seg.n - 1) out << ", ";
		}
		return out << '}';
	}
#undef ifQ
#undef ifU
};

// Supports query
template<class T, class F>
auto make_Q_segment_tree(F TT, T T_id){
	using U = int;
	auto _UU = [&](U, U)->U{ return U{}; };
	auto _UT = [&](U, T)->T{ return T{}; };
	return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT);
}
// Supports update
template<class U, class F>
auto make_U_segment_tree(F UU, U U_id){
	using T = int;
	auto _TT = [&](T, T)->T{ return T{}; };
	auto _UT = [&](U, T)->T{ return T{}; };
	return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT);
}
// Supports query and update
template<class T, class U, class F1, class F2, class F3>
auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){
	return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT);
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, qn;
	cin >> n >> qn;
	vector<long long> a(n);
	copy_n(istream_iterator<long long>(cin), n, a.begin());
	vector<pair<long long, int>> cmpr;
	for(auto i = 0; i < n; ++ i){
		cmpr.push_back({a[i], i});
	}
	vector<array<long long, 3>> q(qn);
	for(auto i = n; auto &[type, p, x]: q){
		cin >> type;
		if(type != 2){
			cin >> p, -- p;
			if(type == 1){
				cin >> x;
				cmpr.push_back({x, i ++});
			}
		}
	}
	ranges::sort(cmpr);
	cmpr.erase(ranges::unique(cmpr).begin(), cmpr.end());
	using T = pair<int, long long>; // cnt, maxv
	T T_id{0, -1};
	auto TT = [&](const T &x, const T &y)->T{
		return {x.first + y.first, max(x.second, y.second)};
	};
	auto seg = make_Q_segment_tree(TT, T_id);
	auto index = [&](long long x, int i)->int{
		return ranges::lower_bound(cmpr, pair{x, i}) - cmpr.begin();
	};
	seg.build((int)cmpr.size(), T_id);
	map<int, int> lazy;
	for(auto i = 0; i < n; ++ i){
		lazy[i] = index(a[i], i);
	}
	for(int i = n; auto [type, p, x]: q){
		if(type == 1){
			lazy[p] = index(x, i ++);
		}
		else if(type == 2){
			static vector<int> update;
			update.clear();
			for(auto [p, v]: lazy | ranges::views::reverse){
				auto w = seg.max_pref(0, [&](auto pref){ return pref.first <= p; });
				if(w < (int)cmpr.size()){
					seg.set(w, T_id);
				}
				update.push_back(v);
			}
			ranges::sort(update);
			for(auto v: update){
				seg.set(v, T{1, cmpr[v].first});
			}
			lazy.clear();
		}
		else{
			if(lazy.contains(p)){
				cout << cmpr[lazy[p]].first << "\n";
			}
			else{
				auto x = seg.max_pref(0, [&](auto pref){ return pref.first <= p; });
				cout << seg.query(x).second << "\n";
			}
		}
	}
	return 0;
}

/*

*/

yukicoder

結果

テストケース

ソースコード