[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