题意：给定n个数和k，把n个数排成序列，满足ai >= ai/k，并使之字典序最大。
解：毒瘤线段树贪心...
以i/k为i的父亲构树。
当这n个数不同的时候，直接后序遍历贪心即可。
正解神奇的一批......
从大到小排序并建线段树，维护fi为每个数自己及左边(大于等于它)之中有多少个数能选。
假设我们i位置选了x，i的siz是s，那么[x, n]的f值要减去s，表示其中s个数被i的子树预定了。
然后当我们算i的儿子的时候，就要把[x, n]的f加上siz son i，避免给自己预定的自己反而不能选。
如何确定x？要尽量大，所以在线段树上往左找。
一个数能被选，需要他的f值不小于siz i
这样我们发现样例都过不了。之前加[x, n]的时候，[1, x-1]没有改变，但是这是不对的，简略来说就是右边对左边有影响。
如果我们选了一个位置，但是右边有一个的f值却小于siz i了。那么你想啊，能选大的不能选小的，显然有问题。就是那个小的的左边都不够，你更靠左怎么可能够...
于是要求[x, n]的f全部不小于siz i。
选出来的x对应的值可能有多个，选择最右的那个。是因为这样有决策包容性？
还是有一点不懂，比如为什么不需要标记一个位置已被选，不怕选重复了吗？
#include <cstdio>
#include <algorithm> const int N = ; int n, a[N], siz[N], pos[N], fa[N], ans[N], X[N], xx;
double k;
int tag[N * ], small[N * ]; inline void pushdown(int o) {
if(tag[o]) {
tag[o << ] += tag[o];
tag[o << | ] += tag[o];
small[o << ] += tag[o];
small[o << | ] += tag[o];
tag[o] = ;
}
return;
} inline void add(int L, int R, int v, int l, int r, int o) {
//printf("add : %d %d %d %d %d \n", L, R, v, l, r);
if(L <= l && r <= R) {
small[o] += v;
tag[o] += v;
return;
}
int mid = (l + r) >> ;
pushdown(o);
if(L <= mid) {
add(L, R, v, l, mid, o << );
}
if(mid < R) {
add(L, R, v, mid + , r, o << | );
}
small[o] = std::min(small[o << ], small[o << | ]);
//printf("min %d %d = %d \n", l, r, small[o]);
return;
} inline int getpos(int k, int l, int r, int o) {
//printf("ask %d %d %d \n", k, l, r);
if(l == r) {
return small[o] < k ? a[r + ] : a[r];
}
int mid = (l + r) >> ;
pushdown(o);
//printf("%d >= %d \n", small[o << 1 | 1], k);
if(small[o << | ] >= k) {
return getpos(k, l, mid, o << );
}
else {
return getpos(k, mid + , r, o << | );
}
} void build(int l, int r, int o) {
if(l == r) {
small[o] = r;
return;
}
int mid = (l + r) >> ;
build(l, mid, o << );
build(mid + , r, o << | );
small[o] = std::min(small[o << ], small[o << | ]);
return;
} int main() {
scanf("%d%lf", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
X[i] = a[i];
}
std::sort(a + , a + n + );
std::sort(X + , X + n + );
std::reverse(a + , a + n + );
int xx = std::unique(X + , X + n + ) - X - ;
for(int i = n; i >= ; i--) {
a[i] = std::lower_bound(X + , X + xx + , a[i]) - X;
siz[i]++;
fa[i] = (i / k);
siz[fa[i]] += siz[i];
} for(int i = ; i <= n; i++) {
pos[a[i]] = i;
} build(, n, ); for(int i = ; i <= n; i++) {
// choose i
if(fa[i]) {
add(ans[fa[i]], n, siz[i], , n, );
}
int t = getpos(siz[i], , n, );
//printf("i = %d t = %d \n", i, t);
t = pos[t]--;
// i choose t
ans[i] = t;
//printf("fa = %d \n", fa[i]);
add(t, n, -siz[i], , n, );
} for(int i = ; i <= n; i++) {
printf("%d ", X[a[ans[i]]]);
}
return ;
}
AC代码
总之很神。