#P18692. Swapping Operation

    ID: 18028 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-有限候选集缩减暴力枚举前后缀最值二分查找对称性分析

Swapping Operation

Swapping Operation

给定一个长度为 nn 的非负整数序列 A=a1,a2,…,anA=a_1,a_2,\ldots,a_n,定义

$$F(A)=\max_{1\le k<n}\bigl((a_1\mathbin{\&}a_2\mathbin{\&}\cdots\mathbin{\&}a_k)+(a_{k+1}\mathbin{\&}a_{k+2}\mathbin{\&}\cdots\mathbin{\&}a_n)\bigr),$$

其中 &\& 表示按位与运算。

你至多可以执行一次交换操作:选择两个下标 i,ji,j,满足 1≤i<j≤n1\le i<j\le n,交换 aia_i 和 aja_j 的值。

求至多执行一次交换操作后,F(A)F(A) 的最大可能值。

输入格式

输入包含多组测试用例。第一行包含一个整数 TT,表示测试用例数。

对于每个测试用例:

第一行包含一个整数 nn(2≤n≤1052\le n\le10^5),表示序列长度。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤1090\le a_i\le10^9),表示给定序列。

保证整个输入中所有测试用例的 nn 之和不超过 10510^5。

输出格式

对于每个测试用例,输出一行,包含一个整数,表示至多执行一次交换操作后 F(A)F(A) 的最大可能值。

样例 1 输入

3
6
6 5 4 3 5 6
6
1 2 1 1 2 2
5
1 1 2 2 2

样例 1 输出

7
3
3

样例说明

对于第一组测试用例,可以交换 a4a_4 和 a6a_6,序列变为 {6,5,4,6,5,3}\{6,5,4,6,5,3\}。然后选择 k=5k=5,得到 $F(A)=(6\mathbin{\&}5\mathbin{\&}4\mathbin{\&}6\mathbin{\&}5)+(3)=7$。

对于第二组测试用例,可以交换 a2a_2 和 a4a_4,序列变为 {1,1,1,2,2,2}\{1,1,1,2,2,2\}。然后选择 k=3k=3,得到 $F(A)=(1\mathbin{\&}1\mathbin{\&}1)+(2\mathbin{\&}2\mathbin{\&}2)=3$。

对于第三组测试用例,不执行交换。选择 k=2k=2,得到 $F(A)=(1\mathbin{\&}1)+(2\mathbin{\&}2\mathbin{\&}2)=3$。