思考题for everyone

Dynamic DP

You are given:
integer arrays and of length .
integer arrays and of length .
For each
Known:

for .

Now given queries:
For each query given x and y, if we violently set , print

Example:
when

then DP=
if we set dp[1..2] to 0 then thus 6 is printed

Constriants:
Test1 - n=100 q=100
Test2 - n=1e5 q=1e5,the numbers in A is all 0 except
Test3 - n=1e5 q=1e5,y=0
Test4 - n=1e5 q=1e5

Orange Boy Come And ACCEPTED

P.S: IDK how to do :P

Note: means from to

Solution By MonkeyKing

let's create another array B.
B[N]=0
for i from N to 1, we update B[L[i],R[i]] with B[i]+A[i]

Then for each query, print min(B[1,x])+y

We need a Segment Tree to proceed all of them.

Complexity:O(nlogn)