题解：AT_abc417_d [ABC417D] Takahashi's Expectation

题目翻译：给定 $n$ 次操作，每次操作会给定三个正整数 $P_i,A_i,B_i$，假设将要操作的数为 $x$，则：

• 如果 $x\le P_i$，则将 $x$ 的值加上 $A_i$。
• 如果 $x\gt P_i$，则将 $x$ 的值减去 $B_i$。

给定 $q$ 次询问，每次询问给定一个正整数 $X_i$，问经过这些操作后 $X_i$ 的值为多少。

注意到 $P_i,A_i,B_i$ 都很小，所以考虑从这里下手。

根据题意发现较大的 $X_i$ 会一直执行减 $B_i$ 的操作，所以考虑二分求出第一个使 $X_i\lt 500$ 的操作的位置和经过这些操作后 $X_i$ 的值。

然后我们枚举每个数在经过后面的若干次操作后最终变成什么，然后将 $X_i$ 一个一个带入即可。注意经过操作后的数可能到达 $1000$，所以应该枚举到 $1000$。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
struct Queries{//转离线
	int val, first, id;//经过前 first 个操作后的 X_i 为 val
	bool operator < (const Queries &b) const{
		if(first == b.first) return val < b.val;
		return first > b.first;
	}
}q[500005];
int a[100005], b[100005], c[100005];
int pre[100005];//前缀和，方便二分
int ans[500005];
int cur[1005], fin[1005];//滚动数组，节省空间
int n, m;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
	for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i];//前缀和
	cin >> m;
	for(int i = 1; i <= m; i++){
		cin >> q[i].val;
		q[i].id = i;
		int idx = upper_bound(pre + 1, pre + n + 1, q[i].val - 500) - pre - 1;//二分查询第一个使 X_i<=500 的操作
		q[i].first = idx + 1, q[i].val -= pre[idx];//直接执行这些操作
		if(idx >= n) ans[i] = q[i].val;//如果没有直接写答案
	}
	sort(q + 1, q + m + 1);
	for(int i = 1; i <= 1000; i++){
		cur[i] = i;
		fin[i] = i;
	}
	int l = 1;
	for(int i = n; i >= 1; i--){
		for(int j = 0; j <= 1000; j++){
			if(j <= a[i]) cur[j] = fin[j + b[i]];//计算每个数后i次操作的值
			else cur[j] = fin[max(0ll, j - c[i])];
		}
		for(int j = 0; j <= 1000; j++){
			fin[j] = cur[j];//滚动数组
		}
		while(l <= m && q[l].first > i) l++;
		while(l <= m && q[l].first == i) ans[q[l].id] = fin[q[l].val], l++;//双指针获取答案
	}
	for(int i = 1; i <= m; i++){
		cout << ans[i] << '\n';
	}

	return 0;
}

时间复杂度：$O(nV+q\log q)$，其中 $V=1000$。