题目大意:有a[]和b[],小A要在a[l1,r1]找一个数x,然后小B要在b[l2,r2]找一个数y,A想要xy最大,B想要xy小,请问:xy的值是多少?

思路:

我们换位思考一下:

如果我是A:

我肯定要想:我选这个,B要如何弄?[思考B]

如果我是B:

A选了这个,我该做什么?[思考B]

两个思考不太一样,但都是要想B怎么样

所以我们设计算法时也应该思考B:

我们不难发现,B是这样思考的

1.如果x\ge0,则y=最小值a

2.如果x<0,我y=最大值b

所以,B要么用a,要么用b

那我们在思考A

如果a>0,则我用最大值c

如果b<0,则我用最小值d

如果y=a,x\ge0(定理一)

我又不想少,我用非负最小值e

如果y=b,x<0(定理二)

我用非正最大值f

所以,A用{c,d,e,f}中一个

维护区间最值,ST表在此!

所以,本体使用六个ST表即可

Logo

技术共进,成长同行——讯飞AI开发者社区

更多推荐