题意：给定n个数和k，把n个数排成序列，满足a_i >= a_i/k，并使之字典序最大。

解：毒瘤线段树贪心...

以i/k为i的父亲构树。

当这n个数不同的时候，直接后序遍历贪心即可。

正解神奇的一批......

从大到小排序并建线段树，维护f_i为每个数自己及左边(大于等于它)之中有多少个数能选。

假设我们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对应的值可能有多个，选择最右的那个。是因为这样有决策包容性？

还是有一点不懂，比如为什么不需要标记一个位置已被选，不怕选重复了吗？

1 #include 
      
         2 #include 
       
          3   4 const int N = 500010;  5   6 int n, a[N], siz[N], pos[N], fa[N], ans[N], X[N], xx;  7 double k;  8 int tag[N * 4], small[N * 4];  9  10 inline void pushdown(int o) { 11     if(tag[o]) { 12         tag[o << 1] += tag[o]; 13         tag[o << 1 | 1] += tag[o]; 14         small[o << 1] += tag[o]; 15         small[o << 1 | 1] += tag[o]; 16         tag[o] = 0; 17     } 18     return; 19 } 20  21 inline void add(int L, int R, int v, int l, int r, int o) { 22     //printf("add : %d %d %d %d %d \n", L, R, v, l, r); 23     if(L <= l && r <= R) { 24         small[o] += v; 25         tag[o] += v; 26         return; 27     } 28     int mid = (l + r) >> 1; 29     pushdown(o); 30     if(L <= mid) { 31         add(L, R, v, l, mid, o << 1); 32     } 33     if(mid < R) { 34         add(L, R, v, mid + 1, r, o << 1 | 1); 35     } 36     small[o] = std::min(small[o << 1], small[o << 1 | 1]); 37     //printf("min %d %d  = %d \n", l, r, small[o]); 38     return; 39 } 40  41 inline int getpos(int k, int l, int r, int o) { 42     //printf("ask %d %d %d \n", k, l, r); 43     if(l == r) { 44         return small[o] < k ? a[r + 1] : a[r]; 45     } 46     int mid = (l + r) >> 1; 47     pushdown(o); 48     //printf("%d >= %d \n", small[o << 1 | 1], k); 49     if(small[o << 1 | 1] >= k) { 50         return getpos(k, l, mid, o << 1); 51     } 52     else { 53         return getpos(k, mid + 1, r, o << 1 | 1); 54     } 55 } 56  57 void build(int l, int r, int o) { 58     if(l == r) { 59         small[o] = r; 60         return; 61     } 62     int mid = (l + r) >> 1; 63     build(l, mid, o << 1); 64     build(mid + 1, r, o << 1 | 1); 65     small[o] = std::min(small[o << 1], small[o << 1 | 1]); 66     return; 67 } 68  69 int main() { 70     scanf("%d%lf", &n, &k); 71     for(int i = 1; i <= n; i++) { 72         scanf("%d", &a[i]); 73         X[i] = a[i]; 74     } 75     std::sort(a + 1, a + n + 1); 76     std::sort(X + 1, X + n + 1); 77     std::reverse(a + 1, a + n + 1); 78     int xx = std::unique(X + 1, X + n + 1) - X - 1; 79     for(int i = n; i >= 1; i--) { 80         a[i] = std::lower_bound(X + 1, X + xx + 1, a[i]) - X; 81         siz[i]++; 82         fa[i] = (i / k); 83         siz[fa[i]] += siz[i]; 84     } 85  86     for(int i = 1; i <= n; i++) { 87         pos[a[i]] = i; 88     } 89  90     build(1, n, 1); 91  92     for(int i = 1; i <= n; i++) { 93         // choose i 94         if(fa[i]) { 95             add(ans[fa[i]], n, siz[i], 1, n, 1); 96         } 97         int t = getpos(siz[i], 1, n, 1); 98         //printf("i = %d  t = %d \n", i, t); 99         t = pos[t]--;100         // i choose t101         ans[i] = t;102         //printf("fa = %d \n", fa[i]);103         add(t, n, -siz[i], 1, n, 1);104     }105 106     for(int i = 1; i <= n; i++) {107         printf("%d ", X[a[ans[i]]]);108     }109     return 0;110 }
       
      

总之很神。