AcWing 邻值查找
Description
给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 ，求：min1≤j<i|Ai−Aj|
以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 较小的那个。
Input
第一行输入整数n，代表序列长度。
第二行输入n个整数A1…An,代表序列的具体数值，数值之间用空格隔开。
Output
输出共n-1行，每行输出两个整数，数值之间用空格隔开。
分别表示当i取2~n时，对应的min1≤j<i|Ai−Aj|和的值。
Data Size
- n≤10 ^ 5,|Ai|≤10 ^ 9
Sample Input
31 5 3
Sample Output
4 12 1
题解：
- fhq-treap，按权分裂。
- 显然要找离当前数最近的数，那就是前继和后继喽。
- 用平衡树水过… …
#include#include #include #include #define N 100005#define inf 1e11#define int long longusing namespace std;struct Ret {int val, pos;};struct T {int l, r, val, pos, dat;} t[N];int n, root, tot, x, y, z;int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x *= f;}int New(int val, int pos){ t[++tot].val = val; t[tot].pos = pos; t[tot].dat = rand(); return tot;}void split(int p, int val, int &x, int &y){ if(!p) {x = y = 0; return;} if(t[p].val <= val) { x = p; split(t[p].r, val, t[p].r, y); } else { y = p; split(t[p].l, val, x, t[p].l); }}int merge(int x, int y){ if(!x || !y) return x + y; if(t[x].dat > t[y].dat) { t[x].r = merge(t[x].r, y); return x; } else { t[y].l = merge(x, t[y].l); return y; }}void insert(int val, int pos){ split(root, val, x, y); root = merge(merge(x, New(val, pos)), y);}Ret preNext(int op, int val){ Ret tmp; if(!op) { split(root, val - 1, x, y); int p = x; while(t[p].r) p = t[p].r; tmp.val = t[p].val, tmp.pos = t[p].pos; } else { split(root, val, x, y); int p = y; while(t[p].l) p = t[p].l; tmp.val = t[p].val, tmp.pos = t[p].pos; } root = merge(x, y); return tmp;}signed main(){ New(-inf, 0), New(inf, 0), root = merge(1, 2); cin >> n; insert(read(), 1); for(int i = 2; i <= n; i++) { int val = read(); Ret o1 = preNext(0, val), o2 = preNext(1, val); o1.val = abs(o1.val - val), o2.val = abs(o2.val - val); if(o1.val <= o2.val) printf("%d %d\n", o1.val, o1.pos); else printf("%d %d\n", o2.val, o2.pos); insert(val, i); } return 0;}