[LibreOJ 2472][九省联考2018]IIIDX

danihao123 posted @ 2018年6月28日 16:57 in 题解 with tags 线段树 二分答案 loj 九省联考 , 713 阅读
转载请注明出处:http://danihao123.is-programmer.com/

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

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

考虑从小到大枚举序列的每一位置\(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;
}
Grade 5 Result Chitt 说:
Aug 29, 2022 10:27:32 PM

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. Grade 5 Result Chittagong BoardThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter