CodeForces CF862E题解

\(Part\ 1:\)

我们发现每次修改动的是\(a\)串，所以对于这个答案的公式，\(b_{i+j}\)的部分是可以求出来的。所以我们可以把公式改成如下所示：

\(f(j)=|\sum_{i=1}^{n}\ (-1)^i*b_{i+j}+\sum_{i=1}^{n}\ (-1)^{i-1}*a_{i}|\)，\(0\le j\le m-n\)。

第一部分可以预处理。

在预处理的过程中我们不管绝对值，也就是会出现负数，这一点很重要的。

但是呢，我们发现对于不同的\(j\)，每一个\(i+j\)的奇偶性是不一样的，所以我们不能心安理得的算出来就完事了。

我们不妨设第一个\(j\)是偶数，我们用一个前缀和数组\(sum\)，其中\(sum_i\)表示当\(j\)为偶数的时候\(b\)的前缀和。

计算方法\(:\)

for(int i=1;i<=m;i++) if(i&1) b[i]=-b[i];
for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];

然后我们计算第一轮的答案，也就是我们先把不经过更改的\(a\)数组的答案计算出来，然后得出第一轮的答案，先把第一轮整个\(ans\)数组求出来。

之后呢，因为题目问的是最小值，所以我们要找出距离\(0\)最近的\(f_j\)，输出这个最小值即可。

\(Part\ 2:\)

前面我们说过了如何处理第一轮的答案。

接下来我们看如何应付修改。

最开始是想用线段树维护一下，毕竟区间修改嘛。但是后来发现维护绝对值的时候特别麻烦，会影响到正确性，所以我们重新考虑。

我们发现，这个每次对\(a\)数组的修改是全局性的，也就是说，如果当前这个\(a_i\)匹配到的是\(-1\)的奇数次方，那么就是\(-a_i\)，每次加上\(d\)的话对答案的更新贡献就变成了\(-d\)。同理，如果匹配到的是\(-1\)的偶数次方，那么对答案的更新贡献就是\(+d\)。然后我们发现这个事情特别爽，因为相邻两个位是可以相互抵消的。但是呢，我们这里特别需要处理的就是\(l,r\)奇偶性相同的问题。

\(i.\)如果\(l\%2==r\%2==0\)，那么两边的数字都是偶数，我们最后一定会多出来一个孤零零的\(-d\)。

\(ii.\)如果\(l\%2==r\%2==1\)，那么两边的数字都是奇数，最后一定会多出来一个孤零零的\(+d\)。

然后我们再记录一个偏移量\(shift\)，表示每次更新答案的情况，例如某次\(update\)多出来一个\(-d\)，我们的\(shift-=d\)。这个\(shift\)记录的相当于一个前缀和，所以每次都把答案加上\(shift\)。

\(Code:\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,q,ans;
int a[N],b[N],sum[N],f[N];
int read()
{
    int x=0,f=1;
    char c=getchar();
    while (c<‘0‘||c>‘9‘)
    {
        if(c==‘-‘) f=-1;
        c=getchar();
    }
    while (c>=‘0‘&&c<=‘9‘)
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
int higher(int x)
{
    int l=0,r=m-n,mid,cnt=0x3f3f3f3f3f3f3f3f;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if(x<f[mid]+ans) cnt=mid,r=mid-1;
        else l=mid+1;
    }
    if(cnt==0x3f3f3f3f3f3f3f3f) return cnt;
    return f[cnt];
}
int lower(int x)
{
    int l=0,r=m-n,mid,cnt=0x3f3f3f3f3f3f3f3f;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if(x>=f[mid]+ans) cnt=mid,l=mid+1;
        else r=mid-1;
    }
    if(cnt==0x3f3f3f3f3f3f3f3f) return cnt;
    return f[cnt];
}
signed main()
{
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) b[i]=read();
    for(int i=1;i<=m;i++) if(i&1) b[i]=-b[i];
    for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];
    for(int i=1;i<=n;i++) {if(i%2) ans+=a[i];else ans-=a[i];}
    for(int i=0;i<=m-n;i++)
    {
        if(!(i%2)) f[i]=ans+sum[n+i]-sum[i];
        else f[i]=ans+sum[i]-sum[n+i];
    }
    sort(f,f+m-n+1);
    ans=0;
    cout<<min(abs(higher(0)),abs(lower(0)))<<endl;
    while (q--)
    {
        int l=read(),r=read(),d=read();
        if((l&1) && (r&1)) ans+=d;
        if(!(l&1) && !(r&1)) ans-=d;
        cout<<min(abs(higher(0)+ans),abs(lower(0)+ans))<<endl;
    }
    return 0;
}

CodeForces CF862E题解

原文：https://www.cnblogs.com/juruo-wsy/p/14623319.html