[ARC119C] ARC Wrecker 2 题解

题目链接：[ARC119C] ARC Wrecker 2

题意：

在 AtCoder 街道上有 $N$ 座建筑物，从西到东编号为 $1$ 到 $N$。初始时，建筑物 $1, 2, \ldots, N$ 的高度分别为 $A_1, A_2, \ldots, A_N$。

cxy 是 ARC Wrecker 公司的总裁，她计划选择整数 $l$ 和 $r$ $(1 \leq l < r \leq N)$，并使得建筑物 $l, l+1, \ldots, r$ 的高度全部变为 $0$。为了达成这个目标，她可以任意次数任意顺序地使用以下两种操作：

1. 设置一个整数 $x$ $(l \leq x \leq r-1)$ 并使得建筑物 $x$ 和 $x+1$ 的高度各增加 $1$。
2. 设置一个整数 $x$ $(l \leq x \leq r-1)$ 并使得建筑物 $x$ 和 $x+1$ 的高度各减少 $1$。这种操作仅当这两座建筑物的高度都大于等于 $1$ 时才能进行。

请注意，$x$ 的范围取决于 $(l,r)$。

有多少种 $(l,r)$ 的选择可以让 cxy 实现她的计划？

数据范围：

$2 \leq N \leq 3\times 10^5,~1 \leq A_i \leq 10^9$

这个消数值的属于是经典题了。经典题就经典在每次你看到相似的都不会

容易发现同奇偶性的数可以相互传递数值，而单个修改的操作是同时抵消奇偶性不同的两个数。

因此我们可以得到一个结论，一段区间如果可以被删光，则奇数位的和与偶数位的和相等。

显然这个只需要把偶数位乘以 $-1$ 就可以转化为「区间和为 $0$ 」了，考虑前缀和处理。

一段区间 $[l,r]$ 合法当且仅当 $S_{l-1} = S_r$ ，然后就是简单的组合计数问题了

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,sum,res;
unordered_map<int,int> mp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; mp[0] = 1;
    for(int i = 1, x; i <= n; i++)
    {
        cin >> x; sum += x * ((i & 1) ? 1 : -1);
        res += mp[sum]; ++mp[sum];
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/back-to-you/Solutions-arc119c