danihao123's Blog

震惊！省选惊现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;
}

根据Matrix-Tree定理，这题可以求出基尔霍夫矩阵，然后当成行列式求值即可

这样做并没有什么错，大概也能AC，但是时间复杂度是立方级的，并且写起来并不简单（要用到高斯消元什么的，更何况此题还要用高精度）

或许DP也可以？

不过有一个简单的递推式：d[n]=d[n-1]*3-d[n-2]+2

证明比较麻烦（绝大多数人是找规律出来的），可以到这找：http://vfleaking.blog.163.com/blog/static/17480763420119685112649

这题要用高精也太烦人了，我就用了Python写（Python语法真特么烦人啊）

Q：真要考试你交Python啊？

A：我用Python打出来表然后交表啊。

代码：