【BZOJ1588】splay

题意十分好懂

分析
十分简单的一道题啊。
显然，除了第一个，剩下的我们就查一下小于它的最后一个和大于它的第一个，然后比较一下加上去，就做完了。

于是：

…
我就写了一个半小时。
…

哭完了之后我们回到上面的分析。

我们查找的东西很简单，所以我们直接用set就可以很容易的维护这个东西。

我们lower_bound(x)，找到后继，然后it–找到前驱，于是就真的做完了。

#include 
#define sc(n) scanf("%d",&n)
#define pt(n) printf("%d\n",n)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define vi vector
#define vl vector
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5+7;
int a[maxn];
int n;
int main()
{scanf("%d",&n);int ans = 0;set<int> s;for(int i=1;i<=n;i++) scanf("%d",a+i);	s.insert(INF);s.insert(-INF);for(int i=1;i<=n;i++){if(s.size()==2){ans += a[i];s.insert(a[i]);continue;}set<int>::iterator it = s.lower_bound(a[i]);if(*it!=a[i]){set<int>::iterator t = it;t--;ans += min(abs(*it-a[i]),abs(*t-a[i]));s.insert(a[i]);}}printf("%d\n",ans);return 0;
}

但是这个题目，询问前驱和后继，很裸的平衡树的问法吧。
于是我就愉快的码了一个小时的splay。。。

#include 
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2e5+7;
int ch[maxn][2], fa[maxn], val[maxn], cnt[maxn], siz[maxn], ncnt, root;
bool chk(int x) 
{return ch[fa[x]][1]==x;
}
void pushup(int x) 
{siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
}
void rotate(int x) 
{int y = fa[x], z = fa[y], k = chk(x), w = ch[x][k^1];ch[y][k] = w; fa[w] = y;ch[z][chk(y)] = x;fa[x] = z;ch[x][k^1] = y; fa[y] = x;pushup(y); pushup(x);
}
void splay(int x, int goal = 0) 
{while(fa[x] != goal) {int y = fa[x], z = fa[y];if (z != goal) {if(chk(x) == chk(y)) rotate(y);else rotate(x);}rotate(x);}if(!goal) root = x;
}
void insert(int x) 
{int cur = root, p = 0;while(cur && val[cur] != x) {p = cur;cur = ch[cur][x > val[cur]];}if(cur) cnt[cur]++;else {cur = ++ncnt;if(p) ch[p][x > val[p]] = cur;ch[cur][0] = ch[cur][1] = 0;fa[cur] = p; val[cur] = x;cnt[cur] = siz[cur] = 1;}splay(cur);
}
void find(int x) 
{int cur = root;while(ch[cur][x > val[cur]] && x != val[cur]) {cur = ch[cur][x > val[cur]];}splay(cur);
}
int kth(int k) 
{int cur = root;while(true) {if(ch[cur][0] && k <= siz[ch[cur][0]]) {cur = ch[cur][0];} else if(k > siz[ch[cur][0]] + cnt[cur]) {k -= siz[ch[cur][0]] + cnt[cur];cur = ch[cur][1];} else {return cur;}}
}
int pre(int x) 
{find(x);if(val[root] <= x) return root;int cur = ch[root][0];while(ch[cur][1]) cur = ch[cur][1];return cur;
}int succ(int x) 
{find(x);if (val[root] >= x) return root;int cur = ch[root][1];while(ch[cur][0]) cur = ch[cur][0];return cur;
}void remove(int x) 
{int last = pre(x), next = succ(x);splay(last); splay(next, last);int del = ch[next][0];if(cnt[del] > 1) {cnt[del]--;splay(del);}else ch[next][0] = 0;
}
int main() 
{int n;scanf("%d", &n);int ans = 0;insert(INF);insert(-INF);for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(i==1) ans += x; else{ans += min(abs(x-val[pre(x)]),abs(x-val[succ(x)]));}insert(x);}printf("%d\n",ans);
}

没了。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！