题解：P10743 [SEERC2020] AND = OR

· · 题解

这种题放联考 T2 还是过于超前了。

我们先考虑单次询问。

把 a 从小到大排序后，如果存在方案，假设 \mathtt{AND=OR}=x，那么一定是 <x 的全部取 \mathtt{OR}，>x 的全部取 \mathtt{AND}，=x 的随便放即可。于是只需要求出前缀 \mathtt{OR} 和后缀 \mathtt{AND} 的值。

然而这个东西大概是拓展不到区间询问的。我们考虑另一种排序方式：按照 \text{popcount} 排序。

由于取 \mathtt{OR} 后 \text{popcount} 单调不减，取 \mathtt{AND} 后 \text{popcount} 单调不增，所以假设最后 \text{popcount}(\mathtt{AND})=\text{popcount}(\mathtt{OR})=x，那么 \text{popcount}(a_i)<x 的 a_i 应全部取 \mathtt{OR}，\text{popcount}(a_i)>x 的 a_i 应全部取 \mathtt{AND}。

对于 \text{popcount}(a_i)=x 的情况，这些 a_i 必须全部相等。如果存在不相等的 a_i，首先它们不能一起被分到同一个集合里面；其次如果它们分属于不同的集合，相当于在 a\neq b 中选出一个 a 的子集和 b 的超集相等，这显然不可能。

于是我们每次询问从小到大枚举 x，求出 \text{popcount}<x 的数的 \mathtt{OR} 和 \text{popcount}>x 的数的 \mathtt{AND}，然后分类讨论一下 =x 的数应该取哪边即可。

使用二区间合并可以做到 O((n+q)\log w)。

// Problem: P10743 [SEERC2020] AND = OR
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10743
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;

const int N = 1e5 + 5;
const int S = (1 << 30) - 1;
const int L = 32;
const int B = 30;

struct Q {
    int l, r, i;
    Q () { }
    Q (int _l, int _r, int _i) : l(_l), r(_r), i(_i) { }
};

vector<Q> q;

int n, m;
int a[N], c[N], ans[N], vs[N];
int to[L], ta[L], tc[L], ro[L], ra[L], rc[L];
int lo[N][L], la[N][L], lc[N][L];
int po[L], sa[L], pc[L], sc[L];

void mems(int *x, int y) {
    F (i, 0, B) x[i] = y;
}

void memc(int *x, int *y) {
    F (i, 0, B) x[i] = y[i];
}

void conq(int l, int r, vector<Q> qs) {
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    vector<Q> ql, qr, qn;
    for (Q p : qs) {
        int L = p.l, R = p.r;
        if (L > mid) {
            qr.eb(p);
        } else if (R <= mid) {
            ql.eb(p);
        } else {
            qn.eb(p);
            vs[L] = 1;
        }
    }
    mems(to, 0);
    mems(ta, S);
    mems(tc, 0);
    R (i, mid, l) {
        to[c[i]] |= a[i];
        ta[c[i]] &= a[i];
        tc[c[i]]++;
        if (vs[i]) {
            memc(lo[i], to);
            memc(la[i], ta);
            memc(lc[i], tc);
            vs[i] = 0;
        }
    }
    sort(qn.begin(), qn.end(), [](Q &x, Q &y) {
        return x.r < y.r;
    });
    int j = mid + 1;
    mems(ro, 0);
    mems(ra, S);
    mems(rc, 0);
    for (Q p : qn) {
        int L = p.l, R = p.r, i = p.i;
        while (j <= R) {
            ro[c[j]] |= a[j];
            ra[c[j]] &= a[j];
            rc[c[j]]++;
            j++;
        }
        po[0] = (lo[L][0] | ro[0]);
        sa[B] = (la[L][B] & ra[B]);
        pc[0] = lc[L][0] + rc[0];
        sc[B] = lc[L][B] + rc[B];
        F (o, 1, B) {
            po[o] = po[o - 1] | (lo[L][o] | ro[o]);
            pc[o] = pc[o - 1] + lc[L][o] + rc[o];
        }
        R (o, B - 1, 0) {
            sa[o] = sa[o + 1] & (la[L][o] & ra[o]);
            sc[o] = sc[o + 1] + lc[L][o ] + rc[o];
        }
        F (o, 0, B - 1) {
            if (!pc[o] || !sc[o + 1]) {
                continue;
            }
            if (po[o] == sa[o + 1]) {
                ans[i] = 1;
                break;
            }
        }
        if (ans[i]) {
            continue;
        }
        F (o, 0, B) {
            if (lc[L][o] + rc[o] < 2 || (lo[L][o] | ro[o]) != (la[L][o] & ra[o])) {
                continue;
            }
            int w = (lo[L][o] | ro[o]);
            if (((!o ? w : (po[o - 1] | w))) == ((o == B ? w : (sa[o + 1] & w)))) {
                ans[i] = 2;
                break;
            }
        }
    }
    conq(l, mid, ql);
    conq(mid + 1, r, qr);
}

void solve() {
    cin >> n >> m;
    F (i, 1, n) {
        cin >> a[i];
        c[i] = __builtin_popcount(a[i]);
    }
    F (i, 1, m) {
        int l, r;
        cin >> l >> r;
        q.eb(Q(l, r, i));
    }
    conq(1, n, q);
    F (i, 1, m) {
        if (ans[i]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

bool Med;
int main() {
    FIO("bit");
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
    int T = 1;
    // cin >> T;
    while (T--) solve();
    cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
    return 0;
}