#848808 (Go) No.1332 Range Nearest Query

• 問題: No.1332 Range Nearest Query
• ユーザー: 草苺奶昔
• 提出日時: 2023-03-13 16:53:56
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 1,002 ms / 2,500 ms
• コード長: 9,513 bytes
• コンパイル時間: 10,605 ms
• コンパイル使用メモリ: 223,200 KB
• 実行使用メモリ: 96,804 KB
• 最終ジャッジ日時: 2024-09-18 07:37:41
• 合計ジャッジ時間: 45,320 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	3 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	898 ms; 85,892 KB
testcase_04	AC	884 ms; 85,892 KB
testcase_05	AC	920 ms; 85,884 KB
testcase_06	AC	802 ms; 95,384 KB
testcase_07	AC	689 ms; 93,208 KB
testcase_08	AC	720 ms; 93,848 KB
testcase_09	AC	698 ms; 95,384 KB
testcase_10	AC	650 ms; 93,720 KB
testcase_11	AC	673 ms; 93,592 KB
testcase_12	AC	685 ms; 94,240 KB
testcase_13	AC	713 ms; 95,380 KB
testcase_14	AC	672 ms; 95,380 KB
testcase_15	AC	688 ms; 95,376 KB
testcase_16	AC	928 ms; 96,660 KB
testcase_17	AC	916 ms; 96,784 KB
testcase_18	AC	900 ms; 92,568 KB
testcase_19	AC	925 ms; 92,056 KB
testcase_20	AC	934 ms; 96,664 KB
testcase_21	AC	915 ms; 93,084 KB
testcase_22	AC	893 ms; 91,544 KB
testcase_23	AC	931 ms; 96,660 KB
testcase_24	AC	1,002 ms; 93,824 KB
testcase_25	AC	893 ms; 96,804 KB
testcase_26	AC	516 ms; 93,220 KB
testcase_27	AC	477 ms; 95,148 KB
testcase_28	AC	196 ms; 6,944 KB
testcase_29	AC	200 ms; 6,940 KB
testcase_30	AC	199 ms; 6,940 KB
testcase_31	AC	189 ms; 6,944 KB
testcase_32	AC	208 ms; 6,940 KB
testcase_33	AC	205 ms; 6,940 KB
testcase_34	AC	200 ms; 6,940 KB
testcase_35	AC	192 ms; 6,940 KB
testcase_36	AC	212 ms; 6,944 KB
testcase_37	AC	203 ms; 6,948 KB
testcase_38	AC	695 ms; 55,388 KB
testcase_39	AC	379 ms; 9,944 KB
testcase_40	AC	874 ms; 92,224 KB
testcase_41	AC	466 ms; 26,580 KB
testcase_42	AC	708 ms; 53,348 KB
testcase_43	AC	634 ms; 36,876 KB
testcase_44	AC	858 ms; 77,964 KB
testcase_45	AC	797 ms; 65,568 KB
testcase_46	AC	702 ms; 49,256 KB
testcase_47	AC	737 ms; 61,524 KB

ソースコード

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func 区间最短距离和() {
	// https://yukicoder.me/problems/no/924
	// n,q<=2e5
	// -1e9 <= nums[i] <= 1e9
	// 给定n个查询[l,r]
	// !求区间[l,r]中位数到区间[l,r]中每个数的距离之和
	// !也就求函数 f(x)= ∑|nums[i]-x| (l<=i<=right) 的最小值
	// !区间中位数
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, q int
	fmt.Fscan(in, &n, &q)
	OFFSET := int(1e9 + 10)
	nums := make([]int, n)
	for i := range nums {
		fmt.Fscan(in, &nums[i])
		nums[i] += OFFSET
	}
	preSum := make([]int, n+1)
	for i := range nums {
		preSum[i+1] = preSum[i] + nums[i]
	}

	wm := NewWaveletMatrixSum(nums, 32+2)
	for i := 0; i < q; i++ {
		var left, right int
		fmt.Fscan(in, &left, &right)
		left--

		n := right - left
		lowerCount := n / 2
		ceilCount := n - lowerCount
		mid, lowerSum := wm.Kth(left, right, lowerCount, 0)
		_, allSum := wm.Kth(left, right, n, 0)
		ceilSum := allSum - lowerSum

		res := 0
		res += mid*lowerCount - lowerSum
		res += ceilSum - mid*ceilCount
		fmt.Fprintln(out, res)
	}
}

func main() {
	// nums := []int{3, 1, 2, 4, 5, 6, 7, 8, 9, 10}
	// wm := NewWaveletMatrixSum(nums, 32)
	// fmt.Println(wm.MaxRightValue(0, 10, 0, func(preSum E) bool { return preSum < 11 })) // 5 即值域在 [0,5) 中的数的和小于 11
	// fmt.Println(wm.MaxRightCount(0, 10, 0, func(preSum E) bool { return preSum < 11 })) // 4 即排序后前 4 个数的和小于 11
	// fmt.Println(wm.Ceil(0, 10, 3, 0))
	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 := NewWaveletMatrixSum(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
}

const INF int = 1e18

type E = int

func (*WaveletMatrixSum) e() E        { return 0 }
func (*WaveletMatrixSum) op(a, b E) E { return a + b }
func (*WaveletMatrixSum) inv(a E) E   { return -a }

type WaveletMatrixSum struct {
	n, log int
	mid    []int
	bv     []*BitVector
	preSum [][]int
}

func NewWaveletMatrixSum(nums []int, log int) *WaveletMatrixSum {
	nums = append(nums[:0:0], nums...)
	res := &WaveletMatrixSum{}
	n := len(nums)
	mid := make([]int, log)
	bv := make([]*BitVector, log)
	for i := 0; i < log; i++ {
		bv[i] = NewBitVector(n)
	}
	preSum := make([][]int, log+1)
	for i := range preSum {
		preSum[i] = make([]int, n+1)
		for j := range preSum[i] {
			preSum[i][j] = res.e()
		}
	}

	a0, a1 := make([]int, n), make([]int, n)
	for d := log - 1; d >= -1; d-- {
		p0, p1 := 0, 0
		for i := 0; i < n; i++ {
			preSum[d+1][i+1] = res.op(preSum[d+1][i], nums[i])
		}
		if d == -1 {
			break
		}
		for i := 0; i < n; i++ {
			f := (nums[i] >> d) & 1
			if f == 0 {
				a0[p0] = nums[i]
				p0++
			} else {
				bv[d].Set(i)
				a1[p1] = nums[i]
				p1++
			}
		}
		mid[d] = p0
		bv[d].Build()
		nums, a0 = a0, nums
		for i := 0; i < p1; i++ {
			nums[p0+i] = a1[i]
		}
	}

	res.n, res.log = n, log
	res.mid, res.bv, res.preSum = mid, bv, preSum
	return res
}

// 返回区间 [left, right) 中 范围在 [a, b) 中的 (元素的个数, op 的结果)
func (wm *WaveletMatrixSum) Count(left, right, a, b, xor int) (int, E) {
	c1, s1 := wm.CountPrefix(left, right, a, xor)
	c2, s2 := wm.CountPrefix(left, right, b, xor)
	return c2 - c1, wm.op(wm.inv(s1), s2)
}

// 返回区间 [left, right) 中 范围在 [0, x) 中的 (元素的个数, op 的结果)
func (wm *WaveletMatrixSum) CountPrefix(left, right, x, xor int) (int, E) {
	if x >= 1<<wm.log {
		return right - left, wm.get(wm.log, left, right)
	}
	count := 0
	sum := wm.e()
	for d := wm.log - 1; d >= 0; d-- {
		add := (x >> d) & 1
		f := (xor >> d) & 1
		l0, r0 := wm.bv[d].Rank(left, 0), wm.bv[d].Rank(right, 0)
		var kf int
		if f == 0 {
			kf = r0 - l0
		} else {
			kf = (right - left) - (r0 - l0)
		}
		if add == 1 {
			count += kf
			if f == 1 {
				sum = wm.op(sum, wm.get(d, left+wm.mid[d]-l0, right+wm.mid[d]-r0))
				left, right = l0, r0
			} else {
				sum = wm.op(sum, wm.get(d, l0, r0))
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		} else {
			if f == 0 {
				left, right = l0, r0
			} else {
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		}
	}

	return count, sum
}

// 返回区间 [left, right) 中的 (第k小的元素, 前k个元素(不包括第k小的元素) 的 op 的结果)
//  如果k < 0, 返回 (-1, 0); 如果k >= right-left, 返回 (-1, 区间 op 的结果)
func (wm *WaveletMatrixSum) Kth(left, right, k, xor int) (int, E) {
	if k < 0 {
		return -1, 0
	}
	if right-left <= k {
		return -1, wm.get(wm.log, left, right)
	}
	res, sum := 0, wm.e()
	for d := wm.log - 1; d >= 0; d-- {
		f := (xor >> d) & 1
		l0, r0 := wm.bv[d].Rank(left, 0), 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, right = l0, r0
			} else {
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		} else {
			k -= kf
			res |= 1 << d
			if f == 1 {
				sum = wm.op(sum, wm.get(d, left+wm.mid[d]-l0, right+wm.mid[d]-r0))
				left, right = l0, r0
			} else {
				sum = wm.op(sum, wm.get(d, l0, r0))
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		}
	}

	if k != 0 {
		sum = wm.op(sum, wm.get(0, left, left+k))
	}
	return res, sum
}

// 返回使得 check(prefixSum) 为 true 的最大值 val.
//  !(即区间内小于 val 的数的和 prefixSum 满足 check函数, 找到这样的最大的 val)
//  如果整个区间都满足, 返回 INF.
//  eg: val = 5 => 即区间内值域在 [0,5) 中的数的和满足 check 函数.
func (wm *WaveletMatrixSum) MaxRightValue(left, right, xor int, check func(preSum E) bool) E {
	if check(wm.get(wm.log, left, right)) {
		return INF
	}
	res := 0
	sum := wm.e()
	for d := wm.log - 1; d >= 0; d-- {
		f := (xor >> d) & 1
		l0, r0 := wm.bv[d].Rank(left, 0), wm.bv[d].Rank(right, 0)
		var loSum E
		if f == 0 {
			loSum = wm.get(d, l0, r0)
		} else {
			loSum = wm.get(d, left+wm.mid[d]-l0, right+wm.mid[d]-r0)
		}
		if check(wm.op(sum, loSum)) {
			sum = wm.op(sum, loSum)
			res |= 1 << d
			if f == 1 {
				left, right = l0, r0
			} else {
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		} else {
			if f == 0 {
				left, right = l0, r0
			} else {
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		}
	}

	return res
}

// 返回使得 check(prefixSum) 为 true 的区间前缀个数的最大值.
//  eg: count = 4 => 即区间内的数排序后, 前4个数的和满足 check 函数.
func (wm *WaveletMatrixSum) MaxRightCount(left, right, xor int, check func(preSum E) bool) int {
	if check(wm.get(wm.log, left, right)) {
		return right - left
	}
	res := 0
	sum := wm.e()
	for d := wm.log - 1; d >= 0; d-- {
		f := (xor >> d) & 1
		l0, r0 := wm.bv[d].Rank(left, 0), wm.bv[d].Rank(right, 0)
		var kf int
		var loSum E
		if f == 0 {
			kf = r0 - l0
			loSum = wm.get(d, l0, r0)
		} else {
			kf = (right - left) - (r0 - l0)
			loSum = wm.get(d, left+wm.mid[d]-l0, right+wm.mid[d]-r0)
		}

		if check(wm.op(sum, loSum)) {
			sum = wm.op(sum, loSum)
			res += kf
			if f == 1 {
				left, right = l0, r0
			} else {
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		} else {
			if f == 0 {
				left, right = l0, r0
			} else {
				left, right = left+wm.mid[d]-l0, right+wm.mid[d]-r0
			}
		}
	}

	res += wm.binarySearch(func(k int) bool {
		return check(wm.op(sum, wm.get(0, left, left+k)))
	}, 0, right-left)

	return res
}

// [left, right) 中小于等于 x 的数中最大的数
//  如果不存在则返回-INF
func (w *WaveletMatrixSum) Floor(start, end, value, xor int) int {
	less, _ := w.CountPrefix(start, end, value, xor)
	if less == 0 {
		return -INF
	}
	res, _ := w.Kth(start, end, less-1, xor)
	return res
}

// [left, right) 中大于等于 x 的数中最小的数
//  如果不存在则返回INF
func (w *WaveletMatrixSum) Ceil(start, end, value, xor int) int {
	less, _ := w.CountPrefix(start, end, value, xor)
	if less == end-start {
		return INF
	}
	res, _ := w.Kth(start, end, less, xor)
	return res
}

func (wm *WaveletMatrixSum) binarySearch(f func(E) bool, ok, ng int) int {
	for abs(ok-ng) > 1 {
		x := (ok + ng) >> 1
		if f(x) {
			ok = x
		} else {
			ng = x
		}
	}
	return ok
}

func (wm *WaveletMatrixSum) get(d, l, r int) E {
	return wm.op(wm.inv(wm.preSum[d][l]), wm.preSum[d][r])
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

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
}