[LibreOJ 2174][FJOI2016]神秘数 & [CC]FRBSUM

danihao123 posted @ 2018年3月12日 08:58 in 题解 with tags loj CodeChef FJOI 主席树 , 582 阅读
转载请注明出处:http://danihao123.is-programmer.com/

震惊!省选惊现CodeChef原题……竟然是为了……出原题难道不是普遍现象吗

这个题的思想肥肠喵啊(我膜了很长时间题解才看懂)……我争取给各位读者讲懂。

首先对于最后的答案\(x + 1\),一定说明\([1, x]\)都会被凑出来。那么我们可以考虑去维护这个前缀区间。

考虑把数从小到大加入。假设当前我们的可凑出来的前缀区间是\([1, r]\),那么加入一个数\(x\),如果说\(x > r + 1\),那么把之前所有可能的子集和都加上这个\(x\),一定凑不出来\(r + 1\)。并且这之后加入的数会越来越大,那个\(r\)不会再变大了,所以那个\(r\)就是答案了。

如果说\(x\leq r + 1\)呢?那么把前缀区间的每个数加上\(x\)都是可凑成数。所以前缀区间会变成\([1, r + x]\)。

然后观察出来这种性质之后,我们发现我们要考虑区间中不同的数,可以考虑主席树。我们建立一排主席树,对于查询\([L, R]\),不妨假设当前的前缀区间是\([1, r]\),然后考虑将其扩大。首先再加上大于\(r + 1\)的数是对扩大\(r\)没有意义的,所以我们就考虑在\([L, R]\)中找到所有权值处于\([1, r + 1]\)的数字的和(主席树可以派上用场),这样就是一个新的答案了。如果发现转移过去之后答案没有变大,那么以后也不会变大了,跳出来即可。

考虑分析一波复杂度。对于每一个\(r\),转移到更大的\(r\)会让他至少加上\(r + 1\),所以转移的次数是\(\log_2 s\)(这里假设\(s\)是所有数的和),然后每次一次转移的复杂度是\(\log_2 n\),所以单次查询复杂度可以大致认为是\(\log^2 n\)。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 100005;
const int maxsiz = maxn * 40;
ll sumv[maxsiz]; int tot = 0;
int lc[maxsiz], rc[maxsiz];
int build_tree(int L, int R) {
  int ret = ++ tot;
  if(L < R) {
    int M = (L + R) / 2;
    lc[ret] = build_tree(L, M);
    rc[ret] = build_tree(M + 1, R);
  }
  return ret;
}
int update(int o, int L, int R, int p, int v) {
  int ret = ++ tot;
  sumv[ret] = sumv[o] + (ll(v));
  lc[ret] = lc[o], rc[ret] = rc[o];
  if(L < R) {
    int M = (L + R) / 2;
    if(p <= M) {
      lc[ret] = update(lc[ret], L, M, p, v);
    } else {
      rc[ret] = update(rc[ret], M + 1, R, p, v);
    }
  }
  return ret;
}
ll query(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return sumv[o];
  } else {
    int M = (L + R) / 2;
    ll ans = 0;
    if(ql <= M) ans += query(lc[o], L, M, ql, qr);
    if(qr > M) ans += query(rc[o], M + 1, R, ql, qr);
    return ans;
  }
}

int n;
ll A[maxn], A2[maxn];
int cnt;
void discretiz() {
  std::sort(A2 + 1, A2 + n + 1);
  cnt = std::unique(A2 + 1, A2 + 1 + n) - A2 - 1;
}
int get_p(ll v) {
  int ret = (std::lower_bound(A2 + 1, A2 + 1 + cnt, v) - A2);
  if(A2[ret] > v) ret --;
  return ret;
}

int T[maxn];
void init_tree() {
  T[0] = build_tree(1, cnt);
  for(int i = 1; i <= n; i ++) {
    T[i] = update(T[i - 1], 1, cnt, get_p(A[i]), A[i]);
  }
}
const ll INF = 1000000000LL;
ll calc_sum(int l, int r, int typ) {
  if(typ == 0) return 0LL;
  return query(T[r], 1, cnt, 1, typ) - query(T[l - 1], 1, cnt, 1, typ);
}
ll calc(int l, int r) {
  ll maxv = 0LL, R = 1LL;
  maxv = calc_sum(l, r, get_p(R));
  while(maxv >= R && R < INF) {
    R = std::min(maxv + 1LL, INF);
    maxv = calc_sum(l, r, get_p(R));
  }
  return maxv + 1LL;
}
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]); A2[i] = A[i];
  }
  discretiz(); init_tree();
  int q; scanf("%d", &q);
  while(q --) {
    int l, r; scanf("%d%d", &l, &r);
    printf("%lld\n", calc(l, r));
  }
  return 0;
}
PSC Result 2022 dhak 说:
Aug 30, 2022 01:12:14 AM

Minister of Education, Bangladesh Mr. Nahid Hasan has announced this year PSC Result 2022 will be announced in the last week of December 2022 with the total or full mark sheet of the Primary School Certificate Exam, PSC Result 2022 dhaka Board based on previous years schedule, once the official date is confirmed we will update here with timings.Previously this Prathomik Somaponi Result 2022 was announced on 30th or 31st December, and this year also announced same for the class 5th grade result with merit or toppers list asper regular GPA Marking schedule, and Directorate of Primary Education (DPE) has announced this year is very tough to conduct evaluation process to announce subject wise marks for Grade 5 terminal exams.


登录 *


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