---
title: '洛谷：P4552：IncDec Sequence'
url: 'https://rsywx.com/luogu/04552'
markdown: 'https://rsywx.com/luogu/04552.md'
date: '2026-10-01'
description: 'Table of contents: 题目 分析 答案 思考 …'
taxonomy:
  tag:
    - 差分
---

[  **Grav**  ](https://rsywx.com/) 

# 洛谷：P4552：IncDec Sequence

 Posted on 1st Oct 2026

 ![洛谷：P4552：IncDec Sequence](https://rsywx.com/images/f/7/f/5/a/f7f5a17855670c7b34aeb27e85fa781db8ed9272-solution.jpg "洛谷：P4552：IncDec Sequence")
[P4552：IncDec Sequence](https://www.luogu.com.cn/problem/P4552)

这也是一道差分题目，灵感来自题目中“每次可以选择一个区间\\(\[l,r\]\\)，使这个区间内的数都加1或者都减1”。

假定我们根据原始数据构造出了一个差分数组：

`[0号差分未使用] 1 3 -2 -3 2 0 1 -4`

我们显然是要最后得到一个`[0号差分未使用] 1 0 0 0 0...`的差分数组。其中第一个元素`1`不用变，因为按照差分数组的定义，`diff[1]=a[1]-a[0]=a[1]`。而从`[2]=3`开始的每个差分都需要变成0！由于每次都只能对原数据加1或者减1，所以：`3`需要3次减1操作，`-3`需要3次加1操作。正的diff有一个总的操作数量（`pos_sum`），负的diff也有一个总的操作数量（`neg_sum`）。但是，最终操作数量不是`pos_sum+neg_sum`。

我们可以自由选择操作的区间！按照差分增减的操作，对于`[l, r]`区间加1的操作是`[l]+1, [r+1]-1`，我们可以合理选择`r`的范围：

| diff | ? | -2 | 0 | +3 | 0 |
|---|---|---|---|---|---|
| 位置 | 1 | 2 | 3 | 4 | 5 |

我们一定可以选择`[2,4)`这个范围，都+1，而`[4]`这个位置-1。所以，+1和-1的操作可以配对。只有多出来的`|pos_num-neg_sum|`是需要单个处理的，因此操作次数是\\(max(pos\\\_num, neg\\\_num)\\)。

回头来看结果的可能数量。按照上述的差分表格，我们最终得到的是一个`diff[1], 0, 0, .... 0`的差分数组。它保证所有的数字都是一样的。因此有几种答案，取决于`diff[1]`可以有怎样的取值范围。我们有\\(min(pos\\\_sum, neg\\\_sum)\\)次操作是互相抵消的。而多出来次数的操作，可以一次都不包括`diff[1]`，也可以每次都包括`diff[1]`，所以`diff[1]`的取值范围从`0`到`abs(pos_num-neg_num)`，也就是\\(abs(pos\\\_sum-neg\\\_sum)+1\\)。

一道看似的模拟题，最后用数学公式进行了优美的解答！

![Solution](https://rsywx.com/user/pages/32.luogu/04552/solution.jpg)

这道题目提示我们，善于分析，找出公式，可能是解题的正确思路——当然，不是所有的题目都能如此！

   [差分](https://rsywx.com/tag:%E5%B7%AE%E5%88%86 "See other posts in 差分")

- 
- 
- 
- 

 [ Previous](https://rsywx.com/luogu/04447) [Next ](https://rsywx.com/luogu/04653)

---

## Navigation

- Parent: [洛谷练习](https://rsywx.com/luogu.md)
- Previous: [洛谷：P4447：分组](https://rsywx.com/luogu/04447.md)
- Next: [洛谷：P4653：Sure Bet](https://rsywx.com/luogu/04653.md)
