Description:
- \(n\) 个数：\(x_1,···,x_n\)，从左向右扫，当 \(s=x_i\) 时，可以将这 \(n\) 个数分为若干个闭区间 \([s,x_1],[s,x_2],···,[s,x_n]\)（当然如果\(x_i<s\)，则区间形如 \([x_i,s]\)）
- 对于每一个 \(s\in (x_1,···,x_n)，\)有一个整数 \(p\)，记 \(f_p\) 为其在划分出的所有区间中被包含的次数，请计算出 \(\sum_{p=1}^{10^9} f_p\)
- 例如, 对于 \([1,2,5,7,1]\)，当 \(s=x_3=5\) 时，划分的区间为 \([1,5]，[2,5],[5,5],[5,7],[1,5]\)，其中 \(p=1\) 时在2个区间中出现，即 \(f_1=2\)，同理，\(f_2=3\)，\(f_3=3\)，\(f_4=3\)，\(f_5=5\)，\(f_6=1\)，\(f_7=1\)，\(f_8=0\)，\(f_9=0\)，\(···\)，\(f_{10^9}=0\).
所以 \(\sum_{p=1}^{10^9} f_p=2+3+3+3+5+1+1=18\)
Constraints:
- \(1\leq n \leq 2·10^5\)
- \(1 \leq x_i \leq 10^9\)
Analysis:
- 对于一个固定的 \(s=x_i\)，考虑这 \(n\) 个区间中所含初始元素的贡献，不难发现：\(x_i\) 的贡献总和恰好等于 \(n\) 个区间的长度总和，即该定态下可以\(O(n)\)
- 那如何更高效呢？\(\Rightarrow\) 排个序看看（升序），有序之后就可以利用数学知识对区间考虑。
- 当处理到 \(s=x_i\) 时，对于所有的 \(j\leq i\)，划分出区间 \([x_j,s]\)，对于所有的 \(j>i\)，划分出区间 \([s,x_j]\)，求所有区间长度总和即可（需要前缀和维护）。
Solution:
const int maxn = 2e5+5;
//或许用pair写会更简洁，但鄙人偏爱结构体..
struct Node {
ll a; int id;
Node(){}
Node(ll _a, int _id) : a(_a), id(_id){}
};
bool cmp(Node x, Node y) {
if(x.a == y.a) return x.id < y.id;
return x.a < y.a;
}
ll pre[maxn]; // 前缀和
void solve() {
int n; cin >> n;
for(int i=0;i<=n;i++) pre[i] = 0;
vector<Node> v;
for(int i=1;i<=n;i++) {
ll x; cin >> x;
v.push_back(Node(x,i));
}
sort(v.begin(),v.end(),cmp);
for(int i=1;i<=n;i++) pre[i] = pre[i-1] + v[i-1].a;
// 注意下标细节
vector<ll> ans(n+1);
for(int i=1;i<=n;i++) {
ll s = v[i-1].a;
ans[v[i-1].id] = (s+1)*i+(n-i)*(1-s)+pre[n]-2*pre[i];
}
// 闲来无事：基于条件控制输出（避免行末空格）的简洁写法（详解在文末）
for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n];
}