n块积木的大小依次为1,2,...n,每块是红色或蓝色。每次询问给定[l,r],用这些积木搭塔,要求每座她从下到上大小递减、相邻颜色不同。
求最少的塔数。
基础做法:
对于一个询问,从小到大处理积木,把当前积木连接到某座塔的底部,因为当前积木比已经处理的都大,只需判断颜色。
维护底部为红色,蓝色的塔数分别为u,v。当遇到红色积木时,若v>0,就接到一座蓝底塔下面,那么u+1,v-1.蓝色同理。
单词询问时间复杂度为O(r-l+1),总时间复杂度为O(nq).
优化做法(满分):
把红色塔记录为+1,蓝色塔记录为-1。
对于当前询问中的序列,设已经处理部分的和为S,至今出现过的最大、最小前缀和为M,L。
那么扫描过程中始终有:u=S-L v=M-S