結果
| 問題 |
No.1471 Sort Queries
|
| コンテスト | |
| ユーザー |
 nok0
|
| 提出日時 | 2021-04-04 09:56:43 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 76 ms / 2,000 ms |
| コード長 | 9,538 bytes |
| コンパイル時間 | 3,537 ms |
| コンパイル使用メモリ | 215,256 KB |
| 最終ジャッジ日時 | 2025-01-20 10:59:28 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
#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;
};
int n, q, l, r, x;
std::string s;
int main() {
std::cin >> n >> q >> s;
WaveletMatrix mat(s);
while(q--) {
std::cin >> l >> r >> x;
std::cout << (char)(mat[mat.quantile(--l, r, --x)]) << '\n';
}
return 0;
}