#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const ll INF=1e18;
template<typename U, typename V>
ostream &operator<<(ostream &os, const pair<U, V> &p){
return os<<"("<<p.fst<<", "<<p.snd<<")";
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &s){
os<<"{";
bool flag=false;
for(const T &x:s){
if(flag) cout<<", ";
flag=true;
os<<x;
}
return os<<"}";
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
os<<"[";
bool flag=false;
for(const T &x:v){
if(flag) cout<<", ";
flag=true;
os<<x;
}
return os<<"]";
}
ll d;
struct Node{
vll vals;
vll mini;
vll suff;
ll cost=0LL;
Node(){}
Node(vll v){
if(v.empty()) return;
vals=v;
int n=sz(v);
mini.resize(n),suff.resize(n);
mini[n-1]=suff[n-1]=vals[n-1];
dforn(i,n-1){
mini[i]=min(mini[i+1],vals[i]);
cost+=vals[i]-mini[i];
suff[i]=suff[i+1]+mini[i];
}
}
};
const int SZ=1<<19;
Node st[2*SZ];
ll query(int l, int r){
vi left,right;
for(l+=SZ,r+=SZ;l<r;l/=2,r/=2){
if(l&1) left.pb(l++);
if(r&1) right.pb(--r);
}
vi nodes=left;
dforn(i,sz(right)) nodes.pb(right[i]);
ll mini=INF;
ll cost=0;
reverse(all(nodes));
for(int u:nodes){
int lo=-1,hi=sz(st[u].mini);
while(hi-lo>1){
int mid=(lo+hi)/2;
if(st[u].mini[mid]>=mini) hi=mid;
else lo=mid;
}
cost+=st[u].cost;
if(hi!=sz(st[u].mini))cost+=st[u].suff[hi]-mini*(sz(st[u].mini)-hi);
mini=min(mini,st[u].mini.front());
}
return cost;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n>>d;
forn(i,n){
ll c; cin>>c;
st[i+SZ]=vll{c};
}
dforsn(i,1,SZ){
vll v=st[2*i].vals;
forn(j,sz(st[2*i+1].vals)) v.pb(st[2*i+1].vals[j]);
st[i]=v;
}
int q;
cin>>q;
forn(_,q){
int l,r;
cin>>l>>r;
--l;
cout<<query(l,r)<<'\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |