Also Try Minecraft
CF1709BAlso Try Minecraft题解
还是原题：搁这呢
题目大意：
给定长度为n的序列，a[i]代表第i位置的高度，从某个更高的位置走到更矮的位置会获得两者差值的下降伤害。m次询问，询问从s走到t的下降伤害。（s可能大于t）
大致思路
前缀和:sum[i]维护从1走到i的伤害. sum1[i]维护从n走i的值。s<t就是往前走，用sum[t]-sum[s]，否则为sum1[t]-sum1[s]
贴个AC CODE：
int n,m;
long long a[N],sum1[N],sum[N];
void solve() {
// 竞赛程序
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
if(i > 1) sum1[i] = sum1[i - 1] + max((long long)0, a[i - 1] - a[i]);
}
for(int i = n - 1; i >= 1; --i)
sum[i] = sum[i+1] + max((long long)0, a[i + 1] - a[i]);
while(m--) {
int s, t;
cin >> s >> t;
if(s == t)
cout << "0";
else if(s > t)
cout << sum[t] - sum[s] << endl;
else
cout << sum1[t] - sum1[s] << endl;
}
}
