ARC119C ARC Wrecker 2 题解

link T1です

定义“编辑”为选择数组中相邻的两个数同加或同减。

给定一个长度为 $n$ 的数组 $a$，你想统计有多少个 $a$ 的子序列满足可以通过若干次“编辑”，途中所有值在任意时刻不能为负，最终子序列内所有元素均为 $0$。

（注意是子序列，即你不能一个数在外面一个数在里面来单点修改子序列）

---

先不考虑同加。考虑什么样的情况是可以的。

一个很直接的想法是从左往右消，如果说有某个值与后面产生了脱离，这样就是不可以的。

比如说

4 5 13 3 5

先把 $a_1,a_2$ 消掉 $4$ ，此时变为 0 1 13 3 5，

把 $a_2,a_3$ 消掉 $1$，此时变为 0 0 12 3 5，

最后把 $a_3,a_4$ 消掉 $3$，此时变为 0 0 9 0 5，而这个 $9$ 是无法与后面接壤的。

我们考虑怎么样维护这个东西。

可以发现，在 $a_{i-1},a_i$ 消去之后，$a_i'\leftarrow a_i-a_{i-1}'$。这相当于一个全局的 $\times (-1)$ 和 $+a_i$ 操作。

那么我们就可以使用一个 multiset 维护这个东西。

扫一遍整个数组。边扫边将新的初始值添加进去。

一旦出现负数，就说明了出现了无法接壤的情况。比如 12 3 会强制算为 0 -9 。只需要 lower_bound 一下分界点舍弃掉这种情况即可。

如果要统计答案，直接使用 count(a[i+1]) 即可。即最后两个相同的可以直接消去，这是合法的情况。

---

那么我们现在考虑同加。

还是以 0 0 9 0 5 为例。我们可以将 0 5 加上 $9$，这样子就可以使得 9 9 消掉了，留下一个 14。

这种情况怎么表示呢？原来的值是 (0 0) 12 3 5

给 0 5 加上 $9$ 事实上是给 $3$ 加 $9$ 变成 $12$。

由于 $9=a_3'-a_4$，因此 $a_5'=a_5+9=a_5+(a_3'-a_4)=a_5-(a_4-a_3')=a_5-a_4'$，与之前的 $a_i'\leftarrow a_i-a_{i-1}'$ 并无区别。

因此在有了同加后就不需要考虑无法接壤的情况了。还更简单了呢。

---

小细节：multiset.count() 的复杂度为 count 的数量。建议使用 map 或 umap。

代码：

unordered_map<ll,int> tot;
int tf=1;
ll delta;
//这里全局操作 化为了两个变量。tf代表此时 a_i 加入的符号。delta是带了符号的
//下面是原值x与map内引用值y的转换关系
//(y+delta)*tf=x
//x*tf-delta=y
ll ans;
void solve(){
	tot[a[1]]=1;
	for(int i=2;i<=n;++i){
		ll y=a[i]*tf-delta;
		if(tot.count(y)) ans+=tot[y];

		tf*=-1;
		delta+=a[i]*tf;
		y=a[i]*tf-delta;
		if(tot.count(y)) ++tot[y];
		else tot[y]=1;
	}
}

象征性给出一个毫无必要的链接