AGC002

A Range Product

不会，弃疗了/kk

照题意模拟。

如果有相邻两个\(a\)之和\(\ge L\)就可以一直切到这里然后切掉它们中间，否则不行。

二分一下，然后要算一个点搜出去，只搜边\(\leq z\)的点数，直接上K算法重构树= =

神仙题Orz

首先降序\(a\)，然后题意变成了，一个不规则的图形从\((0,0)\)开始走走到边界的人输。

图形的样子大概是高度依次为\(a_1,a_2,\ldots,a_n\)的柱子。

证明一下除了边界，\(f_{x,y}=f_{x-1,y-1}\)

如果\(f_{x,y}=0\)即先手必败，那么在\((x-1,y-1)\)时不管先手怎么走后手都可以走到\((x,y)\)

如果\(f_{x,y}=1\)先手必胜，假设不满足，把大概情况画出来

注意\(0\)的出边全是\(1\)，\(1\)出边至少一个\(0\)

    y-1 y y+1

x+1   B A

x     1 1 C

x-1   0 1 D

那么AC至少一个0，进而BD至少一个1，但是根据\(f_{x-1,y-1}=0\)推出了另外两个1，那么BD都应该全是0才对，矛盾

然后找出最大的不在边界上的\((i,i)\)，此时只能一直向一个方向走（转弯必死），暴力搞搞就行。

忘了= =

看了一下，大概是\(f_{i,j}\)表示放了\(i\)个白块\(j\)个种颜色，转移自己推推。