P1077 长街行 官方题解

【部分分：测试点 1∼31\sim 31∼3】

• 这一档的序列很短。对一次询问 $[l,r]$，可以枚举区间内所有非空位置集合 $S$。
• 对每个集合直接计算

若结果不为 $0$，就用 $\lvert S\rvert$ 更新答案。

• 单次询问的时间复杂度为 $\mathcal O(2^n n)$，总时间复杂度为 $\mathcal O(q2^n n)$。

【部分分：测试点 4∼74\sim 74∼7】

• 上一档枚举了所有集合，瓶颈在于集合数量。考虑一支合法队伍为何能够通过长街。

• 必要性：若若干整数按位与不为 $0$，结果中至少有一个二进制位为 $1$，因此所有被选整数在这一位上都是 $1$。

• 充分性：固定一个二进制位，把区间中这一位为 $1$ 的整数全部选出，它们的按位与在这一位上仍为 $1$。

• 所以，合法队伍等价于共享某个值为 $1$ 的二进制位。答案就是各二进制位出现次数的最大值。

• 这一档只有一次询问。枚举二进制位，并扫描整个询问区间。

• 记 $c_j$ 为区间中第 $j$ 位为 $1$ 的整数个数，那么答案为

• 时间复杂度为 $\mathcal O(n\log V)$，空间复杂度为 $\mathcal O(\log V)$，其中 $V$ 表示值域。

【部分分：测试点 8∼158\sim 158∼15】

• 询问增多以后，反复扫描区间会成为新的瓶颈。可以预先求出所有区间的答案。
• 枚举左端点 $l$，再从 $l$ 开始向右移动右端点 $r$。每加入一个数，就更新它含有的所有二进制位的出现次数。
• 根据上一档的结论，当前各二进制位出现次数的最大值就是区间 $[l,r]$ 的答案。之后每次询问可以在 $\mathcal O(1)$ 时间内完成。
• 时间复杂度为 $\mathcal O(n^2\log V+q)$，空间复杂度为 $\mathcal O(n^2)$。

【正解】

• 上一档仍然求出了 $\mathcal O(n^2)$ 个区间的答案，但真正需要回答的区间只有 $q$ 个。只保留每个二进制位的前缀信息即可。
• 记 $[P]$ 为命题 $P$ 的 Iverson 括号。对每个二进制位 $j$ 建立前缀和

• 在询问 $[l,r]$ 中，第 $j$ 位出现的次数为

• 根据已经证明的等价条件，一次询问的答案为

• 预处理前缀和需要 $\mathcal O(n\log V)$ 的时间，每次询问只需枚举二进制位。
• 总时间复杂度为 $\mathcal O((n+q)\log V)$，空间复杂度为 $\mathcal O(n\log V)$。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/314Name:street.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 20001011using namespace std;12 13int c,T,n,q,Line[MAXN],Pre[31][MAXN];14 15void Solve(){16    scanf("%d%d",&n,&q);17    for(int i=1;i<=n;i++) scanf("%d",&Line[i]);18    for(int j=0;j<=30;j++){19        Pre[j][0]=0;20        for(int i=1;i<=n;i++) Pre[j][i]=Pre[j][i-1]+((Line[i]>>j)&1);21    }22    while(q-->0){23        int l,r,Ans=0;24        scanf("%d%d",&l,&r);25        for(int j=0;j<=30;j++) Ans=max(Ans,Pre[j][r]-Pre[j][l-1]);26        printf("%d\n",Ans);27    }28    return;29}30 31int main(){32    freopen("street.in","r",stdin);33    freopen("street.out","w",stdout);34    scanf("%d%d",&c,&T);35    while(T-->0) Solve();36    return 0;37}