結果
問題 | No.1332 Range Nearest Query |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-23 01:23:25 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 889 ms / 2,500 ms |
コード長 | 4,451 bytes |
コンパイル時間 | 11,753 ms |
コンパイル使用メモリ | 225,336 KB |
実行使用メモリ | 21,120 KB |
最終ジャッジ日時 | 2024-09-18 15:12:46 |
合計ジャッジ時間 | 44,642 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 785 ms
19,584 KB |
testcase_04 | AC | 721 ms
19,584 KB |
testcase_05 | AC | 729 ms
19,584 KB |
testcase_06 | AC | 615 ms
17,408 KB |
testcase_07 | AC | 614 ms
17,920 KB |
testcase_08 | AC | 623 ms
17,408 KB |
testcase_09 | AC | 611 ms
19,712 KB |
testcase_10 | AC | 612 ms
17,408 KB |
testcase_11 | AC | 642 ms
17,920 KB |
testcase_12 | AC | 614 ms
17,920 KB |
testcase_13 | AC | 615 ms
17,920 KB |
testcase_14 | AC | 628 ms
17,920 KB |
testcase_15 | AC | 613 ms
17,920 KB |
testcase_16 | AC | 766 ms
17,408 KB |
testcase_17 | AC | 760 ms
21,120 KB |
testcase_18 | AC | 784 ms
21,120 KB |
testcase_19 | AC | 781 ms
21,120 KB |
testcase_20 | AC | 768 ms
21,120 KB |
testcase_21 | AC | 759 ms
21,120 KB |
testcase_22 | AC | 757 ms
21,120 KB |
testcase_23 | AC | 766 ms
17,408 KB |
testcase_24 | AC | 789 ms
21,120 KB |
testcase_25 | AC | 889 ms
21,120 KB |
testcase_26 | AC | 513 ms
20,992 KB |
testcase_27 | AC | 466 ms
20,992 KB |
testcase_28 | AC | 139 ms
5,376 KB |
testcase_29 | AC | 143 ms
5,376 KB |
testcase_30 | AC | 144 ms
5,376 KB |
testcase_31 | AC | 136 ms
5,376 KB |
testcase_32 | AC | 148 ms
5,376 KB |
testcase_33 | AC | 146 ms
5,376 KB |
testcase_34 | AC | 139 ms
5,376 KB |
testcase_35 | AC | 141 ms
5,376 KB |
testcase_36 | AC | 143 ms
5,376 KB |
testcase_37 | AC | 144 ms
5,376 KB |
testcase_38 | AC | 664 ms
13,952 KB |
testcase_39 | AC | 394 ms
5,760 KB |
testcase_40 | AC | 853 ms
17,536 KB |
testcase_41 | AC | 468 ms
6,144 KB |
testcase_42 | AC | 613 ms
13,056 KB |
testcase_43 | AC | 529 ms
7,296 KB |
testcase_44 | AC | 685 ms
17,920 KB |
testcase_45 | AC | 656 ms
16,896 KB |
testcase_46 | AC | 570 ms
12,416 KB |
testcase_47 | AC | 734 ms
13,952 KB |
ソースコード
package main import ( "bufio" "fmt" "math/bits" "os" ) func main() { 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, -1) 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.Ceiling(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:如果要支持异或,则需要按照异或的值来决定值域 // 设为-1时表示不使用异或 func NewWaveletMatrixXor(nums []int, log int) *WaveletMatrixXor { numsCopy := make([]int, len(nums)) max_ := 0 for i, v := range nums { numsCopy[i] = v if v > max_ { max_ = v } } if log == -1 { log = bits.Len(uint(max_)) + 1 } res := &WaveletMatrixXor{} n := len(numsCopy) 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 := (numsCopy[i] >> d) & 1 if f == 0 { a0[p0] = numsCopy[i] p0++ } else { bv[d].Set(i) a1[p1] = numsCopy[i] p1++ } } mid[d] = p0 bv[d].Build() numsCopy, a0 = a0, numsCopy for i := 0; i < p1; i++ { numsCopy[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) Floor(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) Ceiling(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) } 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 }