結果

問題 No.1891 Static Xor Range Composite Query
ユーザー 草苺奶昔
提出日時 2023-03-18 19:59:52
言語 Go
(1.23.4)
結果
AC  
実行時間 1,014 ms / 5,000 ms
コード長 2,269 bytes
コンパイル時間 12,986 ms
コンパイル使用メモリ 234,788 KB
実行使用メモリ 95,832 KB
最終ジャッジ日時 2024-09-18 13:29:13
合計ジャッジ時間 27,531 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	// https://yukicoder.me/problems/no/1891
	// 给定一个长为2的幂次的数组
	// 区间仿射变换,区间查询时每个下标异或上给定的数
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, q int
	fmt.Fscan(in, &n, &q)
	leaves := make([]S, n)
	for i := range leaves {
		fmt.Fscan(in, &leaves[i].mul, &leaves[i].add)
	}

	// RangeAffineRangeComposite
	seg := NewDisjointSparseTableXor(leaves)

	for i := 0; i < q; i++ {
		var start, end, indexXor, x int
		fmt.Fscan(in, &start, &end, &indexXor, &x)
		res := seg.Query(start, end, indexXor)
		fmt.Fprintln(out, (res.mul*x+res.add)%MOD)
	}
}

const MOD int = 998244353

type S = struct{ mul, add int }

func (*DisjointSparseTableXor) e() S { return S{1, 0} }
func (*DisjointSparseTableXor) op(a, b S) S {
	return S{a.mul * b.mul % MOD, (a.add*b.mul + b.add) % MOD}
}

type DisjointSparseTableXor struct {
	log  int
	data [][]S
}

// DisjointSparseTableXor 支持半群的区间静态查询.
//  op:只需要满足结合律 op(op(a,b),c) = op(a,op(b,c)).
//  区间查询时下标可以异或上 indexXor.
//  !nums 的长度必须要是2的幂.
func NewDisjointSparseTableXor(nums []S) *DisjointSparseTableXor {
	res := &DisjointSparseTableXor{}
	n := len(nums)
	log := 0
	for 1<<log < n {
		log++
	}
	if 1<<log != n {
		panic("len(nums) must be power of 2")
	}
	data := make([][]S, log+1)
	data[0] = make([]S, 1<<log)
	copy(data[0], nums)
	for k := 0; k < log; k++ {
		data[k+1] = make([]S, 1<<log)
		for i := 0; i < 1<<log; i++ {
			data[k+1][i] = res.op(data[k][i], data[k][i^(1<<k)])
		}
	}

	res.log = log
	res.data = data
	return res
}

// Calculate prod_{l<=i<r} A[x xor i], in O(log N) time.
func (st *DisjointSparseTableXor) Query(start, end, indexXor int) S {
	xl, xr := st.e(), st.e()
	for k := 0; k <= st.log; k++ {
		if start >= end {
			break
		}
		if start&(1<<k) != 0 {
			xl = st.op(xl, st.data[k][start^indexXor])
			start += 1 << k
		}
		if end&(1<<k) != 0 {
			end -= 1 << k
			xr = st.op(st.data[k][end^indexXor], xr)
		}
	}
	return st.op(xl, xr)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
0