洛谷 P3466 [POI2008]KLO-Building blocks
题目：
题解：
- fhq-treap，按权分裂。
- 题目要求“连续K柱的高度是一样”，那么这个最终高度肯定是这K柱砖里的中位数。那么思绪就是枚举K柱砖的开头，求出每组砖的中位数，再求出花费。最终取一个最小花费。
- 考虑优化，求动态中位数可以用对顶堆/平衡树，那么我选用fhq-treap。
- 考虑优化，计算花费的思绪是暴力枚举K柱砖计算，其实观察可得到公式：花费 = (比mid小的数的个数 * mid - 比mid小的数之和) + (比mid大的数之和 - 比mid大的数的个数 * mid)。那么公式里涉及的几个量可以在平衡树更新过程中顺带更新出来。只需在结构体里开size和sum两个量，up操作时一起更新一下即可。
- 所以此题选用fhq-treap解决问题。具体如何实现见代码
#include #include #include #define N 100005#define int long long#define inf 1e11using namespace std;struct T {int l, r, val, dat, size, sum;} t[N];int n, k, pos, root, tot, x, y, z, tim = inf, st, ans;int a[N];int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}int New(int val){ t[++tot].val = val, t[tot].dat = rand(); t[tot].size = 1, t[tot].sum = val; return tot;}void up(int p){ t[p].size = t[t[p].l].size + t[t[p].r].size + 1; t[p].sum = t[t[p].l].sum + t[t[p].r].sum + t[p].val;}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); } up(p);}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); up(x); return x; } else { t[y].l = merge(x, t[y].l); up(y); return y; }}void insert(int val){ split(root, val, x, y); root = merge(merge(x, New(val)), y);}void erase(int val){ split(root, val, x, z); split(x, val - 1, x, y); y = merge(t[y].l, t[y].r); root = merge(merge(x, y), z);}int valOfRank(int rank){ int p = root; while(p) { if(t[t[p].l].size >= rank) p = t[p].l; else if(t[t[p].l].size + 1 == rank) break; else rank -= t[t[p].l].size + 1, p = t[p].r; } return t[p].val;}int cal(int mid){ split(root, mid - 1, x, y); split(y, mid, y, z); int ans = (t[x].size * mid - t[x].sum) + (t[z].sum - t[z].size * mid); root = merge(x, merge(y, z)); return ans;}signed main(){ cin >> n >> k, pos = (k + 1) / 2; for(int i = 1; i < k; i++) a[i] = read(), insert(a[i]); for(int i = k; i <= n; i++) { a[i] = read(), insert(a[i]); int mid = valOfRank(pos), val = cal(mid); if(val < tim) tim = val, ans = mid, st = i - k + 1; erase(a[i - k + 1]); } for(int i = st; i <= st + k - 1; i++) a[i] = ans; cout << tim << endl; for(int i = 1; i <= n; i++) printf("%lld\n", a[i]); return 0;}