CF1168C And Reachability

发表于 | 阅读数

题意:

给定$a[n]$,有$q$组询问$l,r$

问是否存在$l=p_1<p_2<p_3…p_k=r$

也就是说$(l+1)-(r)$之间尽量是二进制的1多
$if (now \& a[i]>0)$
$now|=a[i]$
设$dp[i][j]$为$a[i]$的第j位最晚出现的位置
那么转移方程就是
$a[i]\& (1<<j)$

在查询的时候只需要知道 $a[l]$是否有一位在$(l+1)-(r)$出现过
即$dp[i][j]>=l$ 此时就一定$a[p_i] \& a[p_{i+1}]>0$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 3e5 + 10;
const int M = 21;
int a[N], n, dp[N][M], pre[M], q;
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < M; j++)
            if (a[i] & (1 << j))
            {
                dp[i][j] = i;
                for (int k = 0; k < M; k++)
                    dp[i][k] = max(dp[i][k], dp[pre[j]][k]);
                pre[j] = i;
            }
    for (int i = 1; i <= q; i++)
    {
        bool flag = 0;
        int l, r;
        scanf("%d%d", &l, &r);
        for (int j = 0; j < M; j++)
            if (a[l] & (1 << j) && dp[r][j] >= l)
                flag = 1;
        puts(flag ? "Shi" : "Fou");
    }
}