波動(dòng)值之和

金牌導(dǎo)航 Splay-1

題目大意

給出一個(gè)數(shù)列，求${\sum }_{i=1}^{n}mi{n}_{j=1}^{i?1}|a_i?a_j|$

輸入樣例

6 5 1 2 5 4 6

輸出樣例

12

樣例解釋

$5+|1?5|+|2?1|+|5?5|+|4?5|+|6?5|=5+4+1+0+1+1=12$

數(shù)據(jù)范圍

$1?n?32767,|a_i|?10^6$

解題思路

用Splay存起來(lái)，然后每次找到最接近當(dāng)前數(shù)的數(shù)（把當(dāng)前數(shù)旋轉(zhuǎn)為根節(jié)點(diǎn)，然后在左子樹(shù)找最大，在右子樹(shù)找最小）

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 40000 using namespace std; int n, x, w, rt, ans, s[N], ls[N], rs[N], fa[N]; int ss(int x) {return x == ls[fa[x]]; } void up(int x) {int y = fa[x], z = fa[y], g = ss(x)? rs[x]: ls[x];if (z) ss(y)? ls[z] = x: rs[z] = x;if (ss(x)) rs[x] = y, ls[y] = g;else ls[x] = y, rs[y] = g;fa[x] = z;fa[y] = x;if (g) fa[g] = y; } void Splay(int x, int y)//旋轉(zhuǎn) {while(fa[x] != y){if (fa[fa[x]] != y)ss(x) == ss(fa[x])? up(fa[x]): up(x);up(x);}if (!y) rt = x; } void add(int v)//加點(diǎn) {int x = rt, y = 0;while(x){y = x;if (v < s[x]) x = ls[x];else x = rs[x];}s[++w] = v;fa[w] = y;if (v < s[y]) ls[y] = w;else rs[y] = w;Splay(w, 0); } int ask()//查詢 {int x = ls[rt], y = rs[rt], xx, yy;//分別查詢左右子樹(shù)if (x) while(rs[x]) x = rs[x];//左子樹(shù)最大的if (y) while(ls[y]) y = ls[y];xx = s[rt] - s[x];yy = s[y] - s[rt];if (!x) return yy;if (!y) return xx;return min(xx, yy); } int main() {scanf("%d", &n);scanf("%d", &ans);s[++w] = ans;rt = 1; while(--n){scanf("%d", &x);add(x);ans += ask();}printf("%d", ans);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【Splay】波动值之和（金牌导航 Splay-1）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。