题目传送门
题目给的定义 \(f_j = \Big|\sum\limits_{i=1}^{n}(-1)^{i-1}\times(a_i - b_{i+j})\Big|\)，题目要求求 \(f_j\) 的最小值。
这个式子我们拆一下。如果不考虑绝对值的话，就可以拆成
\[\sum\limits_{i=1}^{n}(-1)^{i-1}\times a_i - \sum\limits_{i=1}^{n}(-1)^{i-1}\times b_{i+j}
\]
把负号转为正号，就变成了
\[\sum\limits_{i=1}^{n}(-1)^{i-1}\times a_i + \sum\limits_{i=1}^{n}(-1)^i\times b_{i+j}
\]
可以看出前半部分不随 \(j\) 的变化而变化，右半部分 \(b\) 数组不因为询问而改变，可以预处理所有可能的 \(j\) 时右边式子的值。这里可以用前缀和来实现。
左边的初始答案也可以预处理算出来。右边可以预处理得到必须减去 \(m - n + 1\) 个数的一个，要求减去后答案绝对值最小。我们不妨将这 \(m - n + 1\) 个数排序，设左边初始答案为 \(ans\)，那么只需要在这些数里面查询最接近 \(-ans\) 的数就行了。可以用二分来解决该问题。（细节：如果和我一样直接用 \(\text{lower}\_\text{bound}\) 函数的话，要注意有些数是相同的，返回的值两边都不一定是最优答案，只需要再调用一次 \(\text{upper}\_\text{bound}\) 就行了。）
修改时对答案的贡献也是好算的。如果修改的长度是偶数，那么正负抵消，所以左半部分答案和原先一样；否则，判断端点是够作正贡献。如果是，那么左半部分答案为之前答案加上 \(x\)；否则为之前答案减去 \(x\)。然后每次操作后再二分查找答案就行了。
Code
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int t,n,m,A,B,k,q;
int a[200005],b[200005],c[200005],cnt,sum[200005],ans,l,r,cd;
int get_min(int x)//二分查找右半部分取下标x附近时的最小答案
{int p = 1e18;if(x > 1 && abs(c[x - 1] + ans) < abs(p))p = abs(c[x - 1] + ans);if(abs(c[x] + ans) < abs(p))p = abs(c[x] + ans);if(x < cnt && abs(c[x + 1] + ans) < abs(p))p = abs(c[x + 1] + ans);return p;
}
signed main()
{cin >> n >> m >> q;for(int i = 1;i <= n;i ++){cin >> a[i];if(i % 2)ans += a[i];else ans -= a[i];}for(int i = 1;i <= m;i ++){cin >> b[i];if(i % 2)sum[i] = sum[i - 1] - b[i];//前缀和else sum[i] = sum[i - 1] + b[i];}for(int i = n;i <= m;i ++)//计算出备选的右半贡献{if((n - i + 1) % 2)c[++cnt] = sum[i] - sum[i - n];else c[++cnt] = - sum[i] + sum[i - n];}sort(c + 1,c + cnt + 1);c[0] = c[cnt + 1] = 1e18;int ds = lower_bound(c + 1,c + cnt + 1,- ans) - c;int dt = upper_bound(c + 1,c + cnt + 1,- ans) - c;cout << min(get_min(ds),get_min(dt)) << '\n';for(int i = 1;i <= q;i ++){cin >> l >> r >> cd;if((r - l + 1) % 2)//操作{if(l % 2)ans += cd;else ans -= cd;}int ds = lower_bound(c + 1,c + cnt + 1,- ans) - c;int dt = upper_bound(c + 1,c + cnt + 1,- ans) - c;cout << min(get_min(ds),get_min(dt)) << '\n';}
}