CF1168C And Reachability

And Reachability - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF1168C And Reachability

题目大意

给定一个长度为 \(n\) 的数组 \(a\) 。

你可以选择一个长度为 \(k\) 的数组 \(p\)

\(p_1 = x , p _k = y\)

当 \(x<y\) 且 \(a_{p_i} \& a_{p_{i + 1}} > 0\) 时，我们称 \(x , y\) 为可到达的

现在给你 \(q\) 组询问，每个询问问你 \(x , y\) 是否可以到达

思路

\(dp\)

设 \(c_{i , j}\) 为二进制下的 \(a_i\) 的第 \(j\) 位是否为 \(1\)

设 \(g_{i , j}\) 为 \([1,{i- 1}]\) 中第 \(j\) 位为 \(1\) 且离 \(i\) 最近的点

那么

\[g_{i , j} = (c_{i - 1 , j} = 1) ? i - 1 : g_{i - 1 , j} \]

设 \(f_{i , j}\) 为 \([1 , i -1]\) 中第 \(j\) 位为 \(1\) 且能够到达 \(i\) 的最近的一个点

需要中转站

\[f_{i , j} = max (f_{i , j} , f_{g_{i , k} , j}) (c_{i , k} = 1) \]
不需要中转站

\[f_{i , j} = max (f_{i , j} , f_{i , k}) (c_{i , k} == 1 \ and \ c_{g_{i , k} , j} = 1 ) \]

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 3e5 + 5;
int n , q;
int a[N] , f[N][25] , g[N][25] , c[N][25];
int read () {
    int val = 0;
    char ch = getchar ();
    while (ch > '9' || ch < '0') ch = getchar ();
    while (ch >= '0' && ch <= '9') {
        val = val * 10 + (ch - '0');
        ch = getchar();
    }
    return val;
}
void pre (int i , int x) {
    fu (j , 1 , 20) {
        if (x & 1) c[i][j] = 1;
        x >>= 1;
    }
}
int main () {
    freopen ("and.in" , "r" , stdin);
    freopen ("and.out" , "w" , stdout);
    n = read () , q = read ();
    fu (i , 1 , n) {
        a[i] = read ();
        pre (i , a[i]);
    }
    fu (i , 1 , n) {
        fu (j , 1 , 20) {
            if (c[i - 1][j]) g[i][j] = i - 1;
            else g[i][j] = g[i - 1][j];
        }
    }
    fu (i , 1 , n) {
        fu (j , 1 , 20) {
            fu (k , 1 , 20) {
                if (!c[i][k]) continue;
                int x = g[i][k];
                if (c[x][j]) f[i][j] = max (f[i][j] , x);
                else f[i][j] = max (f[i][j] , f[x][j]);
            }
        }
    }
    int l , r , flg = 0;
    while (q --) {
        flg = 0;
        scanf ("%d%d" , &l , &r);
        fu (i , 1 , 20) {
            if (c[l][i] && f[r][i] >= l) {
                puts ("Shi");
                flg = 1;
                break;
            }
        }
        if (flg) continue;
        puts ("Fou");
    }
    return 0;
}