摊还算法——贡献转移

在计算每个元素的作用的时候&＃xff0c;我们可以通过反向枚举作用效果&＃xff0c;添加到作用元素的身上&＃xff0c;这种方法叫做贡献转移。更正式的说&＃xff0c;设aia_iai​为每个元素的作用数&＃xff0c;集合$B$为作用效果&＃xff0c;那么&＃xff1a;

ai&＃61;∑b∈B,b→ai1a_i &＃61; \sum_{b \in B,b \to a_i} 1 ai​&＃61;b∈B,b→ai​∑​1

例题

LeetCode 5874

考虑每一个位置的 pivot &＃xff0c;如果$i$位置能够成为 pivot 的话&＃xff0c;那么前后肯定存在一个位置$j$&＃xff0c;将位置$j$变成$k$之后&＃xff0c;该位置的 pivot 成立&＃xff0c;那么我们称$j$位置对$i$位置有一个贡献&＃xff0c;此时我们可以用哈希表去记录$j$位置的数字&＃xff0c;然后在遍历中进行贡献转移即可。

class Solution
{
public:int waysToPartition(vector<int> &nums, int k){long long lsum &＃61; 0;long long rsum &＃61; accumulate(nums.begin(), nums.end(), 0ll);unordered_map<long long, int> mp;vector<int> contrib(nums.size());int undo &＃61; 0;for (int i &＃61; 0; i < nums.size(); i&＃43;&＃43;){contrib[i] &＃43;&＃61; mp[nums[i]];if (i !&＃61; nums.size() - 1){lsum &＃43;&＃61; nums[i];rsum -&＃61; nums[i];if (rsum &＃61;&＃61; lsum){undo&＃43;&＃43;;}mp[rsum - lsum &＃43; k]&＃43;&＃43;;}}mp.clear();lsum &＃61; accumulate(nums.begin(), nums.end(), 0ll);rsum &＃61; 0;for (int i &＃61; nums.size() - 1; i >&＃61; 0; i--){contrib[i] &＃43;&＃61; mp[nums[i]];if (i !&＃61; 0){lsum -&＃61; nums[i];rsum &＃43;&＃61; nums[i];mp[lsum - rsum &＃43; k]&＃43;&＃43;;}}for (int i &＃61; 0; i < nums.size(); i&＃43;&＃43;){undo &＃61; max(undo, contrib[i]);}return undo;}
};


CF 1603C

我们可以枚举以$x$结尾&＃xff0c;前驱为ai&＃43;1a_i &＃43; 1ai​&＃43;1的⌈aiai&＃43;1⌉−1\lceil \frac{a_i}{a_i &＃43; 1} \rceil - 1⌈ai​&＃43;1ai​​⌉−1贡献。设$dp[i][x]$表示为子数组$a[i:j]$最终以$x$结尾的子数组的数量&＃xff0c;那么前面有$i$个开头的子数组会得到这个贡献。即为i∗dp[i][x]∗(⌈aix⌉−1)i * dp[i][x] * (\lceil \frac{a_i}{x} \rceil - 1)i∗dp[i][x]∗(⌈xai​​⌉−1)。


int arr[100005];
int dp[2][100005];
vector<int> hold[2];
void solve()
{int n;scanf("%d", &n);for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)scanf("%d", arr &＃43; i);ll ans &＃61; 0;hold[0].clear();hold[1].clear();for (int i &＃61; n; i >&＃61; 1; i--){dp[i & 1][arr[i]]&＃43;&＃43;;hold[i & 1].push_back(arr[i]);int las &＃61; arr[i];for (int x : hold[(i &＃43; 1) & 1]){int pos &＃61; arr[i] / ((arr[i] &＃43; x - 1) / x);ll cnt &＃61; dp[(i &＃43; 1) & 1][x];dp[i & 1][pos] &＃43;&＃61; cnt;if (pos !&＃61; las){hold[i & 1].push_back(pos);las &＃61; pos;}ans &＃61; (ans &＃43; (i * ((cnt * (((arr[i] &＃43; x - 1) / x) - 1)) % MOD353)) % MOD353) % MOD353;}for (int k : hold[(i &＃43; 1) & 1])dp[(i &＃43; 1) & 1][k] &＃61; 0;hold[(i &＃43; 1) & 1].clear();}for (int k : hold[0])dp[0][k] &＃61; 0;for (int k : hold[1])dp[1][k] &＃61; 0;cout << ans << endl;
}