P10148 [Ynoi1999] M47 Upgraded “Steel Arno”


Given an integer sequence $a_1,\dots,a_n$ of length $n$. You are also given a sequence of $m$ operations, numbered from $1$ to $m$. The operations include update operations and range sum operations. An update operation gives $l,r,v$ and sets $a_l,a_{l+1},\dots,a_r$ to $v$. A range sum operation gives $l,r$ and asks for $\sum\limits_{i=l}^r a_i$. There are $q$ queries. Each query gives $L,R$ and asks: after initializing the sequence $a$ to $0$, execute operations $L,L+1,\dots,R$ in order, and output the sum of the answers of all range sum operations during this process.

The first line contains three integers $n,m,q$. The next $m$ lines each describe one operation in the form $1,l,r,v$ or $2,l,r$. The next $q$ lines each contain two integers $L,R$, describing one query.

Output $q$ lines. Each line contains one integer, in order, representing the answer to each query.

Idea: Ynoi, Solution: nzhtl1477&ccz181078, Code: ccz181078, Data: ccz181078. Constraints: for all testdata, $1\le l\le r\le n$, $1\le v\le n$, $1\le L\le R\le m$, and $1\le n,m,q\le 5\times 10^5$. For $10\%$ of the testdata, $n,m,q\le 10^2$. For another $20\%$ of the testdata, $n,m,q\le 5\times 10^3$. For another $10\%$ of the testdata, every operation is a range sum operation. For another $20\%$ of the testdata, every query satisfies $L=1$. For another $20\%$ of the testdata, $n,m,q\le 2\times 10^5$. For the remaining testdata, there are no special constraints. Translated by ChatGPT 5