P4552 IncDec Sequence

很有意思的一道题，震惊，差分数组居然还能这么用！
难度：普及+/提高
题目

思路

先来看第一问，

要求序列中所有数都一样的最小操作次数，

把问题转化一下，其实就是使得差分数组除了第一项之外都变成0，

为什么除了第一项呢？

因为根据差分数组的定义，第一项就是第一个数，所以不必是0。

看下区间操作，对于$[l,r]$这段区间：

• 加法： d[l]+=x,d[r+1]-=x
• 减法： d[l]-=x,d[r+1]+=x

$d$数组代表差分数组，$d_i=a_i-a_{i-1}$。

$x$在本题中等于一。

所以要想要让差分数组除了第一位都变成0，那么最赚的操作便是让一个正数$-1$让一个负数$+1$，这样接近0的效率是最大的。

那么能配对的正负数都用完了以后，剩下的就只能和第一位操作了。

所以总操作数便是$\max(p,q)$，这里p代表差分数组正数绝对值之和，q代表差分数组负数绝对值之和。

---

第二问，由于最后剩下了一些无法配对的落单的数，所以它们只能与区间右端点或者左端点配对，所以要么就是r[n+1]+=x要么就是l[1]+=x（要么就是更改左端点，要么就是更改右端点）。

假如一开始全部修改左端点，设这个修改次数为$x$，这是一种修改方法。

那么我也可以左边修改$x-1$次，右边修改$1$次，这也是一种修改方法。

这样枚举下去，我们发现一共有$x+1$种修改方法，也就是有$x+1$种序列。

$x=abs(p-q)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
ll a[N],d[N];
ll p,q;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(i==1)
            continue;
        d[i]=a[i]-a[i-1];
        if(d[i]>0) p+=d[i];
        else q-=d[i];
    }
    printf("%lld\n%lld",max(p,q),abs(p-q)+1);
    return 0;
}