個、個、個、この世で個っ端みじんに壊れた個
个、个、个、在这世上碎成一“个个”渣的“个”
比赛链接
J. Subrectangle Count
给定一个长度为 n（n ≥ 2）的整数序列 a₁, a₂, ..., aₙ，和一个长度为 m（m ≥ 2）的整数序列 b₁, b₂, ..., bₘ。我们可以构造一个 n × m 的矩阵 c，其中矩阵元素 cᵢ,ⱼ = aᵢ ⊕ bⱼ（1 ≤ i ≤ n, 1 ≤ j ≤ m），这里的 ⊕ 表示按位异或运算。
请计算有多少对 (i, j)（1 ≤ i < n, 1 ≤ j < m）满足：矩阵 c 中由 (i, j) 为左上角的 2×2 子矩形：
的形式为：
这等价于同时满足以下三个条件：
cᵢ,ⱼ₊₁ = cᵢ,ⱼ + 1cᵢ₊₁,ⱼ = cᵢ,ⱼ + 2cᵢ₊₁,ⱼ₊₁ = cᵢ,ⱼ + 3
输入
第一行包含一个整数 T（1 ≤ T ≤ 10⁵），表示测试用例的数量。
对于每个测试用例：
- 第一行包含两个用空格分隔的整数
n, m（2 ≤ n, m ≤ 2 × 10⁵），表示矩阵c的行数和列数。 - 第二行包含
n个用空格分隔的整数，表示序列a₁, a₂, …, aₙ（0 ≤ aᵢ < 2³⁰）。 - 第三行包含
m个用空格分隔的整数，表示序列b₁, b₂, …, bₘ（0 ≤ bᵢ < 2³⁰）。
保证所有测试用例的 n 之和不超过 2 × 10⁵，所有测试用例的 m 之和不超过 2 × 10⁵。
输出
对于每个测试用例，输出一行，包含一个整数，表示满足条件的 (i, j) 对数。
题解
设 \(x=c_{i,j}\)，那么我们可以得到一些式子：
-
\(x \oplus x+1=c_{i,j} \oplus c_{i,j+1}=(a_i\oplus b_j) \oplus (a_{i}\oplus b_{j+1})=b_j\oplus b_{j+1}\)
-
\(x \oplus x+2=c_{i,j} \oplus c_{i+1,j}=(a_i\oplus b_j) \oplus (a_{i+1}\oplus b_{j})=a_i\oplus a_{i+1}\)
-
\(x+1 \oplus x+3=c_{i,j+1} \oplus c_{i+1,j+1}=(a_{i}\oplus b_{j+1}) \oplus (a_{i+1}\oplus b_{j+1})=a_i\oplus a_{i+1}\)
-
\(x+2 \oplus x+3=c_{i+1,j} \oplus c_{i+1,j+1}=(a_{i+1}\oplus b_j) \oplus (a_{i+1}\oplus b_{j+1})=b_j\oplus b_{j+1}\)
考虑 \(x\oplus (x+1)=(x+2)\oplus(x+3)=b_j\oplus b_{j+1}=D_b\)。
\(D_b\) 的性质
-
当 \(x\) 是偶数的时候，\((x+1)\)第一位是 \(1\) ,所以 \(x\oplus (x+1)=1=D_b\)，同理 \((x+2)\) 也是偶数，可得 \((x+2)\oplus (x+3)=1=D_b\)
-
当 \(x\) 是奇数的时候,假设 \(x=011_{(2)}\)，那么 \(x+1=100_{(2)},x+2=101_{(2)},x+3=110_{(2)}\)，\(x\oplus (x+1)=111_{(2)}\neq (x+2)\oplus (x+3)=011_{(2)}\)，易得 \(x\) 不能是奇数。
因此 \(x\) 必须是偶数，并且 \(D_b=1\)。
考虑完了关于 \(b\) 数组性质后，接下来考虑 \(a\) 数组性质。
设 \(D_a\) 表示 \(x\oplus (x+2)\)
\(D_a\) 的性质
既然 \(x=2k\)，不妨设 \(D_a=x\oplus(x+2)=2k\oplus (2k+2)=2(k\oplus(k+1))\)，\(k\oplus (k+1)\) 必须是形如 \(2^p-1\),所以 \(D_a=x\oplus (x+2)=2^{p+1}-2\)，设 \(D_a=x\oplus (x+2)=2^v-2\)，那么稍加推理可以得到 \(x\) 的形状是 \(x\equiv 2^{v-1}-2\pmod{2^v}\).
算法步骤:
- 统计所有满足 \(b_j \oplus b_{j+1} = 1\) 的下标 \(j\)。
- 遍历所有可能的 \(v \in [2, 30]\)。对于每一个 \(v\)，找出所有满足 \(a_i \oplus a_{i+1} = 2^v - 2\) 的下标 \(i\)。
- 利用公式 \(x \equiv 2^{v-1}-2 \pmod{2^v}\)，由于 \(x = a_i \oplus b_j\)，该条件等价于：
- 使用排序配合二分查找来快速统计满足条件的 \((i, j)\) 数量。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int N=2e5+5;
int a[N],b[N];
inline void solve(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}vector<int> posj;for(int j=1;j<m;j++){if((b[j]^b[j+1])==1){posj.push_back(j);}}vector<int> aa[32];for(int i=1;i<n;i++){int Da=a[i]^a[i+1];int tar=Da+2;if(tar>=4&&(tar&(tar-1))==0){//tar是2的次方int v=0;while(tar>1){tar>>=1;v++;}aa[v].push_back(i);}}int ans=0;for(int v=2;v<=30;v++){if(aa[v].empty()||posj.empty()) continue;int mod=(1<<v);vector<int> bmods;for(int j:posj){bmods.push_back(b[j]%mod);}sort(bmods.begin(),bmods.end());int xmask=(1<<(v-1))-2;for(int i:aa[v]){int tarbmod=(a[i]%mod)^xmask;//套用公式计算b的应该的值auto range=equal_range(bmods.begin(),bmods.end(),tarbmod);//在升序数组中统计bmods中和tarbmod值相等的区间，左开右闭ans+=distance(range.first,range.second);//区间范围长度}}cout<<ans<<'\n';return;
}
signed main(void){cin.tie(NULL)->sync_with_stdio(false);int T=1;cin>>T;while(T--){solve();}return 0;
}
多理解