#851056 (Go) No.1891 Static Xor Range Composite Query

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
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
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX