20261023

VP:ARC189 (Division 2)

A - Reversi 2

注意观察，首先首位是 0，末位得相同，其余肯定是一个 $[10...01]$ 或者 $[01...10]$ 的结构，然后考虑内部的修改次数。

再次注意发现，可以直接看相等或不相等的新序列 $B_i = (A_i + A_{i+1}) \mod{2}$

新操作就等价于在 $B$ 里选择， $[10...01]$ 的部分，把两端变成 $0$。

起始的序列是全 $1$ 的

以此来考虑所需要修改的区间长度，然后乘以一个选点顺序即可，

因为，不相邻的连续 0 列，不会产生影响

B - Minimize Sum

推式子，可以发现奇偶之间贡献是不成链的

D - Takahashi is Slime

考虑每个点往外扩展，暴力搜即可

  void solve() {
  	ll N; rd(N);
  	V<ll> A(N); rd(A);
  	V<ll> pre(N + 1, 0);
  	rep(i, N) pre[i + 1] = pre[i] + A[i];
  	debug(A); debug(pre);
  	Segtree<S, op> segt(A, e());

  	rep(i, N) {
  		ll l = i, r = i + 1;
  		ll ans = 0;
  		while(1) {
  			target = pre[r] - pre[l];
  			l = segt.min_left(l, f);
  			r = segt.max_right(r, f);
  			bool ok = 0;
  			if(l != 0 && A[l - 1] < pre[r] - pre[l]) -- l, ok = 1;
  			if(r != N && A[r] < pre[r] - pre[l]) ++ r, ok = 1;
  			if(!ok) break;
  		}
  		wtN(pre[r] - pre[l], "");
  	}

  }