結果
問題 | No.1332 Range Nearest Query |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-13 13:50:55 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 902 ms / 2,500 ms |
コード長 | 4,878 bytes |
コンパイル時間 | 10,468 ms |
コンパイル使用メモリ | 228,416 KB |
実行使用メモリ | 20,508 KB |
最終ジャッジ日時 | 2024-09-18 07:31:35 |
合計ジャッジ時間 | 44,241 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 816 ms
18,392 KB |
testcase_04 | AC | 829 ms
18,388 KB |
testcase_05 | AC | 823 ms
20,488 KB |
testcase_06 | AC | 711 ms
20,460 KB |
testcase_07 | AC | 726 ms
20,460 KB |
testcase_08 | AC | 715 ms
20,460 KB |
testcase_09 | AC | 727 ms
20,460 KB |
testcase_10 | AC | 720 ms
20,460 KB |
testcase_11 | AC | 725 ms
20,460 KB |
testcase_12 | AC | 695 ms
20,504 KB |
testcase_13 | AC | 722 ms
20,460 KB |
testcase_14 | AC | 703 ms
20,460 KB |
testcase_15 | AC | 714 ms
20,460 KB |
testcase_16 | AC | 902 ms
14,396 KB |
testcase_17 | AC | 871 ms
20,460 KB |
testcase_18 | AC | 849 ms
14,396 KB |
testcase_19 | AC | 851 ms
20,460 KB |
testcase_20 | AC | 857 ms
20,460 KB |
testcase_21 | AC | 873 ms
14,396 KB |
testcase_22 | AC | 843 ms
20,504 KB |
testcase_23 | AC | 850 ms
20,508 KB |
testcase_24 | AC | 836 ms
20,460 KB |
testcase_25 | AC | 855 ms
14,396 KB |
testcase_26 | AC | 470 ms
20,504 KB |
testcase_27 | AC | 559 ms
20,508 KB |
testcase_28 | AC | 329 ms
6,940 KB |
testcase_29 | AC | 331 ms
6,940 KB |
testcase_30 | AC | 330 ms
6,944 KB |
testcase_31 | AC | 320 ms
6,940 KB |
testcase_32 | AC | 338 ms
6,944 KB |
testcase_33 | AC | 326 ms
6,940 KB |
testcase_34 | AC | 324 ms
6,940 KB |
testcase_35 | AC | 322 ms
6,940 KB |
testcase_36 | AC | 324 ms
6,940 KB |
testcase_37 | AC | 330 ms
6,944 KB |
testcase_38 | AC | 716 ms
14,148 KB |
testcase_39 | AC | 530 ms
7,836 KB |
testcase_40 | AC | 859 ms
14,396 KB |
testcase_41 | AC | 614 ms
7,928 KB |
testcase_42 | AC | 708 ms
12,064 KB |
testcase_43 | AC | 660 ms
8,064 KB |
testcase_44 | AC | 799 ms
18,428 KB |
testcase_45 | AC | 773 ms
12,280 KB |
testcase_46 | AC | 703 ms
12,204 KB |
testcase_47 | AC | 759 ms
14,224 KB |
ソースコード
package main import ( "bufio" "fmt" "math/bits" "os" ) func main() { // https://yukicoder.me/problems/no/1332 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int fmt.Fscan(in, &n) nums := make([]int, n) for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) } M := NewWaveletMatrixXor(nums, 32) var q int fmt.Fscan(in, &q) for i := 0; i < q; i++ { var left, right, x int fmt.Fscan(in, &left, &right, &x) left-- res := INF lower := M.Floor(left, right, x, 0) // 严格小于x的最大值 if lower != -INF { res = min(res, abs(lower-x)) } higher := M.Ceil(left, right, x, 0) // 严格大于x的最小值 if higher != INF { res = min(res, abs(higher-x)) } fmt.Fprintln(out, res) } } func min(a, b int) int { if a < b { return a } return b } func abs(a int) int { if a < 0 { return -a } return a } const INF int = 1e18 type WaveletMatrixXor struct { n, log int mid []int bv []*BitVector } // log:所有数不超过 2^log-1 , 1e9时一般设为32 // 如果要支持异或,则需要按照异或的值来决定值域 func NewWaveletMatrixXor(data []int, log int) *WaveletMatrixXor { data = append(data[:0:0], data...) res := &WaveletMatrixXor{} n := len(data) mid := make([]int, log) bv := make([]*BitVector, log) for i := 0; i < log; i++ { bv[i] = NewBitVector(n) } a0, a1 := make([]int, n), make([]int, n) for d := log - 1; d >= 0; d-- { p0, p1 := 0, 0 for i := 0; i < n; i++ { f := (data[i] >> d) & 1 if f == 0 { a0[p0] = data[i] p0++ } else { bv[d].Set(i) a1[p1] = data[i] p1++ } } mid[d] = p0 bv[d].Build() data, a0 = a0, data for i := 0; i < p1; i++ { data[p0+i] = a1[i] } } res.n = n res.log = log res.mid = mid res.bv = bv return res } // [left, right) 中位于 `[a,b)` 的数的個数 func (wm *WaveletMatrixXor) Count(left, right, a, b, xor int) int { return wm.CountPrefix(left, right, b, xor) - wm.CountPrefix(left, right, a, xor) } // [left, right) 中位于 `[0,x)` 的数的個数 func (wm *WaveletMatrixXor) CountPrefix(left, right, x, xor int) int { if x >= 1<<wm.log { return right - left } res := 0 for d := wm.log - 1; d >= 0; d-- { add := x >> d & 1 f := (x ^ xor) >> d & 1 if add != 0 { res += wm.bv[d].Rank(right, f^1) - wm.bv[d].Rank(left, f^1) } left = wm.bv[d].Rank(left, f) + (f * wm.mid[d]) right = wm.bv[d].Rank(right, f) + (f * wm.mid[d]) } return res } // [left, right) 中的第 k 小的數(k>=0),如果不存在則返回-1 func (wm *WaveletMatrixXor) Kth(left, right, k, xor int) int { if k < 0 || k >= right-left { return -1 } res := 0 for d := wm.log - 1; d >= 0; d-- { f := (xor >> d) & 1 l0 := wm.bv[d].Rank(left, 0) r0 := wm.bv[d].Rank(right, 0) var kf int if f == 0 { kf = r0 - l0 } else { kf = right - left - (r0 - l0) } if k < kf { if f == 0 { left = l0 right = r0 } else { left += wm.mid[d] - l0 right += wm.mid[d] - r0 } } else { k -= kf res |= 1 << d if f == 0 { left += wm.mid[d] - l0 right += wm.mid[d] - r0 } else { left = l0 right = r0 } } } return res } // [left, right) 中严格小于 x 的数中最大的数,如果不存在则返回-INF func (w *WaveletMatrixXor) Lower(start, end, value, xor int) int { less := w.CountPrefix(start, end, value, xor) if less == 0 { return -INF } return w.Kth(start, end, less-1, xor) } // [left, right) 中严格大于 x 的数中最小的数,如果不存在则返回INF func (w *WaveletMatrixXor) Higher(start, end, value, xor int) int { less := w.CountPrefix(start, end, value, xor) if less == end-start { return INF } return w.Kth(start, end, less, xor) } // [left, right) 中小于等于 x 的数中最大的数,如果不存在则返回-INF func (w *WaveletMatrixXor) Floor(start, end, value, xor int) int { same := w.Count(start, end, value, value+1, xor) if same > 0 { return value } return w.Lower(start, end, value, xor) } // [left, right) 中大于等于 x 的数中最小的数,如果不存在则返回INF func (w *WaveletMatrixXor) Ceil(start, end, value, xor int) int { same := w.Count(start, end, value, value+1, xor) if same > 0 { return value } return w.Higher(start, end, value, xor) } type BitVector struct { data [][2]int } func NewBitVector(n int) *BitVector { return &BitVector{data: make([][2]int, (n+63)>>5)} } func (bv *BitVector) Set(i int) { bv.data[i>>5][0] |= 1 << (i & 31) } func (bv *BitVector) Build() { for i := 0; i < len(bv.data)-1; i++ { bv.data[i+1][1] = bv.data[i][1] + bits.OnesCount(uint(bv.data[i][0])) } } // [0, k) 内1的個数 func (bv *BitVector) Rank(k int, f int) int { a, b := bv.data[k>>5][0], bv.data[k>>5][1] ret := b + bits.OnesCount(uint(a&((1<<(k&31))-1))) if f == 1 { return ret } return k - ret }