Codeforces #755 Div1 : C. Game with Stones

これは割とすんなり解けているな。
https://codeforces.com/contest/1588/problem/C

問題

非負整数列に対し、隣接する2要素を選んでデクリメントすることを繰り返し、全要素0にできる場合、その数列を良い数列と呼ぶことにする。

整数列Aが与えられるので、そのうち部分列が良い数列であるものは何通りか。

解法

f(n) := A[n]-A[n-1]+A[n-2]-...と交互に符号を取ったprefix sum
とする。
A[L...R]が良い数列である条件は、以下をいずれも満たす場合である。

• f(R)=f(L-1)
• L-1とパリティが一致するnのうちf(n)＜f(L-1)であるが区間[L,R]に含まれない物

後者の条件はSegTreeを二分探索することで、L以上最小のnを求められる。
あとはf(n)を値毎にindexを列挙した数列を二分探索すれば、f(R)=f(L-1)となるRの個数を求められる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1LL<<60;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll,1<<19> up,down;


int T,N;
int A[303030];
ll S[303030];
map<ll,vector<int>> M;
void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>T;
	while(T--) {
		cin>>N;
		M.clear();
		M[0].push_back(0);
		
		FOR(i,N) {
			cin>>A[i];
			S[i+1]=S[i];
			if(i%2==0) {
				S[i+1]+=A[i];
				up.update(i+1,S[i+1]);
			}
			else {
				S[i+1]-=A[i];
				down.update(i+1,-S[i+1]);
			}
			M[S[i+1]].push_back(i+1);
		}
		ll ret=0;
		FOR(i,N) {
			int R=i,R2=i;
			
			for(j=19;j>=0;j--) {
				if(R+(1<<j)<=N) {
					if(up.getval(i,R+(1<<j)+1)>=S[i]) R+=1<<j;
				}
				if(R2+(1<<j)<=N) {
					if(down.getval(i,R2+(1<<j)+1)>=-S[i]) R2+=1<<j;
				}
			}
			R=min(R,R2);
			vector<int>& V=M[S[i]];
			ret+=lower_bound(ALL(V),R+1)-lower_bound(ALL(V),i+1);
		}
		cout<<ret<<endl;
	}
	
}

まとめ

1500ptのCの割にはわりとさっくり解いたな。