题解：AT_abc417_d [ABC417D] Takahashi Expectation

题意

给定个三元组，定义心情值为，需要按照到的顺序执行以下操作：

若，那么；
否则。

给定次查询，每次查询给定一个整数，要求求出初始心情值为时，最终的心情值。

。

思路

本场总结：E < D。

我们发现，如果，那么一定会减少到以下，且如果数据开满，那么心情值会在以内上下乱跳。而，所以我们可以预处理出到以内的从开始操作的答案。

接着考虑非常大的数如何转化为小数。我们发现，操作时，减少到以内的操作是一段前缀。而停止的条件是，也就是。而的最大值是。对于不同的数据，我们设这个最大值为，且对于一个的数，记其转化为小数后的结果为，且停止减少的第一轮操作是第轮。

转化为小数后，并不能直接按照从开始的答案计算。因为前面已经跳过了一些步骤，所以我们还需要处理出从给定的操作步骤开始的答案。

所以，我们将答案分为三段处理：

若，直接求解；
若，那么给挂上查询，其中表示当前的查询下标。
若，那么最后也无法减少到以内，直接输出即可。

但是，注意一点，如果我们直接处理出以内每个数从每一轮开始的答案，实际上是会超时的。因为此题答案不能反推，所以需要的时间来预处理，会超时。

所以，如前面部分所言，我们将操作离线，分为两个函数：

第一个用来处理和数组的值。
第二个用来离线处理查询。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 1e4 + 10, MAXV = 1e3 + 10, MAXQ = 5e5 + 10;

struct Query {
  int i, id;
};

struct Node {
  int p, a, b;
} a[MAXN];

int n, q, mx, sum;
int res[MAXV], ans[MAXQ];
pii val[MAXN * MAXV];
vector<Query> v[MAXN];
vector<int> r;

void change(int &k, int i) {
  k <= a[i].p ? k += a[i].a : k = max(0, k - a[i].b);
}

void init() { // 预处理
  // 时间复杂度 O(NV)
  for (int i = 1; i <= n; i++) {
    sum += a[i].b;
    for (int j = mx + 1; j <= sum + a[i].p; j++) {
      val[j] = {j - (sum - a[i].b), i};
    }
    mx = max(mx, sum + a[i].p);
  }
}

void solve() { // 求解答案
  // 时间复杂度 O(NV)
  for (int i = 0; i <= 1000; i++) {
    int k = i;
    for (int j = 1; j <= n; j++) {
      change(k, j);
    }
    res[i] = k;
    for (Query &x : v[i]) {
      int k = i;
      for (int j = x.i; j <= n; j++) {
        change(k, j);
      }
      ans[x.id] = k;
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].p >> a[i].a >> a[i].b;
  }
  init();
  cin >> q;
  r.assign(q + 5, 0);
  for (int i = 1; i <= q; i++) {
    cin >> r[i];
    // 将可以求解的大数据挂到小数据上做查询
    if (r[i] > 1000 && r[i] <= mx) {
      v[val[r[i]].first].push_back({val[r[i]].second, i});
    }
  }
  solve();
  // 离线查询
  for (int i = 1; i <= q; i++) {
    if (r[i] <= 1000) {
      ans[i] = res[r[i]];
    } else if (r[i] > mx) {
      ans[i] = r[i] - sum;
    }
    cout << ans[i] << '\n';
  }
  return 0;
}