#644365 (C++17) No.1471 Sort Queries

提出ソース

結果

問題	No.1471 Sort Queries
ユーザー	nok0
提出日時	2021-04-04 11:14:21
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	41 ms / 2,000 ms
コード長	9,877 bytes
コンパイル時間	9,032 ms
コンパイル使用メモリ	336,428 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-08 02:39:45
合計ジャッジ時間	10,177 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	11 ms 5,376 KB
testcase_14	AC	11 ms 5,376 KB
testcase_15	AC	17 ms 5,376 KB
testcase_16	AC	11 ms 5,376 KB
testcase_17	AC	9 ms 5,376 KB
testcase_18	AC	7 ms 5,376 KB
testcase_19	AC	11 ms 5,376 KB
testcase_20	AC	16 ms 5,376 KB
testcase_21	AC	9 ms 5,376 KB
testcase_22	AC	8 ms 5,376 KB
testcase_23	AC	20 ms 5,376 KB
testcase_24	AC	20 ms 5,376 KB
testcase_25	AC	31 ms 5,376 KB
testcase_26	AC	24 ms 5,376 KB
testcase_27	AC	27 ms 5,376 KB
testcase_28	AC	26 ms 5,376 KB
testcase_29	AC	22 ms 5,376 KB
testcase_30	AC	21 ms 5,376 KB
testcase_31	AC	31 ms 5,376 KB
testcase_32	AC	34 ms 5,376 KB
testcase_33	AC	38 ms 5,376 KB
testcase_34	AC	39 ms 5,376 KB
testcase_35	AC	40 ms 5,376 KB
testcase_36	AC	39 ms 5,376 KB
testcase_37	AC	40 ms 5,376 KB
testcase_38	AC	39 ms 5,376 KB
testcase_39	AC	41 ms 5,376 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

template <int bit_size = 30>
struct WaveletMatrix {
	using u16 = unsigned short;
	using u64 = unsigned long long;

public:
	template <class T>
	WaveletMatrix(const std::vector<T> &vec) : n((u64)vec.size()) {
		assert(n > 0);
		matrix = std::vector<bitvector>(bit_size, bitvector(n));
		begin_one.resize(bit_size);

		std::vector<u64> v(n);
		for(u64 i = 0; i < n; i++) v[i] = vec[i];

		for(u64 i = 0; i < bit_size; i++) {
			std::vector<u64> tmp;
			for(u64 j = 0; j < n; j++) {
				const u64 bit = (v[j] >> (bit_size - 1 - i)) & 1;
				if(!bit) {
					tmp.emplace_back(v[j]);
					matrix[i].set(j, 0);
				}
			}
			begin_one[i] = (int)tmp.size();
			for(u64 j = 0; j < n; j++) {
				const u64 bit = (v[j] >> (bit_size - 1 - i)) & 1;
				if(bit) {
					tmp.emplace_back(v[j]);
					matrix[i].set(j, 1);
				}
			}
			matrix[i].build();
			v = tmp;
		}
		for(u64 i = 0; i < n; i++) begin_val[v[n - 1 - i]] = n - 1 - i;
	}

	WaveletMatrix(const std::string &vec) : n((u64)vec.size()) {
		assert(n > 0);
		matrix = std::vector<bitvector>(bit_size, bitvector(n));
		begin_one.resize(bit_size);

		std::vector<u64> v(n);
		for(u64 i = 0; i < n; i++) v[i] = vec[i];

		for(u64 i = 0; i < bit_size; i++) {
			std::vector<u64> tmp;
			for(u64 j = 0; j < n; j++) {
				const u64 bit = (v[j] >> (bit_size - 1 - i)) & 1;
				if(!bit) {
					tmp.emplace_back(v[j]);
					matrix[i].set(j, 0);
				}
			}
			begin_one[i] = (int)tmp.size();
			for(u64 j = 0; j < n; j++) {
				const u64 bit = (v[j] >> (bit_size - 1 - i)) & 1;
				if(bit) {
					tmp.emplace_back(v[j]);
					matrix[i].set(j, 1);
				}
			}
			matrix[i].build();
			v = tmp;
		}
		for(u64 i = 0; i < n; i++) begin_val[v[n - 1 - i]] = n - 1 - i;
	}

	u64 size() const noexcept { return n; }

	// return v[pos]
	u64 operator[](u64 pos) const {
		assert(pos < n);
		u64 ret = 0;
		for(u64 i = 0; i < bit_size; i++) {
			const u64 bit = matrix[i].access(pos);
			ret = ret << 1 | bit;
			pos = matrix[i].rank(pos, bit);
			if(bit) pos += begin_one[i];
		}
		return ret;
	}

	//return the number of val in [0, pos)
	u64 rank(u64 pos, const u64 val) {
		assert(pos <= n);
		if(!begin_val.count(val)) return 0;
		for(u64 i = 0; i < bit_size; i++) {
			const u64 bit = (val >> (bit_size - 1 - i)) & 1;
			pos = matrix[i].rank(pos, bit);
			if(bit) pos += begin_one[i];
		}
		return pos - begin_val[val];
	}

	//return the number of val in [l, r)
	u64 rank(u64 l, u64 r, const u64 val) {
		assert(l <= r);
		return rank(r, val) - rank(l, val);
	}

	//return the number of less than val
	u64 rank_less_than(u64 l, u64 r, const u64 val) const {
		[[maybe_unused]] auto [ig0, ret, ig1] = rank_all(l, r, val);
		return ret;
	}

	//return the number of more than val
	u64 rank_more_than(u64 l, u64 r, const u64 val) const {
		[[maybe_unused]] auto [ig0, ig1, ret] = rank_all(l, r, val);
		return ret;
	}

	//return tuple[the number of val, the number of less than val, the number of more than val] in [l, r)
	std::tuple<u64, u64, u64> rank_all(u64 l, u64 r, const u64 val) const {
		assert(l <= r);
		assert(r <= n);
		if(l == r) return std::make_tuple(0, 0, 0);
		const u64 len = r - l;

		u64 rank_less = 0, rank_more = 0;
		for(u64 i = 0; i < bit_size and l < r; i++) {
			const u64 bit = val >> bit_size - 1 - i & 1;
			const u64 rank0_l = matrix[i].rank(l, 0);
			const u64 rank0_r = matrix[i].rank(r, 0);
			const u64 rank1_l = l - rank0_l;
			const u64 rank1_r = r - rank0_r;
			if(bit) {
				rank_less += rank0_r - rank0_l;
				l = begin_one[i] + rank1_l;
				r = begin_one[i] + rank1_r;
			} else {
				rank_more += rank1_r - rank1_l;
				l = rank0_l;
				r = rank0_r;
			}
		}
		return std::make_tuple(len - rank_less - rank_more, rank_less, rank_more);
	}

	//return the number of (min_val or more, and less than max_val) in [l, r)
	u64 frequency(u64 l, u64 r, const u64 min_val, const u64 max_val) {
		[[maybe_unused]] auto [ig0, max_ret, ig1] = rank_all(l, r, max_val);
		[[maybe_unused]] auto [ig2, min_ret, ig3] = rank_all(l, r, min_val);
		return max_ret - min_ret;
	}

	//return the position of k'th val
	u64 select(const u64 val, const u64 k) {
		if(!begin_val.count(val)) return n;
		u64 idx = begin_val[val] + k + 1;
		for(u64 i = 0; i < bit_size; i++) {
			const u64 bit = val >> i & 1;
			if(bit == 1) idx -= begin_one[bit_size - 1 - i];
			idx = matrix[bit_size - 1 - i].select(idx, bit);
		}
		return std::min(idx - 1, n);
	}

	// return the position of k'th smallest element in [l, r)
	u64 quantile(u64 l, u64 r, u64 k) {
		assert(l <= r and r <= n);
		assert(k < r - l);
		u64 val = 0;
		for(u64 i = 0; i < bit_size; i++) {
			const u64 num_zero_l = matrix[i].rank(l, 0);
			const u64 num_zero_r = matrix[i].rank(r, 0);
			const u64 num_zero = num_zero_r - num_zero_l;
			const u64 bit = (k < num_zero ? 0 : 1);
			if(bit) {
				k -= num_zero;
				l += begin_one[i] - num_zero_l;
				r += begin_one[i] - num_zero_r;
			} else {
				l = num_zero_l;
				r = num_zero_r;
			}
			val = val << 1 | bit;
		}
		u64 lef = 0;
		for(u64 i = 0; i < bit_size; i++) {
			const u64 bit = val >> bit_size - 1 - i & 1;
			lef = matrix[i].rank(lef, bit);
			if(bit) lef += begin_one[i];
		}
		const u64 sel_k = l + k - lef;
		return select(val, sel_k);
	}

	// return the position of the smallest element in [l, r)
	u64 min_place(u64 l, u64 r) const { return quantile(l, r, 0); }

	// return the position of the largest element in [l, r)
	u64 max_place(u64 l, u64 r) const { return quantile(l, r, r - l - 1); }

private:
	static u64 popcount(u64 c) {
#ifdef __has_builtin
		return __builtin_popcountll(c);
#else
		c = (c & 0x5555555555555555ULL) + (c >> 1 & 0x5555555555555555ULL);
		c = (c & 0x3333333333333333ULL) + (c >> 2 & 0x3333333333333333ULL);
		c = (c + (c >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
		c = c + (c >> 8);
		c = c + (c >> 16);
		c = c + (c >> 32);
		return c & 0x7f;
#endif
	}

	struct bitvector {
	public:
		explicit bitvector(const u64 n) : n(n), bit((n + bnum - 1) / bnum + 1), chunk(n / cw + 1), blocks(n / bw + 1) {}

		void set(u64 pos, u64 b = 1) {
			assert(pos < n);
			assert(b == 0 or b == 1);
			u64 bpos = pos / bnum, offset = pos % bnum;
			if(b == 0)
				bit[bpos] &= ~(1llu << offset);
			else
				bit[bpos] |= (1llu << offset);
		}

		u16 access(u64 pos) const {
			assert(pos < n);
			u64 bpos = pos / bnum, offset = pos % bnum;
			return bit[bpos] >> offset & 1;
		}

		void build() {
			u64 tmp = 0;
			chunk[0] = 0;
			for(u64 i = 0; i <= n; i++) {
				if(i % cw == 0) chunk[i / cw] = tmp;
				if(i % bw == 0) blocks[i / bw] = tmp - chunk[i / cw];
				if(i != n and i % bnum == 0) tmp += popcount(bit[i / bnum]);
			}
		}

		// return the number of b in [0, pos)
		u64 rank(u64 pos, u64 b = 1) const {
			assert(pos <= n);
			assert(b == 0 or b == 1);
			if(b) {
				const u64 offset = pos % bnum;
				const u16 masked = bit[pos / bnum] & (1 << offset) - 1;
				return chunk[pos / cw] + blocks[pos / bw] + popcount(masked);
			} else
				return pos - rank(pos, 1);
		}

		u64 select(u64 num, u64 b = 1) const {
			assert(b == 0 or b == 1);
			if(num == 0) return 0;
			if(rank(n, b) < num) return n;
			u64 large_idx = 0;
			{
				u64 ok = large_idx, ng = n / cw + 1, mid = 0;
				while(mid = (ok + ng) / 2, ng - ok > 1) {
					u64 r = chunk[mid];
					if(b == 0) r = mid * cw - r;

					if(r < num)
						ok = mid, large_idx = mid;
					else
						ng = mid;
				}
			}
			u64 small_idx = large_idx * cw / bw;
			{
				u64 ok = small_idx, ng = std::min((large_idx + 1) * cw / bw, n / bw + 1), mid = 0;
				while(mid = (ok + ng) / 2, ng - ok > 1) {
					u64 r = chunk[large_idx] + blocks[mid];
					if(b == 0) r = mid * bw - r;
					if(r < num)
						ok = mid, small_idx = mid;
					else
						ng = mid;
				}
			}
			u64 rank_pos = 0;
			{
				u64 sum = chunk[large_idx] + blocks[small_idx];
				if(b == 0) sum = small_idx * bw - sum;
				for(u64 i = 0;; i++) {
					u64 tmp = popcount(bit[small_idx + i]);
					if(b == 0) tmp = bnum - tmp;
					if(sum + tmp >= num) {
						u64 block_idx = (b == 1 ? bit[small_idx + i] : ~bit[small_idx + i]);
						auto select_in_block = [&](u64 x, u64 num) -> u64 {
							uint64_t x1 = x - ((x & 0xAAAAAAAAAAAAAAAALLU) >> 1);
							uint64_t x2 = (x1 & 0x3333333333333333LLU) + ((x1 >> 2) & 0x3333333333333333LLU);
							uint64_t x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLLU;

							uint64_t pos = 0;
							for(;; pos += 8) {
								uint64_t rank_next = (x3 >> pos) & 0xFFLLU;
								if(num <= rank_next) break;
								num -= rank_next;
							}

							uint64_t v2 = (x2 >> pos) & 0xFLLU;
							if(num > v2) {
								num -= v2;
								pos += 4;
							}

							uint64_t v1 = (x1 >> pos) & 0x3LLU;
							if(num > v1) {
								num -= v1;
								pos += 2;
							}

							uint64_t v0 = (x >> pos) & 0x1LLU;
							if(v0 < num) {
								num -= v0;
								pos += 1;
							}
							return pos;
						};
						rank_pos = (small_idx + i) * bnum + select_in_block(block_idx, num - sum);
						break;
					}
					sum += tmp;
				}
			}
			return rank_pos + 1;
		}

	private:
		static constexpr u64 cw = 512, bw = 16, bnum = 16;
		const u64 n;
		std::vector<u16> bit;
		std::vector<u64> chunk;
		std::vector<u16> blocks;
	};

	std::vector<bitvector> matrix;
	std::vector<u64> begin_one;
	std::unordered_map<u64, u64> begin_val;
	const u64 n;
};

#include "testlib.h"

int n, q, l, r, x;
std::string s;

int main() {
	registerValidation();
	n = inf.readInt(1, 10000);
	inf.readSpace();
	q = inf.readInt(1, 10000);
	inf.readEoln();
	s = inf.readString();
	for(auto &c : s) {
		assert('a' <= c and c <= 'z');
	}
	assert(s.size() == n);
	WaveletMatrix mat(s);
	while(q--) {
		l = inf.readInt(1, n);
		inf.readSpace();
		r = inf.readInt(l, n);
		inf.readSpace();
		x = inf.readInt(1, r - l + 1);
		inf.readEoln();
		std::cout << (char)(mat[mat.quantile(--l, r, --x)]) << '\n';
	}
	inf.readEof();
	return 0;
}

yukicoder

結果

テストケース

ソースコード