题解：P10743 [SEERC2020] AND = OR
oh_my_shy
·
·
题解
给出一个单 \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。
对每一个二进制位建一个线段树，处理出区间 $[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)$。
``` cpp
#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;
}
```