[BZOJ5249][2018多省省隊聯測]IIIDX（貪心+線段樹）

Address

洛谷P4364

BZOJ5249

LOJ#2472

Solution

被這道題虐了兩天

由于 ⌊ i k ⌋ &lt; i \lfloor\frac ik\rfloor&lt;i ⌊ki​⌋<i ，是以難度的拓撲序是一棵樹或森林。

具體地，我們把 ⌊ i k ⌋ \lfloor\frac ik\rfloor ⌊ki​⌋ （如果存在）作為 i i i 的父親節點。

問題轉化為将 d d d 數組填充進節點的權值，使得每個點子樹内的權值都不小于這個點的權值，并輸出字典序最大的方案。

字典序顯然可以貪心。

考慮記下子樹大小 s i z e size size ，并将 d d d 從大到小排序。

一個優 (cuo) 秀 (wu) 的貪心：

節點 1 1 1 為根，那麼節點 1 1 1 及其子樹内配置設定到 d [ 1... s i z e [ 1 ] ] d[1...size[1]] d[1...size[1]] 的權值。

如果 2 2 2 為根，那麼 2 2 2 及其子樹内配置設定到 d [ s i z e [ 1 ] + 1... s i z e [ 1 ] + s i z e [ 2 ] ] d[size[1]+1...size[1]+size[2]] d[size[1]+1...size[1]+size[2]] 的權值。

如果 3 3 3 還是根，則其子樹配置設定到 d [ s i z e [ 1 ] + s i z e [ 2 ] + 1... s i z e [ 1 ] + s i z e [ 2 ] + s i z e [ 3 ] ] d[size[1]+size[2]+1...size[1]+size[2]+size[3]] d[size[1]+size[2]+1...size[1]+size[2]+size[3]] ，以此類推。

如果 u u u 有父親 v v v 且 v v v 預配置設定到了 d [ l . . . r ] d[l...r] d[l...r] ，就同樣把 d [ l . . . r ] d[l...r] d[l...r] 如上面一樣分組并配置設定給 u u u 。

才怪。 55 分。

考慮 d d d 有相同權值的時候，如：

n = 6 , k = 3 , d = { 3 , 3 , 2 , 2 , 2 , 2 } n=6,k=3,d=\{3,3,2,2,2,2\} n=6,k=3,d={3,3,2,2,2,2}

那麼這是由兩棵樹構成的森林，一棵大小為 4 4 4 另一棵為 2 2 2 。

顯然，第一棵樹要配置設定權值的最小值為 2 2 2 ，即節點 1 1 1 要填充 2 2 2 。

然而如果這時第一棵樹不填充 { 3 , 3 , 2 , 2 } \{3,3,2,2\} {3,3,2,2} 而填充 { 2 , 2 , 2 , 2 } \{2,2,2,2\} {2,2,2,2} 就可以把剩下的 { 3 , 3 } \{3,3\} {3,3} 讓給第二棵樹，得到字典序更大的解。

于是我們改變貪心政策：在 d d d 中從右往左找到最左位置 x x x 使得節點 x x x 的左邊（包括 x x x ）至少存在 s i z e [ u ] size[u] size[u] 個未被取走的節點，然後找到一個 y y y 使得滿足 d [ x ] = d [ y ] d[x]=d[y] d[x]=d[y] 且 y y y 最大。這時候節點 u u u 填充的權值為 d [ y ] d[y] d[y] 。

考慮用線段樹。設 p [ i ] p[i] p[i] 表示 d [ i ] d[i] d[i] 的左邊還有多少個點可取。

計算一個節點 u u u 時，可以得出如果 u u u 的權值能取 d [ i ] d[i] d[i] ，那麼一定滿足：

min ⁡ j = i n p [ j ] ≥ s i z e [ u ] \min_{j=i}^np[j]\ge size[u] j=iminn​p[j]≥size[u]

可以線上段樹上二分得到這個最小的 i i i 。需要記錄區間最小值。

然後找到一個 j j j 滿足 d [ i ] = d [ j ] d[i]=d[j] d[i]=d[j] ， d [ j ] d[j] d[j] 沒有被取走并且 j j j 最大。

然後把 u u u 的權值設為 d [ j ] d[j] d[j] ，這時候， p [ j . . . n ] p[j...n] p[j...n] 都要減去 s i z e [ u ] size[u] size[u] 。維護标記即可。這可以看成是為 u u u 的子樹預留 s i z e [ u ] size[u] size[u] 個權值。

同時注意細節：如果一個點 u u u 有父親 v v v ，那麼這時候 u u u 就可 (bi) 以 (xu) 放在 v v v 的子樹内（廢話），是以要把 v v v 為子樹所預留的點（不包括 v v v 自己）還給 u u u 以及 v v v 的其他子節點，也就是 p [ a n s [ v ] . . . n ] p[ans[v]...n] p[ans[v]...n] 減去 s i z e [ v ] − 1 size[v]-1 size[v]−1 。特别注意 v v v 隻需要在第一個子節點 u u u 處消除影響一次。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
#define p2 p << 1
#define p3 p << 1 | 1
using namespace std;
inline int read() {
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}
const int N = 5e5 + 5, M = N << 2;
int n, d[N], fa[N], sze[N], f[M], add[M], pre[N], nxt[N], ans[N];
double k;
int comp(int a, int b) {
	return a > b;
}
void build(int l, int r, int p) {
	if (l == r) return (void) (f[p] = l);
	int mid = l + r >> 1;
	build(l, mid, p2); build(mid + 1, r, p3);
	f[p] = min(f[p2], f[p3]);
}
void down(int p) {
	add[p2] += add[p]; add[p3] += add[p];
	add[p] = 0;
}
void upt(int p) {
	f[p] = min(f[p2] + add[p2], f[p3] + add[p3]);
}
void change(int l, int r, int s, int e, int v, int p) {
	if (l == s && r == e) return (void) (add[p] += v);
	int mid = l + r >> 1;
	down(p);
	if (e <= mid) change(l, mid, s, e, v, p2);
	else if (s >= mid + 1) change(mid + 1, r, s, e, v, p3);
	else change(l, mid, s, mid, v, p2),
		change(mid + 1, r, mid + 1, e, v, p3);
	upt(p);
}
int ask(int l, int r, int k, int p) {
	if (l == r) return f[p] + add[p] >= k ? l : l + 1;
	int mid = l + r >> 1, res;
	down(p);
	if (f[p3] + add[p3] >= k) res = ask(l, mid, k, p2);
	else res = ask(mid + 1, r, k, p3);
	return upt(p), res;
}
int main() {
	int i;
	cin >> n >> k;
	For (i, 1, n) d[i] = read();
	sort(d + 1, d + n + 1, comp);
	For (i, 1, n) fa[i] = floor(1.0 * i / k);
	For (i, 1, n) {
		pre[i] = i;
		if (i > 1 && d[i - 1] == d[i]) pre[i] = pre[i - 1];
	}
	Rof (i, n, 1) {
		nxt[i] = i;
		if (i < n && d[i] == d[i + 1]) nxt[i] = nxt[i + 1];
	}
	For (i, 1, n) sze[i] = 1;
	Rof (i, n, 1) if (fa[i]) sze[fa[i]] += sze[i];
	build(1, n, 1);
	For (i, 1, n) {
		if (fa[i] && fa[i] != fa[i - 1])
			change(1, n, ans[fa[i]], n, sze[fa[i]] - 1, 1);
		int pos = ask(1, n, sze[i], 1), p = pre[pos], q = nxt[p];
		nxt[p]--; ans[i] = q;
		change(1, n, q, n, -sze[i], 1);
	}
	For (i, 1, n) printf("%d ", d[ans[i]]);
	cout << endl;
	return 0;
}