一直没有填的坑……今天乱写了写跑过了然后厚颜无耻凑一篇题解

还有样例过于草（出题人钦点淫梦运营）

考虑从小到大枚举序列的每一位置\(p\)，然后我们发现每一位置的值的合法性事单调的（小的合法，大了就不合法），这样可以对每一个位置二分答案。

然后我们考虑二分完了答案\(x\)怎么判定。把值离散化一下然后用一个线段树来维护\(T_i\)（表示当前还没有被预定的大于等于\(i\)的数有多少个），然后判定答案就看到\(x\)的前缀区间是否都不小于\(p\)所在子树的大小。同时注意顺次枚举每个点的时候要去除他对他父亲的影响，然后每次一个点确定是什么值了也要修改对应的前缀区间。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using R = long double;
const int maxn = 500005;
const int maxno = maxn << 2;
int n; R k;
int minv[maxno], addv[maxno];
void maintain(int o) {
  int lc = o << 1, rc = o << 1 | 1;
  minv[o] = std::min(minv[lc], minv[rc]);
}
void paint(int o, int v) {
  addv[o] += v; minv[o] += v;
}
void pushdown(int o) {
  if(addv[o] != 0) {
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, addv[o]); paint(rc, addv[o]);
    addv[o] = 0;
  }
}

int left[maxn];
void build_tree(int o, int L, int R) {
  // addv[o] = 0;
  if(L == R) {
    minv[o] = left[L];
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void update(int o, int L, int R, int ql, int qr, int v) {
  if(ql <= L && R <= qr) {
    paint(o, v);
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
    maintain(o);
  }
}
const int INF = 0x7f7f7f7f;
int query_min(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return minv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2, ans = INF;
    if(ql <= M) ans = std::min(ans, query_min(o << 1, L, M, ql, qr));
    if(qr > M) ans = std::min(ans, query_min(o << 1 | 1, M + 1, R, ql, qr));
    return ans;
  }
}

int d[maxn], d2[maxn];
int lsiz;
void process() {
  std::sort(d + 1, d + 1 + n);
  std::sort(d2 + 1, d2 + 1 + n);
  lsiz = std::unique(d2 + 1, d2 + 1 + n) - d2 - 1;
  for(int i = 1; i <= n; i ++) {
    d[i] = std::lower_bound(d2 + 1, d2 + 1 + lsiz, d[i]) - d2;
    left[d[i]] ++;
  }
  for(int i = lsiz - 1; i >= 1; i --) {
    left[i] += left[i + 1];
  }
  build_tree(1, 1, lsiz);
}
int A[maxn], siz[maxn];
void solve() {
  for(int i = n; i >= 1; i --) {
    siz[i] ++;
    int f = (int)floor((R(i)) / k);
    siz[f] += siz[i];
  }
  for(int i = 1; i <= n; i ++) {
    int f = (int)floor((R(i)) / k);
    if(f > 0) {
      update(1, 1, lsiz, 1, A[f], siz[i]);
    }
    int L = (f == 0) ? 1 : A[f], R = lsiz, ret;
    while(true) {
      if(R - L <= 3) {
        for(int j = R; j >= L; j --) {
          if(query_min(1, 1, lsiz, 1, j) >= siz[i]) {
            ret = j; break;
          }
        }
        break;
      }
      int M = L + (R - L) / 2;
      if(query_min(1, 1, lsiz, 1, M) >= siz[i]) {
        L = M;
      } else {
        R = M;
      }
    }
    A[i] = ret; update(1, 1, lsiz, 1, ret, -siz[i]);
  }
}

int main() {
  scanf("%d%Lf", &n, &k);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &d[i]); d2[i] = d[i];
  }
  process(); solve();
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    printf("%d", d2[A[i]]);
  }
  puts(""); return 0;
}

• 相关文章
• 全局相关文章