結果
問題 | No.1099 Range Square Sum |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
local mfl, mce = math.floor, math.ceillocal bls, brs = bit.lshift, bit.rshiftlocal function mma(a, b) return a < b and b or a endlocal p2 = {1}for i = 2, 28 dop2[i] = p2[i - 1] * 2endlocal lin = {{0}}local sq = {{0}}local lazy = {{0}}local left_stage = {}local sz_stage = {}local n = io.read("*n", "*l")local stagenum = 0local function updateAll()for i = stagenum - 1, 1, -1 dolocal cnt = p2[i]if stagenum - i + 1 < 9 thenfor j = 1, cnt dolin[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] = 0endelsefor j = 1, cnt dolin[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] = 0endendendendlocal function create()local mul = 1stagenum = 1while mul < n domul, stagenum = mul * 2, stagenum + 1lin[stagenum] = {}sq[stagenum] = {}lazy[stagenum] = {}endfor i = 1, n dolocal sp, sz = 1, p2[stagenum]while(i - 1) % sz ~= 0 dosp, sz = sp + 1, brs(sz, 1)endleft_stage[i] = spendsz_stage = {}local tmp, sp = 1, stagenumfor i = 1, n doif tmp * 2 == i then tmp, sp = tmp * 2, sp - 1 endsz_stage[i] = spendlocal z = io.read()local i = 0for a in z:gmatch("%-?%d+") doi = i + 1a = tonumber(a)lin[stagenum][i] = asq[stagenum][i] = a * alazy[stagenum][i] = 0endfor i = n + 1, mul dolin[stagenum][i] = 0sq[stagenum][i] = 0lazy[stagenum][i] = 0endupdateAll()endlocal function resolveRange(stagepos, idx, value, shallow)local linadd = p2[stagenum - stagepos + 1] * valueif stagenum - stagepos + 1 < 9 thensq[stagepos][idx] = sq[stagepos][idx] + (linadd + 2 * lin[stagepos][idx]) * valueelsesq[stagepos][idx] = sq[stagepos][idx] + (linadd + 2LL * lin[stagepos][idx]) * valueendlin[stagepos][idx] = lin[stagepos][idx] + linaddif shallow then return endfor i = stagepos - 1, 1, -1 dolocal dst = brs(idx + 1, 1)local rem = dst * 4 - 1 - idxlin[i][dst] = lin[i + 1][idx] + lin[i + 1][rem]sq[i][dst] = sq[i + 1][idx] + sq[i + 1][rem]idx = dstendendlocal function resolve(right)local offset = 0for i = 1, stagenum - 1 dolocal p = offset + p2[stagenum - i + 1]if p < right thenoffset = pp = p + p2[stagenum - i + 1]endif right < p thenlocal curidx = brs(p, stagenum - i)local lzval = lazy[i][curidx]if lzval ~= 0 thenlocal 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] + lzvallazy[i + 1][curidx * 2] = lazy[i + 1][curidx * 2] + lzvallazy[i][curidx] = 0endelse--p==rightbreakendendendlocal function getRange(left, right)if 1 < left then resolve(left - 1) endresolve(right)local ret = 0LLwhile left <= right dolocal 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]endreturn retendlocal function setRange(left, right, value)if 1 < left then resolve(left - 1) endresolve(right)while left <= right dolocal 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] + valueleft = left + p2[stagenum - stage + 1]endendcreate()local retall = {}local q = io.read("*n")for iq = 1, q dolocal tp = io.read("*n")if tp == 1 thenlocal l, r, x = io.read("*n", "*n", "*n")setRange(l, r, x)elselocal l, r = io.read("*n", "*n")local val = getRange(l, r)val = tostring(val):gsub("LL", "")-- print(val)table.insert(retall, val)endendprint(table.concat(retall, "\n"))-- print(os.clock())