#668878 (PyPy3) No.1099 Range Square Sum

• 問題: No.1099 Range Square Sum
• ユーザー: shotoyoo
• 提出日時: 2021-06-21 23:43:50
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,912 ms / 2,000 ms
• コード長: 4,738 bytes
• コンパイル時間: 230 ms
• コンパイル使用メモリ: 82,688 KB
• 実行使用メモリ: 286,784 KB
• 最終ジャッジ日時: 2024-06-22 22:57:46
• 合計ジャッジ時間: 18,495 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))
### 遅延評価セグメント木(はやい非DFS)
class LSG:
    def __init__(self,n, a=None):
        self._n = n
        self._ninf = ninf
        self._op = op
        self._mapping = mapping
        self._composition = composition
        self._f0 = f0
        x = 0
        while (1 << x) < self._n:
            x += 1
        self._log = x
        self._size = 1 << self._log
        self._d = [self._ninf] * (2 * self._size)
        self._lz = [self._f0] * self._size
        if a is not None:
            for i in range(self._n):
                self._d[self._size + i] = a[i]
            for i in range(self._size - 1, 0, -1):
                self._update(i)
    def check(self):
        return [self.query_point(p) for p in range(self._n)]
    def update_point(self, p, x):
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)
    def query_point(self, p):
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]
    def query(self, left, right):
        if left == right:
            return self._ninf
        left += self._size
        right += self._size
        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push(right >> i)
        sml = self._ninf
        smr = self._ninf
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1
        return self._op(sml, smr)
    def query_all(self):
        return self._d[1]
    def update(self, left, right, f):
        if right is None:
            p = left
            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            if left == right:
                return
            left += self._size
            right += self._size
            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)
            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2
            for i in range(1, self._log + 1):
                if ((left >> i) << i) != left:
                    self._update(left >> i)
                if ((right >> i) << i) != right:
                    self._update((right - 1) >> i)
    def _update(self, k):
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
    def _all_apply(self, k, f) -> None:
        self._d[k] = self._mapping(f, self._d[k])
        if k < self._size:
            self._lz[k] = self._composition(f, self._lz[k])
    def _push(self, k):
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._f0
    def loc(self, l, r):
        return self._lz[self._size+l : self._size+r]
    
ninf = (0,0,0) # (和, 積和, 個数)
f0 = 0
def op(x,y):
    return (x[0]+y[0], x[1]+y[1]+x[0]*y[0], x[2]+y[2])
def mapping(f,x):
    return (
        x[0] + f*x[2],
        x[1] + x[0]*f*(x[2]-1) + f*f*x[2]*(x[2]-1)//2,
        x[2]
    )
# composition: あとからきたクエリがf1に入る
def composition(f1,f2):
    return f1+f2
n = int(input())
a = list(map(int, input().split()))
sg = LSG(n, [(v,0,1) for v in a])
q = int(input())
ans = []
for i in range(q):
    s = input().split()
    if s[0]=="1":
        _,l,r,x = map(int, s)
        l -= 1
        r -= 1
        sg.update(l,r+1,x)
    else:
        _,l,r = map(int, s)
        l -= 1
        r -= 1
        val = sg.query(l,r+1)
#         print(val)
        ans.append(val[0]**2-2*val[1])
write("\n".join(map(str, ans)))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX