https://namomo.top:8081/contest/2
C. 序列
题意：给定一个数列，每次将一个区间 [l,r] 中所有数-1，代价 (r−l+1)2，要求最终全变为0，问在用最少次数操作的前提下，最小代价与最大代价。
差分
考虑逆向操作，从全为 0 的数列，每次选一个区间+1，形成给定数列。
每次选一个区间全部加 1 ，可以差分完成，所以求出给定数列的差分数组，要求操作次数最少，所以差分数组中负数的位置一定是所选操作区间右端点+1，正数位置一定是所选操作区间的左端点，为 0 的位置一定不会作为差分时操作的位置。
所以差分数组相当于一个括号序列，在正数位置只能放左括号，负数只能放右括号。
设差分数组中正数位置为 a，负数位置为 b。
则总的代价 ∑(a[i]−b[i])2=∑(a[i]2+b[i]2)−2∑(a[i]∗b[i])。
前一个求和是常数，不用管，由排序不等式可知要使得后一个求和最小，必须要使得 a 和 b 逆序配对，即 a 递增 配 b 递减，要使得最大，必须要顺序配对。
所以要求总的代价最小，则要每个右括号匹配最前面的左括号，所以可以用队列存储左括号，每次遇到右括号就取队列最前面的。
而要总代价最大，则必须最后一个右括号匹配第一个左括号，倒数第 2 个右括号匹配正数第 2 个左括号，以此类推。又能发现这样匹配如果在已知括号序列必定合法的情况下，就相当于每个右括号匹配左边最靠近的左括号。所以可以用栈实现，每次右括号选栈顶的左括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 5e5 + 10;
int n;
ll a[N], b[N], mx, mn;
typedef pair<ll, ll>pii;
queue<pii>q;
stack<pii>st;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
for (int i = 1; i <= n + 1; i++)b[i] = a[i] - a[i - 1];
for (int i = 1; i <= n + 1; i++) {
if (b[i] > 0) {
q.push(pii(b[i], i));
st.push(pii(b[i], i));
}
else if (b[i] < 0) {
ll tmp = -b[i];
while (tmp > 0) {
ll cn = min(tmp,q.front().first), po = q.front().second;
if (q.front().first == cn)q.pop();
else q.front().first -= cn;
tmp -= cn;
mn = (mn + cn * (i - po) % mod*(i - po) % mod) % mod;
}
tmp = -b[i];
while (tmp > 0) {
ll cn = min(tmp, st.top().first), po = st.top().second;
if (st.top().first == cn)st.pop();
else st.top().first -= cn;
tmp -= cn;
mx = (mx + cn*(i - po) % mod*(i - po) % mod) % mod;
}
}
}
printf("%lld %lld\n", mn, mx);
return 0;
}
|
