Solved!
Difficulty: Div2E

思考题for everyone

Dynamic DP

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
Known:
dp_1=A_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
Example:
when A=[1,9,2,6]
lr=[[1,1],[1,1],[1,2],[2,3]]
then DP=[1,1+9=10,min(1,10)+2=3,min(10,3)+6=9]=[1,10,3,9]
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
Constriants:
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.
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)