题目描述
在一个城市的一条窄到只有长度没有宽度的道路上有 N只婆罗门的斗鸡在不同斗鸡点的上, 对一个城市定义该城市的斗鸡爱好度为:
这n × (n − 1)个距离的总和。
每只婆罗门的斗鸡都计算到其它各只婆罗门的斗鸡的距离。 但是婆罗门数学太差,所以他要让你帮他求城市斗鸡爱好度。
输入输出格式
输入格式:
第一行一个整数 N。
接下来一行每行一个整数 Ji,代表第 i只婆罗门的斗鸡的位置。
输出格式:
输出一个数代表该城市的斗鸡爱好度。
输入输出样例
输入样例#1: 复制
5 1 2 3 4 5
输出样例#1: 复制
40
说明
对于 60%的数据:
N ≤ 1e4.
对于 100%的数据:
N ≤ 1e5, Ji ≤ 1e6 .
主要思路: 暴力 + 线段树优化
我绝对不会告诉你我考试时我电脑炸了
然而,我用快读就会被卡到80分,用scanf有100分。
emmm...
这是个令人深思的问题啊。
好的回到正题。
怎么用线段树?
我们如果求一个点到其他所有点的距离好像不太好做的说,起码O(n^2),
但我们把这些数放在数轴上,可以一次性求出一个点到之前的所有点的距离吗?
当然可以!!!
我们可以想,一个点到另一个点的距离不是这个点的坐标减去另一个点的坐标吗?在这个点a[i]之前有i - 1个坐标,实际上是一个数列求和的问题。
a[i] - a[1] a[i] - a[2] a[i] - a[3] ... a[i] - a[i - 1] || || \--/ \/ a[i] * (i - 1) - (a[1] + a[2] + a[3] + ... + a[i - 1])
我们可以这么求。
如果不考虑爆long long的话,我们可以用一个区间求和的线段树求a[1] ~ a[i - 1],在用a[i] * (i - 1)减去这个数。
但是会爆int,还会爆long long。怎么办?
我们继续考虑线段树上的操作。
如果我们每次存进去一个点的负值,并求前面点的负值和,我们如果直接在线段树上把a[i]加进去,正好是每个点一个a[i] - a[j](思路似乎又转回来了)
这样每次把一段区间区间加a[i],求和加入答案,然后再区间减去a[i]。
这样求出的是一个点到之前点的距离和,只要答案*2就可以变成所有的距离和了
这样相当于只用了一个数据结构,不动脑子,就可以暴力解水题了
记得,目前此题的这组数据有毒,n^2可以过,但是你加了像我这样写的快读,你就可能凉凉
Code:
-------------------------------(线段树板子泥萌确定要看???)------------------------------
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define go(i, j, n, k) for (int i = j; i <= n; i += k) #define fo(i, j, n, k) for (int i = j; i >= n; i -= k) #define rep(i, x) for (int i = h[x]; i; i = e[i].nxt) #define mn 1000100 #define inf 2147483647 #define ll long long #define ld long double #define fi first #define se second #define root 1, n, 1 #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define bson l, r, rt //#define LOCAL #define mod #define Debug(...) fprintf(stderr, __VA_ARGS__) inline int read(){ // 凉凉之快读 int f = 1, x = 0;char ch = getchar(); while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } //This is AC head above... struct tree{ ll x; }; struct SegmentTree{ // 线段树不解释,,,就是板子 tree z[mn << 2]; ll col[mn << 2]; inline void update(int rt){ z[rt].x = z[rt << 1].x + z[rt << 1 | 1].x;} inline tree operation(tree a,tree b){ return (tree){a.x + b.x}; } inline void color(int l,int r,int rt,ll v){ z[rt].x += (r - l + 1) * v; col[rt] += v; } inline void push_col(int l,int r,int rt){ if(col[rt]){ int m = (l + r) >> 1; color(lson, col[rt]);color(rson, col[rt]); col[rt] = 0; } } inline void build(int l,int r,int rt){ if(l==r){z[rt].x = 0;return;} int m = (l + r) >> 1;build(lson);build(rson); update(rt); } inline void modify(int l,int r,int rt,int nowl,int nowr,ll v){ if(nowl<=l && r<=nowr){color(bson, v); return;} int m = (l + r) >> 1; push_col(bson); if(nowl<=m) modify(lson, nowl, nowr, v); if(m<nowr) modify(rson, nowl, nowr, v); update(rt); } inline tree query(int l,int r,int rt,int nowl,int nowr){ if(nowl<=l && r<=nowr) return z[rt]; int m = (l + r) >> 1; push_col(bson); if(nowl<=m){ if(m<nowr) return operation(query(lson, nowl, nowr), query(rson, nowl, nowr)); else return query(lson, nowl, nowr); }else return query(rson, nowl, nowr); } } tr; ll n; ll a[mn], b[mn], ans; int main(){ n = read(); go(i, 1, n, 1) scanf("%d",&a[i]), b[i] = a[i]; tr.build(root); sort(b + 1, b + n + 1); // 在数轴上记得排下序 tr.modify(root, 1, 1, -b[1]); go(i,2,n,1){ tr.modify(root, 1, i - 1, b[i]); ans += tr.query(root, 1, i - 1).x; tr.modify(root, 1, i - 1, -b[i]); tr.modify(root, i, i, -b[i]); } cout << (ans << 1); // 记得要×2 #ifdef LOCAL Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC); #endif return 0; }