BZOJ 1588
题意：求$\sum_{i=1}^n min_{1 \leq j \leq i}(|a_i-a_j|)$
BZOJ 1208
题意：找比某数差别最小的数。
第一个我一开始想写桶然后每次循环 $i$ 桶上下找最近有值，但是绝对被卡。
然后发现这个中间的空间都浪费了，其实绝对值差最小(两数差别最小)就是找前驱后继，用 set 维护即可。
这题也是平衡树题，由于查询的东西有限，写 set
记得 1208 要模
链表离线做法：
将原数组排序，然后弄成一个链表。记录原数组每个位置的数在现在链表的哪个位置。从后往前扫一遍，类似前面的能找到前驱后继，然后处理完删除本点。
知识点：
1、链表判合法要同时判表头表尾
1588:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL ZINF = 100000000000ll;
LL n, a[50000];
set<LL > s;
void clean() {
}
int solve() {
scanf("%lld", &n);
for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]);
clean();
s.insert(ZINF), s.insert(-ZINF);
LL ans = a[1];
s.insert(a[1]);
for (LL i = 2; i <= n; ++i) {
set<LL >::iterator it1 = s.lower_bound(a[i]);
set<LL >::iterator it2 = it1;
--it2;
LL tmp = ZINF;
if (*it1 != ZINF && *it1 != -ZINF) tmp = min(tmp, *it1 - a[i]);
if (*it2 != ZINF && *it2 != -ZINF) tmp = min(tmp, a[i] - *it2);
s.insert(a[i]), ans += tmp;
}
printf("%lld\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
链表：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<utility>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 40000;
pair<int, int > a[MAXN];
int n, b[MAXN];
int tot, l[MAXN + 5], r[MAXN + 5], val[MAXN + 5], h, t;
void ins(int pos, int v) {
++tot, l[tot] = pos, r[tot] = r[pos], val[tot] = v;
l[r[pos]] = tot;
r[pos] = tot;
}
void del(int pos) {
l[r[pos]] = l[pos], r[l[pos]] = r[pos];
}
void clean() {
tot = 2, h = 1, t = 2;
r[h] = t, l[t] = h;
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i].fir), a[i].sec = i;
int gg = a[1].fir;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i) b[a[i].sec] = i + 2;
for (int i = 1; i <= n; ++i) ins(i + 2 - 1, a[i].fir);
int ans = 0;
for (int i = n; i > 1; --i) {
int tmp = 2000000000;
if (l[b[i]] != h && l[b[i]] != t) tmp = min(tmp, abs(val[l[b[i]]] - val[b[i]]));
if (r[b[i]] != t && l[b[i]] != h) tmp = min(tmp, abs(val[r[b[i]]] - val[b[i]]));
ans += tmp;
del(b[i]);
}
printf("%d\n", ans + gg);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
1208:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
namespace flyinthesky {
const LL ZINF = 1000000000000ll, MO = 1000000;
LL n, ans;
set<LL > peo, dg;
void clean() {
}
int solve() {
scanf("%lld", &n); // %I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d
clean();
peo.insert(ZINF), peo.insert(-ZINF);
dg.insert(ZINF), dg.insert(-ZINF);
ans = 0ll;
for (LL a, b, i = 1; i <= n; ++i) {
// cerr << "???" << ans << endl;
scanf("%lld%lld", &a, &b); // %I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d
if (a == 0) {
if ((LL)peo.size() > 2ll) {
set<LL >::iterator it2, it = peo.lower_bound(b);
it2 = it;
--it2;
LL tmp = ZINF;
if (*it != ZINF && *it != -ZINF) {
if (tmp > *it - b) {
tmp = *it - b;
}
}
if (*it2 != ZINF && *it2 != -ZINF) {
if (tmp >= b - *it2) {
tmp = b - *it2;
peo.erase(it2), ans = (ans + tmp) % MO;
continue ;
}
}
peo.erase(it), ans = (ans + tmp) % MO;
} else dg.insert(b);
} else {
if ((LL)dg.size() > 2ll) {
set<LL >::iterator it2, it = dg.lower_bound(b);
it2 = it;
--it2;
LL tmp = ZINF;
//cerr << "HHH" << *it << " " << *it2 << endl;
if (*it != ZINF && *it != -ZINF) {
if (tmp > *it - b) {
tmp = *it - b;
}
}
if (*it2 != ZINF && *it2 != -ZINF) {
if (tmp >= b - *it2) {
tmp = b - *it2;
dg.erase(it2), ans = (ans + tmp) % MO;
continue ;
}
}
dg.erase(it), ans = (ans + tmp) % MO;
//cerr << "FUCK\n";
} else peo.insert(b);
}
}
printf("%lld\n", (ans + MO) % MO);// %I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d
return 0;
}
};
int main() {
flyinthesky::solve();
return 0;
}
