Codeforces 1114F — Please, another Queries on Array?

1package main2 3import (4	"bufio"5	. "fmt"6	"io"7)8 9const mod1114 int64 = 1e9 + 710 11type lazyST1114 []struct {12	l, r         int13	mul, mulTodo int6414	or, orTodo   int6415}16 17func (lazyST1114) pow(x int64, n int) int64 {18	res := int64(1)19	for ; n > 0; n >>= 1 {20		if n&1 == 1 {21			res = res * x % mod111422		}23		x = x * x % mod111424	}25	return res26}27 28func (t lazyST1114) _pushUp(o int) {29	lo, ro := t[o<<1], t[o<<1|1]30	t[o].mul = lo.mul * ro.mul % mod111431	t[o].or = lo.or | ro.or32}33 34func (t lazyST1114) _build(a []int, ors []int64, o, l, r int) {35	t[o].l, t[o].r, t[o].mulTodo = l, r, 136	if l == r {37		t[o].mul = int64(a[l-1])38		t[o].or = ors[l-1]39		return40	}41	m := (l + r) >> 142	t._build(a, ors, o<<1, l, m)43	t._build(a, ors, o<<1|1, m+1, r)44	t._pushUp(o)45}46 47func (t lazyST1114) _spread(o int) {48	lo, ro := &t[o<<1], &t[o<<1|1]49	if mul := t[o].mulTodo; mul != 1 {50		lo.mul = lo.mul * t.pow(mul, lo.r-lo.l+1) % mod111451		ro.mul = ro.mul * t.pow(mul, ro.r-ro.l+1) % mod111452		lo.mulTodo = lo.mulTodo * mul % mod111453		ro.mulTodo = ro.mulTodo * mul % mod111454		t[o].mulTodo = 155	}56	if or := t[o].orTodo; or != 0 {57		lo.or |= or58		ro.or |= or59		lo.orTodo |= or60		ro.orTodo |= or61		t[o].orTodo = 062	}63}64 65func (t lazyST1114) _update(o, l, r, mul int, orVal int64) {66	ol, or := t[o].l, t[o].r67	if l <= ol && or <= r {68		t[o].mul = t[o].mul * t.pow(int64(mul), or-ol+1) % mod111469		t[o].mulTodo = t[o].mulTodo * int64(mul) % mod111470		t[o].or |= orVal71		t[o].orTodo |= orVal72		return73	}74	t._spread(o)75	m := (ol + or) >> 176	if l <= m {77		t._update(o<<1, l, r, mul, orVal)78	}79	if m < r {80		t._update(o<<1|1, l, r, mul, orVal)81	}82	t._pushUp(o)83}84 85func (t lazyST1114) _query(o, l, r int) (mul, or int64) {86	if l <= t[o].l && t[o].r <= r {87		return t[o].mul, t[o].or88	}89	t._spread(o)90	mul = 191	m := (t[o].l + t[o].r) >> 192	if l <= m {93		mul, or = t._query(o<<1, l, r)94	}95	if m < r {96		a, b := t._query(o<<1|1, l, r)97		mul = mul * a % mod111498		or |= b99	}100	return101}102 103func (t lazyST1114) init(a []int, ors []int64)      { t._build(a, ors, 1, 1, len(a)) }104func (t lazyST1114) update(l, r, mul int, or int64) { t._update(1, l, r, mul, or) }105func (t lazyST1114) query(l, r int) (int64, int64)  { return t._query(1, l, r) }106 107// github.com/EndlessCheng/codeforces-go108func CF1114F(_r io.Reader, _w io.Writer) {109	in := bufio.NewReader(_r)110	out := bufio.NewWriter(_w)111	defer out.Flush()112	pow := func(x, n int64) int64 {113		res := int64(1)114		for ; n > 0; n >>= 1 {115			if n&1 == 1 {116				res = res * x % mod1114117			}118			x = x * x % mod1114119		}120		return res121	}122	div := func(p int64) int64 { return (p - 1) * pow(p, mod1114-2) % mod1114 }123	const mx = 300124	factors := [mx + 1]int64{}125	p1p := []int64{}126	for i := 2; i <= mx; i++ {127		if factors[i] == 0 {128			for j := i; j <= mx; j += i {129				factors[j] |= 1 << len(p1p)130			}131			p1p = append(p1p, div(int64(i)))132		}133	}134 135	var n, q, l, r, x int136	var s []byte137	Fscan(in, &n, &q)138	a := make([]int, n)139	ors := make([]int64, n)140	for i := range a {141		Fscan(in, &a[i])142		ors[i] = factors[a[i]]143	}144 145	t := make(lazyST1114, 4*n)146	t.init(a, ors)147	for ; q > 0; q-- {148		Fscan(in, &s, &l, &r)149		if s[0] == 'M' {150			Fscan(in, &x)151			t.update(l, r, x, factors[x])152		} else {153			ans, ps := t.query(l, r)154			for i, v := range p1p {155				if ps>>i&1 == 1 {156					ans = ans * v % mod1114157				}158			}159			Fprintln(out, ans)160		}161	}162}163 164//func main() { CF1114F(os.Stdin, os.Stdout) }