2025牛客WC4-L-Tokitsukaze and XOR-Triangle · znzryb
## 思路讲解
【牛客寒假集训营第四场讲题】 【精准空降到 2:13:15】 [https://www.bilibili.com/video/BV1TxN8eKEQY/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=7995](https://www.bilibili.com/video/BV1TxN8eKEQY/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=7995)
这个题解可以理解为该视频讲解的笔记
其实异或很简单，不就是相同的相消嘛，所以说对数值有贡献的就只有1是吧，那么把1消掉嘛，剩下的1就是我们要求的值了
道理是比较简单的，就是如果A[i]的这位是0，我们就想知道B[i～r]这位有多少个1，反之，如果A[i]的这位是1，B[i~r]这位有多少个0，统计好以后使用权值进行计算
然后知道了这个道道，但怎么样在O（1）的时间内实现这个查询那？需要用到后缀和的前缀和
代码中的ssumB就是代指这个三角形（整体来看是三角形，分序号来看是梯形），ssumB[i][j]如下图所示(第j位是指数位，第i位是指A[i],B[i])
查询就是查中间这个小三角形，于是我们用大梯形-小梯形-矩形就好了
我们还是要细化一下，这个矩形是怎么求的？还是前缀和？~~（也不是不行，但是二维前缀和可能MLE了）~~
我们可以直接用乘法，用a里1的个数乘以b里0的个数就（都是指在数位1里的情况）可以了。
这个长方形计算其实也不容易
## AC代码
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75503543](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75503543)
```cpp
// Problem: Tokitsukaze and XOR-Triangle
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/L
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;
ll N,M,T,A[MAXN],B[MAXN],B2[MAXN][32],A2[MAXN][32],sumB[MAXN][32],sumA[MAXN][32];
ll pow2[35];
ll ssumB[MAXN][32];
inline void solve(){
cin>>N>>M;
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,N){
cin>>B[i];
}
FOR(i,0,N+5){ // init
FOR(j,0,31){
sumB[i][j]=0;
sumA[i][j]=0;
A2[i][j]=0;
B2[i][j]=0;
ssumB[i][j]=0;
// ssumA[i][j]=0;
}
}
FOR(i,1,N){
ll x=A[i];
ll idx=0;
while(x){
A2[i][idx++]=x%2;
x/=2;
}
}
FOR(i,1,N){
ll x=B[i];
ll idx=0;
while(x){
B2[i][idx++]=x%2;
x/=2;
}
}
FOR(i,1,N){ // A的后缀和
FOR(j,0,31){
sumA[i][j]=(sumA[i-1][j]+A2[i][j])%mod;
}
}
ROF(i,N,1){ // 后缀和
FOR(j,0,31){
sumB[i][j]=(sumB[i+1][j]+B2[i][j])%mod;
}
}
FOR(i,1,N){
FOR(j,0,31){
if(A2[i][j]==1){
ssumB[i][j]=(ssumB[i-1][j]+(N-i+1-sumB[i][j]))%mod; // 需要计算0的数量(用总数量-1的数量)
}else{
ssumB[i][j]=(ssumB[i-1][j]+sumB[i][j])%mod;
}
}
}
FOR(i,1,M){
ll l,r;
cin>>l>>r;
ll ans=0;
FOR(j,0,31){
ll sq=0;
// A中0的个数乘以B中1的个数
sq=(r-l+1-(sumA[r][j]-sumA[l-1][j]))*sumB[r+1][j]%mod+(sumA[r][j]-sumA[l-1][j])*(N-r-sumB[r+1][j])%mod;
// 大梯形-小梯形- 长方形(A是前缀和，B是后缀和)
ans=(ans+((ssumB[r][j]-ssumB[l-1][j])%mod-sq)*pow2[j])%mod;
}
if(ans<0) ans+=mod;
cout<<ans<<'\n';
}
// FOR(i,1,N){
// cerr<<i<<": ";
// FOR(j,0,31){
// cerr<<ssumB[i][j]<<' ';
// }
// cerr<<'\n';
// }
// // cerr<<'\n';
// FOR(i,1,N){
// cerr<<i<<": ";
// FOR(j,0,31){
// cerr<<sumB[i][j]<<' ';
// }
// cerr<<'\n';
// }
// // cerr<<'\n';
// FOR(i,1,N){
// cerr<<i<<": ";
// FOR(j,0,31){
// cerr<<sumA[i][j]<<' ';
// }
// cerr<<'\n';
// }
// cerr<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
pow2[0]=1;
FOR(i,1,32){
pow2[i]=(pow2[i-1]*2)%mod;
}
while(T--){
solve();
}
return 0;
}
/*
*/
```
## 心路历程（WA，TLE，MLE……）
这个是有点问题的，因为前缀和没有根据A在这位的值进行变化
```cpp
// Problem: Tokitsukaze and XOR-Triangle
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/L
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;
ll N,M,T,A[MAXN],B[MAXN],B2[MAXN][32],A2[MAXN][32],sumB[MAXN][32],sumA[MAXN][32];
ll pow2[35];
ll ssumB[MAXN][32],ssumA[MAXN][32];
ll alr[32],blr[32];
inline void solve(){
cin>>N>>M;
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,N){
cin>>B[i];
}
FOR(i,0,N+5){ // init
FOR(j,0,31){
sumB[i][j]=0;
sumA[i][j]=0;
A2[i][j]=0;
B2[i][j]=0;
ssumB[i][j]=0;
ssumA[i][j]=0;
}
}
FOR(i,1,N){
ll x=A[i];
ll idx=0;
while(x){
A2[i][idx++]=x%2;
x/=2;
}
}
FOR(i,1,N){
ll x=B[i];
ll idx=0;
while(x){
B2[i][idx++]=x%2;
x/=2;
}
}
ROF(i,N,1){
FOR(j,0,31){
sumB[i][j]=(sumB[i+1][j]+B2[i][j])%mod;
}
}
FOR(i,1,N){
FOR(j,0,31){
sumA[i][j]=(sumA[i-1][j]+A2[i][j])%mod;
}
}
FOR(i,1,N){
FOR(j,0,31){
ssumA[i][j]=(ssumA[i-1][j]+sumA[i][j])%mod;
}
}
ROF(i,N,1){
FOR(j,0,31){
ssumB[i][j]=(ssumB[i+1][j]+sumB[i][j])%mod;
}
}
FOR(i,1,M){
ll l,r;
cin>>l>>r;
FOR(j,0,31){
alr[j]=(ssumA[r][j]-ssumA[l-1][j])%mod;
alr[j]=(alr[j]-sumA[l-1][j]*(r+l-1))%mod;
}
FOR(j,0,31){
blr[j]=(ssumB[l][j]-ssumB[r+1][j])%mod;
blr[j]=(blr[j]-sumB[r+1][j]*(r+l-1))%mod;
}
ull ans=0;
FOR(j,0,31){
ans=(ans+(max(alr[j],blr[j])-min(alr[j],blr[j]))*pow2[j])%mod;
//cerr<<max(alr[j],blr[j])-min(alr[j],blr[j])<<'\n';
}
// FOR(j,0,31){
// cerr<<alr[j]<<' ';
// }
// cerr<<'\n';
// FOR(j,0,31){
// cerr<<blr[j]<<' ';
// }
// cerr<<'\n';
ans%=mod;
if(ans<0) ans+=mod;
cout<<ans<<'\n';
}
FOR(i,1,N){
cerr<<i<<": ";
FOR(j,0,31){
cerr<<ssumB[i][j]<<' ';
}
cerr<<'\n';
}
// cerr<<'\n';
FOR(i,1,N){
cerr<<i<<": ";
FOR(j,0,31){
cerr<<ssumA[i][j]<<' ';
}
cerr<<'\n';
}
FOR(i,1,N){
cerr<<i<<": ";
FOR(j,0,31){
cerr<<sumB[i][j]<<' ';
}
cerr<<'\n';
}
// cerr<<'\n';
FOR(i,1,N){
cerr<<i<<": ";
FOR(j,0,31){
cerr<<sumA[i][j]<<' ';
}
cerr<<'\n';
}
cerr<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
pow2[0]=1;
FOR(i,1,32){
pow2[i]=(pow2[i-1]*2)%mod;
}
while(T--){
solve();
}
return 0;
}
/*
*/
```
当时在赛场上想到了前缀和+前缀和的思路，但是我没想到按位推导的思路，所以就卡住了，在那边疯狂打表找规律，自然看不出来什么~~（数感不行）~~
