思考题for everyone

# Dynamic DP

You are given:

integer arrays

integer arrays

For each

Known:

Now given

For each query given x and y, if we violently set

Example:

when

then DP=

if we set dp[1..2] to 0 then

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:

# 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)