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)个种颜色，转移自己推推。