結果

問題 No.875 Range Mindex Query
ユーザー ras
提出日時 2025-07-28 01:45:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 10,049 bytes
コンパイル時間 3,743 ms
コンパイル使用メモリ 305,900 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-28 01:45:46
合計ジャッジ時間 4,848 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "verify/ds/yuki-0875-Segtree.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/875"
#include <bits/stdc++.h>
#line 2 "cpstl/other/Fastio.hpp"
namespace cpstd {

// Fast I/O

// https://judge.yosupo.jp/submission/21623
// https://maspypy.com/library-checker-many-a-b

namespace Fastio {

static constexpr const uint32_t BUF_SIZE = 1 << 17;
char ibuf[BUF_SIZE], obuf[BUF_SIZE], out[100];
uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
	char num[10000][4];

	constexpr Pre() : num() {
		for (int i = 0; i < 10000; ++i) {
			int n = i;
			for (int j = 3; j >= 0; --j) {
				num[i][j] = n % 10 | '0';
				n /= 10;
			}
		}
	}
} constexpr pre;

inline void load() {
	std::memcpy(ibuf, ibuf + pil, pir - pil);
	pir = pir - pil +
	      std::fread(ibuf + pir - pil, 1, BUF_SIZE - pir + pil, stdin);
	pil = 0;
	if (pir < BUF_SIZE) ibuf[pir++] = '\n';
}

inline void flush() {
	fwrite(obuf, 1, por, stdout);
	por = 0;
}

void _input(char &dest) {
	do {
		if (pil + 1 > pir) load();
		dest = ibuf[pil++];
	} while (std::isspace(dest));
}

void _input(std::string &dest) {
	dest.clear();
	char c;
	do {
		if (pil + 1 > pir) load();
		c = ibuf[pil++];
	} while (std::isspace(c));
	do {
		dest += c;
		if (pil == pir) load();
		c = ibuf[pil++];
	} while (!std::isspace(c));
}

void _input(float &dest) {
	std::string s;
	_input(s);
	dest = std::stof(s);
}

void _input(double &dest) {
	std::string s;
	_input(s);
	dest = std::stod(s);
}

void _input(long double &dest) {
	std::string s;
	_input(s);
	dest = std::stold(s);
}

template <typename T>
void input_int(T &x) {
	if (pil + 100 > pir) load();
	char c;
	do {
		c = ibuf[pil++];
	} while (c < '-');
	bool minus = 0;
	if constexpr (std::is_signed<T>::value || std::is_same_v<T, __int128_t>) {
		if (c == '-') minus = 1, c = ibuf[pil++];
	}
	x = 0;
	while (c >= '0') x = x * 10 + (c & 15), c = ibuf[pil++];
	if constexpr (std::is_signed<T>::value || std::is_same_v<T, __int128_t>) {
		if (minus) x = -x;
	}
}

void _input(int &dest) { input_int(dest); }
void _input(unsigned int &dest) { input_int(dest); }
void _input(long long &dest) { input_int(dest); }
void _input(unsigned long long &dest) { input_int(dest); }
void _input(__int128 &dest) { input_int(dest); }
void _input(unsigned __int128 &dest) { input_int(dest); }

template <typename T, typename U>
void _input(std::pair<T, U> &dest) {
	return _input(dest.first), _input(dest.second);
}

template <std::size_t N = 0, typename T>
void input_tuple(T &t) {
	if constexpr (N < std::tuple_size<T>::value) {
		auto &x = std::get<N>(t);
		input(x);
		input_tuple<N + 1>(t);
	}
}

template <typename... T>
void _input(std::tuple<T...> &dest) {
	input_tuple(dest);
}

template <std::size_t N = 0, typename T>
void _input(std::array<T, N> &dest) {
	for (auto &e : dest) _input(e);
}

template <typename T>
void _input(std::vector<T> &dest) {
	for (auto &e : dest) _input(e);
}

void input() {}

// 各引数に入力
template <typename H, typename... T>
void input(H &desth, T &...destt) {
	_input(desth), input(destt...);
}

void _print(const char tg) {
	if (por == BUF_SIZE) flush();
	obuf[por++] = tg;
}

void _print(const std::string tg) {
	for (char c : tg) _print(c);
}

void _print(const char *tg) {
	std::size_t len = std::strlen(tg);
	for (std::size_t i = 0; i < len; ++i) _print(tg[i]);
}

template <typename T>
void print_int(T x) {
	if (por > BUF_SIZE - 100) flush();
	if (x < 0) obuf[por++] = '-', x = -x;
	int outi;
	for (outi = 96; x >= 10000; outi -= 4) {
		std::memcpy(out + outi, pre.num[x % 10000], 4);
		x /= 10000;
	}
	if (x >= 1000) {
		std::memcpy(obuf + por, pre.num[x], 4);
		por += 4;
	} else if (x >= 100) {
		std::memcpy(obuf + por, pre.num[x] + 1, 3);
		por += 3;
	} else if (x >= 10) {
		int q = (x * 103) >> 10;
		obuf[por] = q | '0';
		obuf[por + 1] = (x - q * 10) | '0';
		por += 2;
	} else
		obuf[por++] = x | '0';
	std::memcpy(obuf + por, out + outi + 4, 96 - outi);
	por += 96 - outi;
}

template <typename T>
void print_real(T tg) {
	std::ostringstream oss;
	oss << std::fixed << std::setprecision(15) << double(tg);
	std::string s = oss.str();
	_print(s);
}

void _print(int tg) { print_int(tg); }
void _print(unsigned int tg) { print_int(tg); }
void _print(long long tg) { print_int(tg); }
void _print(unsigned long long tg) { print_int(tg); }
void _print(__int128 tg) { print_int(tg); }
void _print(unsigned __int128 tg) { print_int(tg); }
void _print(float tg) { print_real(tg); }
void _print(double tg) { print_real(tg); }
void _print(long double tg) { print_real(tg); }

template <typename T, typename U>
void _print(const std::pair<T, U> tg) {
	_print(tg.first);
	_print(' ');
	_print(tg.second);
}

template <std::size_t N = 0, typename T>
void print_tuple(const T tg) {
	if constexpr (N < std::tuple_size<T>::value) {
		if constexpr (N > 0) _print(' ');
		const auto x = std::get<N>(tg);
		_print(x);
		print_tuple<N + 1>(tg);
	}
}

template <typename... T>
void _print(std::tuple<T...> tg) {
	print_tuple(tg);
}

template <typename T, std::size_t N>
void _print(const std::array<T, N> tg) {
	auto len = tg.size();
	for (std::size_t i = 0; i < len; ++i) {
		if (i) _print(' ');
		_print(tg[i]);
	}
}

template <typename T>
void _print(const std::vector<T> tg) {
	auto len = tg.size();
	for (std::size_t i = 0; i < len; ++i) {
		if (i) _print(' ');
		_print(tg[i]);
	}
}

void print() { _print('\n'); }

// 各引数を空白区切りで出力し改行
template <typename H, typename... T>
void print(H &&tgh, T &&...tgt) {
	_print(tgh);
	if (sizeof...(tgt)) _print(' ');
	print(std::forward<T>(tgt)...);
}

void __attribute__((destructor)) _d() { flush(); }

};  // namespace Fastio

using Fastio::flush;
using Fastio::input;
using Fastio::print;

};  // namespace cpstd
#line 2 "cpstl/ds/Segtree.hpp"

#line 4 "cpstl/ds/Segtree.hpp"

namespace cpstd {

// Segment Tree

template <typename S, auto op, auto e>
class Segtree {
   private:
	std::vector<S> dat;
	int N, sz;

   public:
	Segtree() {}
	explicit Segtree(int n) : Segtree(std::vector<S>(n, e())) {}
	explicit Segtree(int n, const S &init) : Segtree(std::vector<S>(n, init)) {}
	explicit Segtree(const std::vector<S> &v) : N((int)v.size()) {
		sz = 1;
		while (sz < N) sz <<= 1;
		dat.assign(sz << 1, e());
		for (int i = 0; i < N; ++i) dat[i + sz] = v[i];
		for (int i = sz - 1; i >= 1; --i)
			dat[i] = op(dat[i << 1], dat[i << 1 | 1]);
	}
	template <class Inputit>
	Segtree(Inputit first, Inputit last)
	    : Segtree(std::vector<S>(first, last)) {}

	// A[pos] ← x で更新
	// O(logN) time
	void set(int pos, const S &x) {
		assert(0 <= pos && pos < N);
		pos += sz;
		dat[pos] = x;
		while (pos > 1) {
			pos >>= 1;
			dat[pos] = op(dat[pos << 1], dat[pos << 1 | 1]);
		}
	}

	// A[pos] ← A[pos] + x で更新
	// O(logN) time
	void add(int pos, const S &x) {
		assert(0 <= pos && pos < N);
		pos += sz;
		dat[pos] += x;
		while (pos > 1) {
			pos >>= 1;
			dat[pos] = op(dat[pos << 1], dat[pos << 1 | 1]);
		}
	}

	// A[pos] ← mapping(f, A[pos]) で更新
	// O(logN) time
	template <typename F, auto mapping>
	void set(int pos, const F &f) {
		assert(0 <= pos && pos < N);
		pos += sz;
		dat[pos] = mapping(f, dat[pos]);
		while (pos > 1) {
			pos >>= 1;
			dat[pos] = op(dat[pos << 1], dat[pos << 1 | 1]);
		}
	}

	// A[pos] を返す
	// O(logN) time
	const S &get(int pos) const {
		assert(0 <= pos && pos < N);
		return dat[pos + sz];
	}

	// A[pos] を返す (assert なし)
	// O(logN) time
	const S &operator[](int pos) const noexcept { return dat[pos + sz]; }

	// op[l, r) を返す
	// O(logN) time
	S fold(int l, int r) const {
		assert(0 <= l && l <= r && r <= N);
		if (l == r) return e();
		S resl = e(), resr = e();
		for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
			if (l & 1) resl = op(resl, dat[l++]);
			if (r & 1) resr = op(dat[--r], resr);
		}
		return op(resl, resr);
	}

	// op[1, N] を返す
	// O(1) time
	S all_fold() const { return dat[1]; }

	// `r = l` または `f(op[l, r)) = true`
	// `r = n` または `f(op[l, r]) = false`
	// これらを両方満たす `r` を返す (`f` が単調なら `f(op[l, r)) = true`
	// となる最大の `r`) O(logN) time
	template <auto f>
	int max_right(int l) const {
		return max_right(l, [](const S &x) -> bool { return f(x); });
	}

	template <typename F>
	int max_right(int l, const F &f) const {
		assert(0 <= l && l <= N);
		assert(f(e()));
		if (l == N) return N;
		l += sz;
		S s = e();
		do {
			while (!(l & 1)) l >>= 1;
			if (!f(op(s, dat[l]))) {
				while (l < sz) {
					l <<= 1;
					if (f(op(s, dat[l]))) s = op(s, dat[l++]);
				}
				return l - sz;
			}
			s = op(s, dat[l++]);
		} while ((l & -l) != l);
		return N;
	}

	// `l = r` または `f(op[l, r)) = true`
	// `l = 0` または `f(op[l - 1, r)) = false`
	// これらを両方満たす `l` を返す (`f` が単調なら `f(op[l, r)) = true`
	// となる最小の `l`) O(logN) time
	template <auto f>
	int min_left(int r) const {
		return min_left(r, [](S x) -> bool { return f(x); });
	}

	template <typename F>
	int min_left(int r, F f) const {
		assert(0 <= r && r <= N);
		assert(f(e()));
		if (r == 0) return 0;
		r += sz;
		S s = e();
		do {
			--r;
			while (r > 1 && (r & 1)) r >>= 1;
			if (!f(op(dat[r], s))) {
				while (r < sz) {
					r = r << 1 | 1;
					if (f(op(dat[r], s))) s = op(dat[r--], s);
				}
				return r + 1 - sz;
			}
			s = op(dat[r], s);
		} while ((r & -r) != r);
		return 0;
	}
};
};  // namespace cpstd
#line 5 "verify/ds/yuki-0875-Segtree.test.cpp"

int op(int a, int b) { return std::min(a, b); }
int e() { return 100000000; }

int main() {
	int N, Q;
	cpstd::input(N, Q);
	std::vector<int> A(N);
	cpstd::input(A);
	cpstd::Segtree<int, op, e> sg(A);
	int t, l, r, lv;
	while (Q--) {
		cpstd::input(t, l, r);
		if (t == 1) {
			lv = sg[--l];
			sg.set(l, sg[--r]);
			sg.set(r, lv);
		} else {
			int mini = sg.fold(--l, r);
			int a1 = sg.max_right(l, [&](int x) -> bool { return x > mini; });
			int a2 = sg.min_left(r, [&](int x) -> bool { return x > mini; });
			--a2;
			assert(a1 == a2);
			cpstd::print(a1 + 1);
		}
	}
	return 0;
}
0