Hi everyone, I'm trying to learn a technique called the slope trick. I have read through several blogs on slope trick e.g https://codeforces.net/blog/entry/77298 and https://codeforces.net/blog/entry/47821. I went on to look at the problem "Sonya and Problem Wihtout A level". However I still couldn't understand how the slope trick work, I know that 2 slop-trickable function can be merged, but I still dunno what is the purpose of knowing that it can be merged and which point are we finding in the graph of the function.
cin>>n;
rep(x,1,n+1) cin>>arr[x];
rep(x,1,n+1) arr[x]-=x;
multiset<int,greater<int> > B={-(int)1e3};
int ans=0;
rep(x,1,n+1){
if (*B.begin()<arr[x]){
B.insert(arr[x]);
}
else{
B.insert(arr[x]);
B.insert(arr[x]);
ans+=*B.begin()-arr[x];
B.erase(B.begin());
}
}
I have a few questions in mind and wanted to ask regarding the above code. 1) what does the multiset store? 2) why does it have to initialize with a large negative value first 3) why do we insert arr[x] twice in the else statement 4) why do we have two cases either <arr[x] or >arr[x]
Really appreciate if you can answer some of my doubts thanks