题解与讨论区 1166: 美味佳肴

题解与讨论区 1166: 美味佳肴

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 256 MB

返回问题页面

题目描述

众所周知,天才程序员菜哭武是一个伟大的厨师。这天,张老师和石头来到菜哭武家做客,想尝一尝菜哭武的手艺。
菜哭武手上有n种食材,每种食材个数无限多,编号为i的食材有一个美味度ai。一道菜中,每种编号的食材至多有一个,
而这道菜的美味度是这道菜包含的食材的美味度之和。
每次张老师会指定一个编号l, 石头会指定一个编号r(l <= r),然后菜哭武会在编号在[l, r]中的食材中选若干
种食材做菜。张老师和石头都是美食家,因此他们要求菜哭武依次做出美味度以1,2,3,4...这样依次加1递增的菜,
直到菜哭武用当前的食材无法做出美味度为x的菜。比如,某一个[l, r]中的食材的美味度依次为2, 1, 1, 1,7,那么
美味度为1, 2, 3, 4, 5的菜都是可以做出来的,而美味度为6的菜是无法做出来的,所以对于这对[l, r],x = 6。
张老师和石头一共会提出m个这样的[l, r]区间,对于每个区间,菜哭武想知道这个x是多少。

第1166题的题解

重型榴弹手

Newbie 的题解


先考虑只询问一次要怎么做:先从小到大排序,如果没有 1 答案就是 1;否则令 x=1x = 1,表示目前可以表示 [1..x1..x] 中的数。然后添加第二个数 yy,如果 y>x+1y > x + 1,那么最多只能表示到 xx,否则可以表示 [1..x+y1..x+y] 中的数。

于是可以找尽可能多的 yxy \le x,然后进行累加,这样 yy 的增长速率是指数的(更严格的说小于斐波那契数列的增长速率)。

对于多次询问,设初始 x=1x = 1,然后不断求区间内不超过 xx 的数的和 sumsum,再令 x=sum+1x = sum + 1,直到无法继续扩展。可以用可持久化值域线段树维护(值域 0 ~1e9,可持久化线段树动态开点,所以是存得下的)。

时间复杂度 O(nlog2n)O(nlog^2n)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define debug(x) cerr << #x << " = " << x << endl
  4. #define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  5. constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 9;
  6. struct SegTree {
  7. int lson, rson, sum;
  8. } tree[MAXN * 64];
  9. int& Lson(int root) { return tree[root].lson; }
  10. int& Rson(int root) { return tree[root].rson; }
  11. int newNode(int& root) { static int tot; return root = ++tot; }
  12. void modify(int pre, int root, int L, int R, int pos) {
  13. tree[root] = tree[pre];
  14. if (L == pos && R == pos) {
  15. tree[root].sum += pos; // 在 pos 处插入,总和加上 pos
  16. return;
  17. }
  18. int mid = (L + R) >> 1;
  19. if (pos <= mid) modify(Lson(pre), newNode(Lson(root)), L, mid, pos);
  20. else modify(Rson(pre), newNode(Rson(root)), mid + 1, R, pos);
  21. tree[root].sum = tree[Lson(root)].sum + tree[Rson(root)].sum;
  22. }
  23. int qSum(int pre, int root, int L, int R, int qL, int qR) { // 求值域 qL <= x <= qR 的 x 的和
  24. if (qL <= L && R <= qR) return tree[root].sum - tree[pre].sum;
  25. int mid = (L + R) >> 1, res = 0;
  26. if (qL <= mid) res += qSum(Lson(pre), Lson(root), L, mid, qL, qR);
  27. if (qR > mid) res += qSum(Rson(pre), Rson(root), mid + 1, R, qL, qR);
  28. return res;
  29. }
  30. int root[MAXN], n, m;
  31. int main() {
  32. boost;
  33. cin >> n;
  34. for (int i = 1, tmp; i <= n; i++) {
  35. cin >> tmp;
  36. modify(root[i - 1], newNode(root[i]), 0, 1e9, tmp);
  37. }
  38. cin >> m;
  39. for (int i = 1, l, r; i <= m; i++) {
  40. cin >> l >> r;
  41. int x = 1;
  42. while (true) {
  43. int sum = qSum(root[l - 1], root[r], 0, 1e9, 0, x); // 查询 <= x 的数的和
  44. if (sum < x) break;
  45. x = sum + 1;
  46. }
  47. cout << x << "\n";
  48. }
  49. return 0;
  50. }



点赞 1
举报