增减序列

题目描述：

给定一个长度为n的序列，每次都可以选一个区间(l,r)，使得a[l],a[l+1],...,a[r]的元素同时加1或者减1，问最少操作多少次可以使得n个数字都相同，且在保证操作次数最少的情况下，存在多少个不同的结果序列

思路：

对一个区间的元素同时进行+1或-1，这可以通过差分来实现

所以我们可以先求出一个差分数组$d[i]$, $d[1]=a[1],d[2]=a[2]-a[1],...,d[n]=a[n]-a[n-1]$

则选择区间(l,r)进行+x的操作，就变成对 $d[l]+=x,d[r+1]-=x$，x = 1或-1

题目的要求是使得所有元素都相等，即使得差分数组d[2] = d[3] = ... = d[n] = 0,

• 所以我们优先考虑使用合理的操作来中和差分数组的正负数，比如对于d[l]>0, d[r+1]<0的情况让d[l]-=1,d[r+1]+=1

• 当差分数组仅剩下正数或者负数的时候，就只能通过下面的方法单独消除：

  比如只剩下正数，假设d[i]>0

  • 方法一：让d[1]+=1, d[i]-=1
  • 方法二：让d[i] += (-1), d[n+1] -= (-1)

  负数也类似，可以发现，这种方法每次只能消除一个1或者-1，假设差分数组中正数的和计作zheng,负数的和的绝对值计作fu，则最小操作次数是 $mac(zheng,fu)$

那在操作次数最小的情况下，能存在多少种不同的序列呢？

由于差分数组求前缀和后就是原数组，而差分数组的后n-1个数字都是0，所以求前缀和后序列的每个数字都是d[1],即代表不同序列的数量取决于d[1]可以存在多少不同的值

我们通过中和正负数的时候，修改的下标都是从2开始的，不会影响到d[1]，真正可以影响到d[1]的只有单纯操作正数或者负数的情况，显然需要操作的次数就是abs(zheng-fu),即数量差的绝对值

拿上面讨论的处理正数的方法分析，每次操作都有两种能满足条件的，但只有方法一是会修改d[1]的值，方法二是不会修改的，所以d[1]的值可能有abs(zheng-fu)+1种情况，这就是答案

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define m_p(a, b) make_pair(a, b)
typedef long long ll;
typedef pair<int, int> pii;
#define MAX 100005
#define mod 1000000007
int n, m, x, k, y, r;
int tr[MAX];

void work(){
	cin >> n;
	for(int i = 1; i <= n; ++i)cin >> tr[i];
	ll x = 0, y = 0;
	for(int i = n; i >= 2; --i){
		tr[i] -= tr[i-1];
		if(tr[i] > 0)x += tr[i];
		else y -= tr[i];
	}
	cout << max(x, y) << endl << abs(x-y) + 1 << endl;
}

int main(){
	io;
	work();
	return 0;
}