In this HackerEarth Dynamic DP problem solution You are given the following:
1. An array A of length n that contains integers
2. DP of length n
3. Arrays L and R of length n that contain integers
You are also provided with the following attributes:
1. If i = 1, then Li = Ri = 1
2. If 2 <= i <= n, then 1 <= Li <= Ri < i
3. DP1 = A1
4. DPi = min(DP[Li,Ri]) + Ai
The element A[x,y] is defined to be all the elements that are available in [a,b] of array A. For example, DP[2,3] indicates DP2 and DP3.

You are also provided with  queries that state the following:
1. You are given two integers x and y.
2. You are required to replace DP[1,x] to y and then update the remaining part of DP. Now, print DPn.

## HackerEarth Dynamic DP problem solution.

```#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string.h>
#include <math.h>
#include <stdio.h>

using namespace std;
#define ll long long
#define pii pair<int,int>

bool debug=true;

set<pii> st;
bool stand=true;
ll n,m,q;
ll ans;
int main(int argc,char* argv[]){
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=0;i<q;i++){
int mode;
scanf("%d",&mode);
if(mode==1){
int x,y;
scanf("%d%d",&x,&y);
set<pii>::iterator pos=st.find(make_pair(x,y));
if(pos!=st.end()){
st.erase(pos);
if(stand){
ans--;
}else{
ans++;
}
}else{
st.insert(make_pair(x,y));
if(stand){
ans++;
}else{
ans--;
}
}
}else{
ans=n*m-ans;
stand=!stand;
}
}

cout<<ans;
return 0;
}```

### Second solution

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 14;
const ll inf = 1e18;

int n, a[maxn], l[maxn], r[maxn];
ll b[maxn];
multiset<ll> s;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
cin >> l[i] >> r[i], l[i]--, r[i]--;
for(int i = n - 1; i >= 0; i--){
s.insert(x);
if(i != n - 1)
b[i] = s.size() ? *s.begin() : inf;
if(i){
rem[ l[i] ].push_back(b[i] + a[i]);
}
for(auto x : rem[i])
s.erase(s.find(x));
}
for(int i = 1; i < n; i++)
b[i] = min(b[i - 1], b[i]);
int q;
cin >> q;
while(q--){
int x, y;
cin >> x >> y;
cout << b[x - 1] + y << '\n';
}
}```