A. 判断序列是否为严格下降序列.
B. (a_i&a_jge a_ioplus a_j)当且仅当(a_i)和(a_j)二进制最高位(1)相等.
C. 线段树.每段区间记录(4)个值:开始为正/负,结尾为正/负的序列最大和.复杂度(O(n+qlog n)).
D. 离散化.答案为(displaystylesum_{x}Bigg(inom{Big|{i:l_ile xle r_i}Big|}{k}-inom{Big|{i:l_i< xle r_i}Big|}{k}Bigg)).复杂度(O(nlog n)).
E. 动态规划.记(dp(a,b,c,d))为考虑前(a)个数,末尾连续(b)个(0),共(c)个(1),操作(d)次可以得到的最大值.
考虑每一位的选择有两种转移(用箭头左侧更新右侧):
[dp(a,b,c,d)+(a-b-c) o dp(a+1,b+1,c,d)\dp(a,b,c,d) o dp(a+1,b,c+1,d+|a+1-p_{d+1}|),
]
其中(p_i)表示原数组中第(i)个(1)的位置.
最后答案为(displaystylemax_{0le jle k,0le ile n-m}dp(n,i,m,j)),其中(m)是原数组(1)的数量.
复杂度为(O(n^5)),使用滚动数组空间复杂度为(O(n^4)),需要注意常数.