Orange Boy Can You Solve It Out? Ep.1
You are given:
integer arrays A and dp of length N.
integer arrays l and r of length N.
For each 2\leq i\leq N,1\leq l_i\leq r_i\leq i-1
dp_i=min(dp[l_i,r_i])+A_i for 2\leq i\leq N.
Now given q queries:
For each query given x and y, if we violently set dp[0,x]=y, print dp_N
if we set dp[1..2] to 0 then DP=[0,0,min(0,0)+2=2,min(0,2)+6=6]=[0,0,2,6] thus 6 is printed
Test1 - n=100 q=100
Test2 - n=1e5 q=1e5,the numbers in A is all 0 except A_1
Test3 - n=1e5 q=1e5,y=0
Test4 - n=1e5 q=1e5
Orange Boy Come And ACCEPTED
P.S: IDK how to do 😛
Note: array[i,j] means from array_i to array_j
Solution By MonkeyKing
let's create another array B.
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.
来源：Hell Hole Studios Blog
I've got a idea(99% wrong), but since I haven't finished my homework, so ...
I've got an idea(99% wrong), but since I haven't finished my homework, so... 🙂