自动搬运

查看原文

来自洛谷，原作者为

	oh_my_shy 400 winters never count.

搬运于2025-08-24 23:00:50，当前版本为作者最后更新于2024-09-04 18:52:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给出一个单 $\log$ 的离线做法。

考虑枚举 OR 和 AND 相等的那个值是什么。

直接枚举值复杂度不可承受，寻找一个和原值具有相似性质且小值域的东西。

枚举 $\operatorname{popcount}$。不断加入新元素的过程中，序列 OR $\operatorname{popc}$ 单调不降，序列 AND $\operatorname{popc}$ 单调不增。（$\operatorname{popc}$ 简写）

设 OR 和 AND 的 $\operatorname{popcount}$ 都等于 $p$，那么所有 $\operatorname{popc}(a_i)<p$ 的都应该放进 OR，$\operatorname{popc}(a_i)>p$ 的都应该被放进 AND。

$\operatorname{popc}(a_i)<p$ 的部分，相当于是 $\operatorname{popc}(a_i)=p$ 的前缀 OR（取 $p-1$ 位置）。 对每一个二进制位建一个线段树，处理出区间 $[l,r]$ 在 $p\in[0,30]$ 上的前缀 OR。判这个前缀 OR 是否是空集可以线段树顺便维护一个区间个数和，然后算个数和的前缀和。$\operatorname{popc}(a_i)>p$ 的后缀 AND 同理。

考虑 $\operatorname{popc}(a_i)=p$ 的情况。

显然多次 OR 或 AND 同一个数不会再次改变值，先关注数的种类。

若 $\operatorname{popc}(a_i)=p$ 的 $a_i$ 只有一种数，全给 OR、全给 AND、若个数 $\ge 2$ 可以两个都给，枚举三种情况。

• 这里只需要查 $\ge 2$，可以预处理每个数向后第一个相等位置，判断位置 $\le r$。

若有两种数，对于 $a_i\ne a_j,\,\operatorname{popc}(a_i)=\operatorname{popc}(a_j)$，有 $\operatorname{popc}(a_i\,|\,a_j)>\operatorname{popc}(a_i)=p,\,\operatorname{popc}(a_i\,\&\,a_j)<\operatorname{popc}(a_i)=p$，根据前面 OR 只能放 $\operatorname{popc}<p$ 的讨论，AND 对称同理，所以两种数一定只能各自给其中一边，设两种数是 $a_i,\,a_j$，OR 和 AND 的 $\operatorname{popc}$ 一定分别是 $\ge p$ 和 $\le p$ 的，$a_i=a_j$ 时两个 $\operatorname{popc}$ 才有可能取等，这与 $a_i\ne a_j$ 矛盾。所以两种数一定不合法。

对于三种及以上，同样不会合法，所以种类要 $\le 1$。

预处理枚举到每个 $\operatorname{popcount}=p$ 时每个位置向后两个互不相同且 $\operatorname{popc}=p$ 的数，就可以判上述情况了。

复杂度 $O(n\log V+q\log V\log n)$。

考虑优化，瓶颈在于 $\log V$ 个线段树每次询问时的查询。

考虑分治，将询问离线挂在分治树上，每次处理跨过当前分治区间 $mid$ 的询问，猫树的思想，将询问 $[ql,qr]$ 拆为 $[l,mid]$ 上的后缀 $[ql,mid]$，和 $[mid+1,r]$ 上的前缀 $[mid+1,qr]$，直接扫过 $[l,mid$] 得到每个后缀的答案，贡献到询问上，$[mid+1,r]$ 同理。

时间复杂度 $O(n\log n+ q\log V)$。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, f, t) for (int i(f); i <= t; ++i)
#define re(i, t) for (int i(1); i <= t; ++i)
#define per(i, t, f) for (int i(t); i >= f; --i)
#define pe(i, t) for (int i(t); i >= 1; --i)
typedef pair<int, int> pii;
#define pb push_back
#define mkp make_pair
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define fi first
#define se second
const int N = 1e5 + 5;
int n, Q, a[N], pc[N];
int ini[N];
int A[31], B[31], Ac[31], Bc[31], C[31];
using Pos = tuple<int, int>;
Pos P[31][N];
int nxt[N];
map<int, int> buc;
pii qry[N];
vector<int> t[N * 4];
void putqry(int rt, int l, int r, int ql, int qr, int id)
{
    if (l == r)
    {
        t[rt].pb(id);
        return;
    }
    int mid = (l + r) / 2;
    if (qr <= mid)
    {
        putqry(ls(rt), l, mid, ql, qr, id);
        return;
    }
    if (ql > mid)
    {
        putqry(rs(rt), mid + 1, r, ql, qr, id);
        return;
    }
    t[rt].pb(id);
}
struct Dat
{
    int Or, And, cnt;
} Res[31][N];
int tmp[31];
vector<int> vec[N];
void work(int rt, int l, int r)
{
    if (l == r)
    {
        for (int id : t[rt])
        {
            Res[pc[l]][id].Or |= a[l];
            Res[pc[l]][id].And &= a[l];
            Res[pc[l]][id].cnt++;
        }
        return;
    }
    int mid = (l + r) / 2;

    for (int id : t[rt])
        vec[qry[id].fi].pb(id), vec[qry[id].se].pb(id);
    rep(i, 0, 30) tmp[i] = 0;
    rep(i, mid + 1, r)
    {
        tmp[pc[i]] |= a[i];
        for (int id : vec[i])
            rep(p, 0, 30) Res[p][id].Or |= tmp[p];
    }
    rep(i, 0, 30) tmp[i] = 0;
    per(i, mid, l)
    {
        tmp[pc[i]] |= a[i];
        for (int id : vec[i])
            rep(p, 0, 30) Res[p][id].Or |= tmp[p];
    }
    rep(i, 0, 30) tmp[i] = (1 << 30) - 1;
    rep(i, mid + 1, r)
    {
        tmp[pc[i]] &= a[i];
        for (int id : vec[i])
            rep(p, 0, 30) Res[p][id].And &= tmp[p];
    }
    rep(i, 0, 30) tmp[i] = (1 << 30) - 1;
    per(i, mid, l)
    {
        tmp[pc[i]] &= a[i];
        for (int id : vec[i])
            rep(p, 0, 30) Res[p][id].And &= tmp[p];
    }
    rep(i, 0, 30) tmp[i] = 0;
    rep(i, mid + 1, r)
    {
        tmp[pc[i]]++;
        for (int id : vec[i])
            rep(p, 0, 30) Res[p][id].cnt += tmp[p];
    }
    rep(i, 0, 30) tmp[i] = 0;
    per(i, mid, l)
    {
        tmp[pc[i]]++;
        for (int id : vec[i])
            rep(p, 0, 30) Res[p][id].cnt += tmp[p];
    }
    for (int id : t[rt])
        vec[qry[id].fi].clear(), vec[qry[id].se].clear();

    work(ls(rt), l, mid);
    work(rs(rt), mid + 1, r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> Q;
    re(i, n) cin >> a[i];
    pe(i, n)
    {
        nxt[i] = buc[a[i]];
        if (nxt[i] == 0)
            nxt[i] = n + 1;
        buc[a[i]] = i;
    }
    re(i, n) pc[i] = __builtin_popcount(a[i]);
    rep(p, 0, 30)
    {
        re(i, n)
        {
            if (pc[i] == p)
                ini[i] = a[i];
            else
                ini[i] = -1;
        }
        Pos now = make_tuple(n + 1, n + 1);
        pe(i, n)
        {
            if (ini[i] != -1)
            {
                int u = 0, v = 0;
                tie(u, v) = now;
                if (u == n + 1)
                    u = i;
                else if (v == n + 1)
                {
                    if (a[u] == a[i])
                        u = i;
                    else
                        v = u, u = i;
                }
                else
                {
                    if (a[u] == a[i])
                        u = i;
                    else if (a[v] == a[i])
                        v = u, u = i;
                    else
                        v = u, u = i;
                }
                now = tie(u, v);
            }
            P[p][i] = now;
        }
    }
    re(i, Q)
    {
        int l = 0, r = 0;
        cin >> l >> r;
        qry[i] = mkp(l, r);
        putqry(1, 1, n, l, r, i);
    }
    rep(p, 0, 30) re(i, Q)
    {
        Res[p][i].Or = 0;
        Res[p][i].And = (1 << 30) - 1;
        Res[p][i].cnt = 0;
    }
    work(1, 1, n);
    re(qid, Q)
    {
        int l = 0, r = 0;
        tie(l, r) = qry[qid];
        if (l == r)
        {
            cout << "NO\n";
            continue;
        }
        rep(p, 0, 30)
        {
            Dat tt = Res[p][qid];
            A[p] = tt.Or, B[p] = tt.And;
            Ac[p] = Bc[p] = C[p] = tt.cnt;
        }
        rep(p, 1, 30) A[p] |= A[p - 1], Ac[p] += Ac[p - 1];
        per(p, 29, 0) B[p] &= B[p + 1], Bc[p] += Bc[p + 1];
        int Ans = 0;
        rep(p, 0, 30)
        {
            int As = 0, Bs = (1 << 30) - 1, tA = 0, tB = 0;
            if (p > 0)
                As = A[p - 1], tA = (Ac[p - 1] > 0);
            if (p < 30)
                Bs = B[p + 1], tB = (Bc[p + 1] > 0);
            int Cnt = 0;
            int u = 0, v = 0;
            tie(u, v) = P[p][l];
            Cnt = (u <= r) + (v <= r);
            u = min(u, r);
            v = min(v, r);
            if (Cnt == 0)
            {
                if (As == Bs && tA && tB)
                {
                    Ans = 1;
                    break;
                }
            }
            if (Cnt == 1)
            {
                int ok = (((As | a[u]) == Bs && tB) | (As == (Bs & a[u]) && tA));
                if (nxt[u] <= r)
                    ok |= ((As | a[u]) == (Bs & a[u]));
                if (ok)
                {
                    Ans = 1;
                    break;
                }
            }
        }
        if (Ans)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}