BZOJ 5249: [2018多省省隊聯測]IIIDX(貪心 + 線段樹)

題意

這一天，\(\mathrm{Konano}\) 接到了一個任務，他需要給正在制作中的游戲 \(\mathrm{《IIIDX》}\) 安排曲目 的解鎖順序。游戲內共有\(n\) 首曲目，每首曲目都會有一個難度 \(d\) ，游戲內第 \(i\) 首曲目會在玩家 Pass 第 \(\lfloor \frac{i}{k} \rfloor\) 首曲目后解鎖（ \(\lfloor x \rfloor\) 為下取整符號）若 \(\lfloor \frac{i}{k} \rfloor = 0\) ，則說明這首曲目無需解鎖

舉個例子：當 \(k = 2\) 時，第 \(1\) 首曲目是無需解鎖的（ \(\lfloor \frac{1}{2} \rfloor = 0\) ），第 \(7\) 首曲目需要玩家Pass 第 \(\lfloor \frac{7}{2} \rfloor= 3\) 首曲目才會被解鎖。

\(\mathrm{Konano}\) 的工作，便是安排這些曲目的順序，使得每次解鎖出的曲子的難度不低于作為條件需要玩家通關的曲子的難度，即使得確定順序后的曲目的難度對于每個 \(i\) 滿足

\[d_i \geq d_{\lfloor \frac{i}{k} \rfloor}\]

當然這難不倒曾經在信息學競賽摸魚許久的 \(\mathrm{Konano}\) 。那假如是你，你會怎么解決這份任務呢？

\((1 \le n \le 500000, 1 \le k,d \le 10^9)\)

題解

一開始只想到了樹上貪心的思路qwq 但是拍了幾組就發現錯了

原來是 \(d_i\) 互不相同的時候是對的 相同的時候就會被 \(hack\) 掉 這個很容易舉出反例

還是簡單講一下貪心思路吧...

我們發現這個題目可以轉化成一個樹上問題 (因為每個點有且僅有一個父親(前驅節點)和它有關系)

就是使得原序列字典序盡量大 并且每對父子要滿足兒子權值大于等于父親

不難發現這個我們直接把這棵樹建出來 然后按后序遍歷倒著分配編號就行了 (可以自行模擬一下qwq)

意思就是我們每次貪心地使得序列在前面的點字典序盡量大 并且 它后面有足夠空間來分配的最優方案

?

這個可以用來做正解的思路 我們考慮 序列從前往后 單獨考慮

我們肯定需要當前這個最優 但后面我們不能就草莽就做下決定

所以我們可以考慮 根的為子樹預留空位 的貪心

這個我們舉 題解 的一個例子來考慮吧

我們將原 \(d\) 數組降序排列 例如

\[9,8,7,6,5,5,5,5,4,3,2\]

我們令 \(F_i\) 表示第 \(i\) 個結點左邊預留了的位置個數 那么 \((i-F_i)\) 就是 \(i\) 左邊可用數的數量..

假設結點 \(1\) 的子樹大小為 \(7\) 那么我第 \(1\) 個結點的值即為第 \(7\) 大的數 , \(5\)

我們把最右邊的 \(5\) (第 \(9\) 位) 給第 \(1\) 個結點

那么我們需要在 \([1,8]\) 區間中預定 \(6\) 個數給第 \(1\) 個結點的子樹

?

接著對于第 \(2\) 個結點 (設其子樹大小為 \(s\) )

找到一個 盡量靠左 的位置 \(x\) ( 盡量大 ) 使得 \(x\) 右側的可用數量都不少于 \(x\)

\[\displaystyle \min_{\forall i \ge x, (i-F_i) \ge s} x\]

而且到第 \(i\) 個點如果有父親的話 , 父親的預定額就可以去掉了 ( 只去掉一次 )

但保留父親占的那一個位置就行了

然后這樣就可以保證合法 并且 答案最優了

其實我想講的是如何用線段樹實現這個過程2333

我們其實只要開一顆支持 區間加減 + 區間最小值 的線段樹就行了

維護一段區間 \(i-F_i\) 的最小值 我們就可以將那個 \(\forall\) 變成判一個了qwq

如果這段區間這個最小值不可行 并不直接代表整個區間不存在解 但代表如果整個區間全選上是不行的

然后我們取預定額的時候 把后面點需要預定的全都都減去那么多就行了

?

重點是如何查找那個盡量靠左的位置

你先考慮右區間是否可行 如果右區間 當前 不可行 那么左區間 整個 必不可行 那么直接去右區間看是否有解就行了

如果右區間全部都可行 那么我們去左區間看看是否可行 不進行回溯

如果左區間到底的話發現不可行 那么這個點 在原序列后一個就可行了

?

有一個小問題 如果這樣預留的話 可能查的時候就把那個預留位置給占了啊qwq

但這種情況并不會出現的 因為你當前想要走到左子樹 那么右子樹必須全部滿足

但你之前把右區間一個點直接減到不能走了 所以絕對是不可以出現這種情況的qwq (相當于右區間對左區間 \(chkmin\) )

代碼

/**************************************************************Problem: 5249User: zjp_shadowLanguage: C++Result: AcceptedTime:5244 msMemory:28644 kb
****************************************************************/#include <bits/stdc++.h>
#define For(i, l, r) for(int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for(int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memeset(a, v, sizeof(a))
using namespace std;inline bool chkmin(int &a, int b) { return b < a ? a = b, 1 : 0; }
inline bool chkmax(int &a, int b) { return b > a ? a = b, 1 : 0; }inline int read() {int x = 0, fh = 1; char ch = getchar();for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);return x * fh;
}void File() {freopen ("iiidx.in", "r", stdin);freopen ("iiidx.out", "w", stdout);
}double k;
const int N = 500100;#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r
#define Del(o, v) tag[(o)] += (v), minv[(o)] -= (v);
struct Segment_Tree {int tag[N << 2], minv[N << 2];void push_down(int o) {if (!tag[o]) return; Del(o << 1, tag[o]); Del(o << 1 | 1, tag[o]); tag[o] = 0;}void push_up(int o) { minv[o] = min(minv[o << 1], minv[o << 1 | 1]); }void Build(int o, int l, int r) { tag[o] = 0 ; if (l == r) { minv[o] = l; return ; }int mid = (l + r) >> 1; Build(lson); Build(rson); push_up(o);}void Update(int o, int l, int r, int ul, int ur, int uv) {if (ul <= l && r <= ur) { Del(o, uv); return; }int mid = (l + r) >> 1; push_down(o);if (ul <= mid) Update(lson, ul, ur, uv);if (ur > mid) Update(rson, ul, ur, uv);push_up(o);}int Query(int o, int l, int r, int qv) {if (l == r) return (minv[o] >= qv ? l : l + 1);int mid = (l + r) >> 1, res = 0; push_down(o); if (minv[o << 1 | 1] >= qv) res = Query(lson, qv);else res = Query(rson, qv);push_up(o);return res;}
} T;int Num[N], n, a[N], Size[N], fa[N];
int ans[N], cnt[N];int main() {cin >> n >> k;For (i, 1, n) a[i] = read();sort(a + 1, a + 1 + n);reverse(a + 1, a + 1 + n);Fordown (i, n - 1, 1) if (a[i] == a[i + 1]) cnt[i] = cnt[i + 1] + 1;Fordown (i, n, 1) {++ Size[i];Size[fa[i] = floor(i / k)] += Size[i];}T.Build(1, 1, n);For (i, 1, n) {if (fa[i] && fa[i] != fa[i - 1]) T.Update(1, 1, n, ans[fa[i]], n, -(Size[fa[i]] - 1));int res = T.Query(1, 1, n, Size[i]);res += cnt[res]; ++ cnt[res]; res -= (cnt[res] - 1); ans[i] = res;T.Update(1, 1, n, res, n, Size[i]);}For (i, 1, n) printf ("%d ", a[ans[i]]);return 0;
}