题意：n个摆成一根直线的盒子，有依赖关系（连续的盒子的父亲是一个盒子），你有n个带编号的球（编号可能相同），要放在盒子里面，要求一个盒子的编号要大于其父亲的编号，并且要求序列顺序下前面的值尽量大
先考虑球两两不同的情况：我们先按权值大小从大到小排序，然后从序列顺序依次考虑每棵子树，如：
5 4 3 2 1
1的子树大小为3，那么我们就拿出5 4 3为第一棵子树，类推即可
接下来我们考虑为什么这样做是错的：
3 3 2 2 1
a b
|\ |
c d e
假如还是3个点，我们取了3 3 2，发现不是最优的，正确的方法是3 2 2，然后第二个子树是3 1
我们来考虑维护两个东西：
- f_i表示从大到小第i个球前面有多少个球（至少现在是这个意思），那么初始化就是f_i=i
- g_i表示从大到小第i个球到后面有多少个球和自己一样（不含自己），如上面的那个序列就是
1 0 1 0 0
接下来我们查询放x=3个球的最大是哪个球，发现是第三个球，但是g_3 = 1，于是我们在第四位及其以后每一位f_i = f_i -3代表[1, 4]有3个球被占用，序列变成1 2 3 1 2，这个时候你就发现f的意思不大一样了...
新的序列我们可以考虑为这样：如果存在一个j > i使f_i > f_j，那么就说明f_i已经被锁定了。（我们锁f_i大的方便我们取f_i小的，也就是编号大的）
接下来我们要取两个球，因为球的编号要尽量大，所以我们取尽量左边的球，我们发现第二位的2，但是第二位右边有个1，说明那个2是不能取的（1~4只有一个球是空闲的！取了这里面的2，那子树就没有球了！），我们就找到第二个2，然后f_i=f_i-2\quad i\ge 5预留2个球，序列变成1 2 3 1 0，最右边有个0，说明我们这个序列没有球了。
接下来看c盒子，由于父亲a留了2个球给他的儿子，我们现在对留给我们的球解锁，把父亲减数的点加size_a - 1，序列变成1 2 3 3 2，然后取1个点出来，...
我们再总结一下：
a = [3 3 2 2 1]
f = [1 2 3 4 5]
g = [1 0 1 0 0]
size[1] = 3
f[x]?v=3 -> x = 3
x += g[x] -> x = 4
f[4...] -= 3 -> [1 2 3 1 2]
ans[1] = x -> 4 (a[4] = 2)
size[2] = 2
f[x]?v=2 -> x = 2
\because f[4] = 1
\therefore f[x]?v=2&&x>4 -> x = 5
x += g[5] -> x = 5
f[5...] -= 2 -> [1 2 3 1 0]
size[3] = 1
fa[3] = 1
vis[fa[3]] == false
\therefore f[ans[1]...] += size[ans[1] - 1]
->[1 2 3 3 4]
f[x]?v=1 -> x = 1
x += g[x] -> x = 2
f[2...] -= 1 -> [1 1 2 2 3]
可能你看完还是迷迷糊糊的，我们回过头来看这个“f”序列：
- 意思还是“从大到小第i个球前面有多少个”
- 排好序以后一段连续的球我们考虑在最右的那个球打标记，考虑这个情况：
3 3 2 2 1
a b c
|\
c d
我们在尽可能在右边的地方打标记，方便后面（可以的话）取更左边的球
3 3 0 2 1 -> b没法取第一个球
3 3 2 1 1
然后我们看相同球序列最右边和非最右边的区别
1 2 2 2 3
1 2 3 4 5
1. 我们不管取第二第三个，最后都是在第四个球处加加减减
2. 最后加加减减3次以后，f_4=1，能够代表整段2不能选了
3. 对f_x减一个数之后，f_i > f_x且i < x的球将在f_x解锁之后继续保持作用（不再可能保持就代表那个球被选了），而相同球序列最右边的f用了一次以后就肯定不会再次选了（想想为什么），所以f序列是有效的
对f使用线段树维护，参见代码：
void update(int p)
{
P = std::min(L, R);
}
void pushdown(int p)
{
if (t[p])
{
L += t[p];
R += t[p];
t[LV] += t[p];
t[RV] += t[p];
t[p] = 0;
}
}
void add(int p, int l, int r)
{
if (pl <= l && r <= pr)
{
P += pv;
t[p] += pv;
return;
}
pushdown(p);
int mid = (l + r) >> 1;
if (pl <= mid) add(LV, l, mid);
if (mid < pr) add(RV, mid + 1, r);
update(p);
}
int get(int p, int l, int r)
{
if (l == r) return P >= px ? l : l + 1;
//上面那个三元表达式：考虑1 1 2 3取2
pushdown(p);
if (px > R) //说明不能选左边的序列
return get(RV, ((l + r) >> 1) + 1, r);
else
return get(LV, l, (l + r) >> 1);
}
signed main(void)
{
scanf("%d %lf", &n, &k);
for (int i = 1; i <= n; ++i) a[i] = read;
std::sort(a + 1, a + n + 1, std::greater<int>());
Seg::build(1, 1, n);
for (int i = n; i; --i)
{
size[i] += 1;
size[FA(i)] += size[i];
ptr[i] = a[i] == a[i + 1] ? ptr[i + 1] + 1 : 0;
}
for (int i = 1; i <= n; ++i)
{
static bool vis[N];
static int fa;
fa = FA(i);
if (fa && !vis[fa])
{
Seg::add(ans[fa], size[fa] - 1);
vis[fa] = true;
}
int tg = Seg::get(size[i]);
tg += ptr[tg];
ans[i] = tg;
Seg::add(tg, -size[i]);
}
for (int i = 1; i <= n; ++i) printf("%d ", a[ans[i]]);
}
附赠完整代码：
#include <bits/stdc++.h>
struct Read
{
//...
} read;
const size_t N = 500000 + 10;
int n, a[N], size[N], ans[N], ptr[N];
double k;
namespace Seg
{
int v[N << 2];
int t[N << 2];
#define LV (p << 1)
#define RV (LV | 1)
#define L (v[LV])
#define R (v[RV])
#define P (v[p])
void build(int p, int l, int r)
{
P = l;
if (l == r) return;
int mid = (l + r) >> 1;
build(LV, l, mid);
build(RV, mid + 1, r);
}
void update(int p)
{
P = std::min(L, R);
}
void pushdown(int p)
{
if (t[p])
{
L += t[p];
R += t[p];
t[LV] += t[p];
t[RV] += t[p];
t[p] = 0;
}
}
int pl, pr, px;
signed pv;
void add(int p, int l, int r)
{
if (pl <= l && r <= pr)
{
P += pv;
t[p] += pv;
return;
}
pushdown(p);
int mid = (l + r) >> 1;
if (pl <= mid) add(LV, l, mid);
if (mid < pr) add(RV, mid + 1, r);
update(p);
}
int get(int p, int l, int r)
{
if (l == r) return P >= px ? l : l + 1;
pushdown(p);
if (px > R)
return get(RV, ((l + r) >> 1) + 1, r);
else
return get(LV, l, (l + r) >> 1);
}
void add(int l, signed v)
{
pl = l, pr = n, pv = v;
add(1, 1, n);
}
int get(int p)
{
px = p;
return get(1, 1, n);
}
}
#define FA(a) ((int)(((double)a) / k))
signed main(void)
{
scanf("%d %lf", &n, &k);
for (int i = 1; i <= n; ++i) a[i] = read;
std::sort(a + 1, a + n + 1, std::greater<int>());
Seg::build(1, 1, n);
for (int i = n; i; --i)
{
size[i] += 1;
size[FA(i)] += size[i];
ptr[i] = a[i] == a[i + 1] ? ptr[i + 1] + 1 : 0;
}
for (int i = 1; i <= n; ++i)
{
static bool vis[N];
static int fa;
fa = FA(i);
if (fa && !vis[fa])
{
Seg::add(ans[fa], size[fa] - 1);
fprintf(stderr, "change(%d, %d)\n", ans[fa], size[fa] - 1);
vis[fa] = true;
}
int tg = Seg::get(size[i]);
tg += ptr[tg];
ans[i] = tg;
fprintf(stderr, "change(%d, %d)\n", tg, -size[i]);
Seg::add(tg, -size[i]);
}
for (int i = 1; i <= n; ++i) printf("%d ", a[ans[i]]);
}