結果

問題 No.1099 Range Square Sum
ユーザー 👑 obakyan
提出日時 2021-07-26 23:56:10
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 1,381 ms / 2,000 ms
コード長 4,118 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 7,072 KB
実行使用メモリ 52,192 KB
最終ジャッジ日時 2024-07-22 14:39:42
合計ジャッジ時間 13,808 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

local mfl, mce = math.floor, math.ceil
local bls, brs = bit.lshift, bit.rshift
local function mma(a, b) return a < b and b or a end
local p2 = {1}
for i = 2, 28 do
p2[i] = p2[i - 1] * 2
end
local lin = {{0}}
local sq = {{0}}
local lazy = {{0}}
local left_stage = {}
local sz_stage = {}
local n = io.read("*n", "*l")
local stagenum = 0
local function updateAll()
for i = stagenum - 1, 1, -1 do
local cnt = p2[i]
if stagenum - i + 1 < 9 then
for j = 1, cnt do
lin[i][j] = lin[i + 1][j * 2 - 1] + lin[i + 1][j * 2]
sq[i][j] = sq[i + 1][j * 2 - 1] + sq[i + 1][j * 2]
lazy[i][j] = 0
end
else
for j = 1, cnt do
lin[i][j] = lin[i + 1][j * 2 - 1] + lin[i + 1][j * 2]
sq[i][j] = 1LL * sq[i + 1][j * 2 - 1] + sq[i + 1][j * 2]
lazy[i][j] = 0
end
end
end
end
local function create()
local mul = 1
stagenum = 1
while mul < n do
mul, stagenum = mul * 2, stagenum + 1
lin[stagenum] = {}
sq[stagenum] = {}
lazy[stagenum] = {}
end
for i = 1, n do
local sp, sz = 1, p2[stagenum]
while(i - 1) % sz ~= 0 do
sp, sz = sp + 1, brs(sz, 1)
end
left_stage[i] = sp
end
sz_stage = {}
local tmp, sp = 1, stagenum
for i = 1, n do
if tmp * 2 == i then tmp, sp = tmp * 2, sp - 1 end
sz_stage[i] = sp
end
local z = io.read()
local i = 0
for a in z:gmatch("%-?%d+") do
i = i + 1
a = tonumber(a)
lin[stagenum][i] = a
sq[stagenum][i] = a * a
lazy[stagenum][i] = 0
end
for i = n + 1, mul do
lin[stagenum][i] = 0
sq[stagenum][i] = 0
lazy[stagenum][i] = 0
end
updateAll()
end
local function resolveRange(stagepos, idx, value, shallow)
local linadd = p2[stagenum - stagepos + 1] * value
if stagenum - stagepos + 1 < 9 then
sq[stagepos][idx] = sq[stagepos][idx] + (linadd + 2 * lin[stagepos][idx]) * value
else
sq[stagepos][idx] = sq[stagepos][idx] + (linadd + 2LL * lin[stagepos][idx]) * value
end
lin[stagepos][idx] = lin[stagepos][idx] + linadd
if shallow then return end
for i = stagepos - 1, 1, -1 do
local dst = brs(idx + 1, 1)
local rem = dst * 4 - 1 - idx
lin[i][dst] = lin[i + 1][idx] + lin[i + 1][rem]
sq[i][dst] = sq[i + 1][idx] + sq[i + 1][rem]
idx = dst
end
end
local function resolve(right)
local offset = 0
for i = 1, stagenum - 1 do
local p = offset + p2[stagenum - i + 1]
if p < right then
offset = p
p = p + p2[stagenum - i + 1]
end
if right < p then
local curidx = brs(p, stagenum - i)
local lzval = lazy[i][curidx]
if lzval ~= 0 then
local sz = p2[stagenum - i]
resolveRange(i + 1, curidx * 2 - 1, lzval, true)
resolveRange(i + 1, curidx * 2, lzval, true)
lazy[i + 1][curidx * 2 - 1] = lazy[i + 1][curidx * 2 - 1] + lzval
lazy[i + 1][curidx * 2] = lazy[i + 1][curidx * 2] + lzval
lazy[i][curidx] = 0
end
else--p==right
break
end
end
end
local function getRange(left, right)
if 1 < left then resolve(left - 1) end
resolve(right)
local ret = 0LL
while left <= right do
local stage = mma(left_stage[left], sz_stage[right - left + 1])
ret = ret + sq[stage][1 + brs(left - 1, stagenum - stage)]
left = left + p2[stagenum - stage + 1]
end
return ret
end
local function setRange(left, right, value)
if 1 < left then resolve(left - 1) end
resolve(right)
while left <= right do
local stage = mma(left_stage[left], sz_stage[right - left + 1])
local idx = 1 + brs(left - 1, stagenum - stage)
resolveRange(stage, idx, value)
lazy[stage][idx] = lazy[stage][idx] + value
left = left + p2[stagenum - stage + 1]
end
end
create()
local retall = {}
local q = io.read("*n")
for iq = 1, q do
local tp = io.read("*n")
if tp == 1 then
local l, r, x = io.read("*n", "*n", "*n")
setRange(l, r, x)
else
local l, r = io.read("*n", "*n")
local val = getRange(l, r)
val = tostring(val):gsub("LL", "")
-- print(val)
table.insert(retall, val)
end
end
print(table.concat(retall, "\n"))
-- print(os.clock())
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0