Znzryb's Blog
0%

2025牛客WC4-L-Tokitsukaze and XOR-Triangle

Posted on Edited on

思路讲解

【牛客寒假集训营第四场讲题】 【精准空降到 2:13:15】 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）的时间内实现这个查询那？需要用到后缀和的前缀和

image

代码中的ssumB就是代指这个三角形（整体来看是三角形，分序号来看是梯形），ssumB[i][j]如下图所示(第j位是指数位，第i位是指A[i],B[i])

image

查询就是查中间这个小三角形，于是我们用大梯形-小梯形-矩形就好了

image

我们还是要细化一下，这个矩形是怎么求的？还是前缀和？（也不是不行，但是二维前缀和可能MLE了）

我们可以直接用乘法，用a里1的个数乘以b里0的个数就（都是指在数位1里的情况）可以了。

image

这个长方形计算其实也不容易

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75503543

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// 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在这位的值进行变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
// 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;
}
/*

*/

当时在赛场上想到了前缀和+前缀和的思路，但是我没想到按位推导的思路，所以就卡住了，在那边疯狂打表找规律，自然看不出来什么~~（数感不行）~~

赛时在草稿纸上画的图