1857E.Power of Points

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]\)，求所有区间长度总和即可（需要前缀和维护）。

• 总复杂度：\(O(n\log n)\)

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]; 
}