【九省联考2018】【BZOJ5249】【LOJ2472】iiidx

【题目链接】

BZOJ5249LOJ2472

【前置技能】

贪心线段树

【题解】

对于所有$d_i$互不相同的部分分，有一个贪心的做法。先把所有数排序并且假装有一个虚拟的$0$号节点，首先，根节点一定要取最小的数（$0$号节点就不管它），对于其他子树，把较大的数值预留给编号小的子树，然后分治下去做。但是当不保证$d_i$互不相同的情况下，这个算法就是错误的。举一个简单的例子，$n=5,k=2,d=\{1,1,1,1,2\}$，贪心的做法得出的答案是$1,1,1,2,1$，而正确答案是$1,1,2,1,1$。那么就不能直接简单地贪心了，但是这个贪心的思路还是很优秀的。其实我们要做的就是逐位确定答案，从小到大处理每一个位置。发现在当前位置能放的数是可二分的，如果放$x$能够满足条件的话，小于$x$的数一定也满足条件。现在需要支持找到最大的满足条件的数，考虑用维护区间最小值的线段树来支持这个过程。这一次为了写起来方便，不妨将$d$数组倒序排序，线段树的每个节点记录这个节点（包括自己）的左边还有多少个位置可以放。每个位置的答案在线段树上二分，找到最靠左的一个数，满足其后缀min大于等于当前子树的size。当存在与答案相同的数时，为了让后面靠前的位置的答案有可能更大，选择相同的数中最靠右的那一个。然后将这个数右边（包括自己）的所有节点维护的值减去当前子树的size，表示为这棵子树占用的位置。在进行操作之前，还要记得把父亲节点为根的子树占用的位置消除掉。时间复杂度$O(NlogN)$

【代码】

#include<bits/stdc++.h> #define MAXN 500010 #define EPS 1e-10 using namespace std; int n, a[MAXN], fa[MAXN], size[MAXN], ans[MAXN], nxt[MAXN]; double k; template <typename T> void chkmin(T &x, T y){x = min(x, y);} template <typename T> void chkmax(T &x, T y){x = max(x, y);} template <typename T> void read(T &x){ x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } struct Segment_Tree{ struct info{int ls, rs, minn, maxn, tag;}a[MAXN * 3]; int root, cnt; void push_down(int pos){ a[a[pos].ls].tag += a[pos].tag; a[a[pos].rs].tag += a[pos].tag; a[a[pos].ls].minn += a[pos].tag; a[a[pos].rs].minn += a[pos].tag; a[a[pos].ls].maxn += a[pos].tag; a[a[pos].rs].maxn += a[pos].tag; a[pos].tag = 0; } void merge(int pos){ a[pos].minn = min(a[a[pos].ls].minn, a[a[pos].rs].minn); a[pos].maxn = max(a[a[pos].ls].maxn, a[a[pos].rs].maxn); } void build(int &pos, int l, int r){ pos = ++cnt; if (l == r) { a[pos].minn = a[pos].maxn = l; return; } int mid = (l + r) >> 1; build(a[pos].ls, l, mid); build(a[pos].rs, mid + 1, r); merge(pos); } void init(){ cnt = root = 0; build(root, 1, n); } void modify(int pos, int l, int r, int ll, int rr, int d){ push_down(pos); if (l == ll && r == rr){ a[pos].tag += d; a[pos].minn += d; a[pos].maxn += d; return; } int mid = (l + r) >> 1; if (rr <= mid) modify(a[pos].ls, l, mid, ll, rr, d); else if (ll > mid) modify(a[pos].rs, mid + 1, r, ll, rr, d); else { modify(a[pos].ls, l, mid, ll, mid, d); modify(a[pos].rs, mid + 1, r, mid + 1, rr, d); } merge(pos); } void modify(int x, int d){ modify(1, 1, n, x, n, d); } int query(int pos, int l, int r, int val){ push_down(pos); if (a[pos].minn >= val) return l; if (a[pos].maxn < val) return r + 1; int mid = (l + r) >> 1; if (a[a[pos].rs].minn >= val) return query(a[pos].ls, l, mid, val); else return query(a[pos].rs, mid + 1, r, val); } int query(int x){ return nxt[query(1, 1, n, x)]; } }sgt; bool cmp(int a, int b){ return a > b; } int main(){ read(n); scanf("%lf", &k); for (int i = 1; i <= n; ++i) read(a[i]); sort(a + 1, a + 1 + n, cmp); for (int i = n; i >= 1; --i) nxt[i] = (a[i] == a[i + 1]) ? nxt[i + 1] : i; for (int i = n; i >= 1; --i) fa[i] = (int)(i / k + EPS), ++size[i], size[fa[i]] += size[i]; sgt.init(); for (int i = 1; i <= n; ++i){ if (fa[i] && (fa[i] != fa[i - 1])) sgt.modify(ans[fa[i]], size[fa[i]] - 1); ans[i] = sgt.query(size[i]); sgt.modify(ans[i], -size[i]); } for (int i = 1; i <= n; ++i) printf("%d%c", a[ans[i]], " \n"[i == n]); return 0; }