洛谷P4364 IIIDX

题意：给定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对应的值可能有多个，选择最右的那个。是因为这样有决策包容性？

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

 #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代码

总之很神。

巴特西

洛谷P4364 IIIDX

最新文章

热门文章