Znzryb's Blog
0%

Posted on Edited on

思路讲解

我们将不匹配的位置分类，发现最多只有四类，ab 分别是 00*,* 01*,* 10*,* 11 ，任意
两个不同种类不匹配的话，我们一定可以交换其中的某一位 0 和 1 使之两两匹配，

其他的没什么特殊的，我们发现四种情况全部都可以选择其他另外一种情况抵消。

那么问题就来到了怎么样抵消的问题上

我们一定可以交换其中的某一位 0 和 1 使之两两匹配，那么我
们就只看最多的一类不匹配的位置的数量有没有超过总数的一半即可。
如果超过就超过的部分反置，其余匹配，否则一定存在一种分配方式使之匹配后至多
仅剩一个。

官解的匹配方式是这样的，但我相信这个分类讨论大抵是没那么容易想到的，那我们有没有一种策略去匹配不出错那？

用大的去匹配次大的

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
priority_queue<ll> pq;
pq.push(rem0);
pq.push(rem1);
pq.push(rem01);
pq.push(rem10);
ll ans=0;
while (SZ(pq) != 1) {
  ll u = pq.top();
  pq.pop();
  ll v = pq.top();
  pq.pop();
  ans += v * Y;
  if (u == v) continue;
  pq.push(u - v);
}
ans += pq.top() * X;

用大的去匹配小的

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
priority_queue<ll> pq;
pq.push(rem0);
pq.push(rem1);
pq.push(rem01);
pq.push(rem10);
ll ans = 0;
while (SZ(pq) > 1) {
  ll u = pq.top();
  pq.pop();
  ll v = pq.top();
  pq.pop();
  ans += v * Y;
  pq.push(u - v);
}
if (pq.empty()) {
  cout << ans << '\n';
  return 0;
}
ans += pq.top() * X;
cout << ans << '\n';

似乎都会出问题，这些贪心策略都有瑕疵（见以下hack数据3，5，7，13）

1
2
3
4
5
6
7
28 5 6
0001111100000001111111111111
0001111111111110000000000000
1111111100000000000000000000

应该输出
84（14次交换*6=84）

有些人~~（我）~~可能觉得3，5，7，13根本无法消除（无法完全通过交换消除），通过交换最终会剩余2

但实际上是可以的，只不过比较复杂，需要通过分段的方法消除，具体见下

image

AC代码

AC

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

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
// Problem: 小L的位运算
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95337/C
// Memory Limit: 512 MB
// Time Limit: 2000 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
#define SZ(a) ((int)a.size())

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>(1e6) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, X, Y, T;
char A[MAXN], B[MAXN], C[MAXN];
// ll rem[7];
ll rem1, rem0, rem10, rem01;
// vector<ll> pq;
// ll ans=INF;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> X >> Y;
  FOR(i, 1, N) { cin >> A[i]; }
  FOR(i, 1, N) { cin >> B[i]; }
  FOR(i, 1, N) { cin >> C[i]; }
  FOR(i, 1, N) {
    if (((A[i] - '0') ^ (B[i] - '0')) != (C[i] - '0')) {
      if (C[i] == '1') {
        if (A[i] == '0' && B[i] == '0') {
          rem0 += 1;
        } else {
          rem1 += 1;
        }
      } else {
        if (A[i] == '1') {
          rem10 += 1;
        } else {
          rem01 += 1;
        }
      }
    }
  }
  // rem[0]=rem0,rem[1]=rem1,rem[2]=rem10,rem[3]=rem01;
  if (X * 2 > Y) {
    ll sum=rem0+rem1+rem10+rem01;
    ll maxR=max({rem0,rem1,rem10,rem01});
    ll ans=0;
    if(maxR*2<=sum){
    	ans=sum/2*Y+sum%2*X;
    }else{
    	ans=(maxR-(sum-maxR))*X+(sum-maxR)*Y;
    }
    cout << ans << '\n';
  } else {
    cout << (rem1 + rem0 + rem10 + rem01) * X << '\n';
  }
  return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

哈哈，不知道还可以这样分段消除，还以为题目出问题了，我太菜了

Posted on Edited on

思路讲解

image

倒过来找，不断的找树状数组上第pi个空位

这样做是对的原因是前面的被占的都是后来者，你是先来的，所以你只用管空白位置，完全不用管被占的位置

AC代码

AC

https://atcoder.jp/contests/abc392/submissions/62634320

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
// Problem: F - Insert
// Contest: AtCoder - Japan Registry Services (JPRS) Programming Contest 2025#1
// (AtCoder Beginner Contest 392) URL:
// https://atcoder.jp/contests/abc392/tasks/abc392_f Memory Limit: 1024 MB Time
// Limit: 2000 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
#define SZ(a) ((int)a.size())

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;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(5e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T, P[MAXN], ans[MAXN];

struct BIT {  // 普通的单点修改区间查询树状数组（依赖MAXN）
  ll tr[MAXN];
  int n;
  inline int lowbit(int x) { return x & (-x); }
  BIT(int ln) {  // 构造+初始化函数
    n = ln;
    FOR(i, 1, n) { tr[i] = 0; }
  }
  inline void add(int p, int x) {
    while (p <= n) {
      tr[p] += x;
      p += lowbit(p);
    }
  }
  inline ll query(int l, int r) {
    ll lres = 0, rres = 0;
    l -= 1;
    while (l > 0) {
      lres += tr[l];
      l -= lowbit(l);
    }
    while (r > 0) {
      rres += tr[r];
      r -= lowbit(r);
    }
    return rres - lres;
  }
  inline int findKth(int k) {  // 找到第k个空位
    int cx = 0;
    for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
      if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
        // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
        k -= lowbit(cx + i) - tr[cx + i];
        cx += i;
      }
    }
    return cx+1;	// 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
  }
};

inline void solve() {
  cin >> N;
  BIT cnt(N);
  FOR(i, 1, N) { cin >> P[i]; }
  ROF(i, N, 1) {
    ll p = cnt.findKth(P[i]);  // 所有之后要在P[i]之前的都会影响i的摆放
    ans[p] = i;
    cnt.add(p, 1);
  }
  FOR(i, 1, N) { cout << ans[i] << ' '; }
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();

  return 0;
}
/*
AC
https://atcoder.jp/contests/abc392/submissions/62634320
9
1 2 2 4 5 2 3 2 3

1 8 9 6 7 3 2 4 5

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

为什么这道题目可以用类似于双指针的东西做出来？

其实有点类似于我最早的思路，就是已经合并过的就不管了。

不过他是以边为主视角的，这个还是比较新颖的，我之前的都是以块为主视角的，但块存在自环，重边，没边等等情况，总之肯定没有以边为主视角方便。

image

AC代码

https://atcoder.jp/contests/abc392/submissions/62618534

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
#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
#define SZ(a) ((int)a.size())

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;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T;
vector<pll> g[MAXN];
pll ab[MAXN];
bool isRem[MAXN];

struct DSU {  // referred jiangly
  int fa[MAXN], siz[MAXN], ln;
  DSU(int n) {
    ln = n;
    FOR(i, 1, n) {
      fa[i] = i;
      siz[i] = 1;
    }
  }
  int find(int x) {
    while (fa[x] != x) {
      x = fa[x];
      fa[x] = fa[fa[x]];
    }
    return x;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    siz[x] += siz[y];
    fa[y] = x;
    return true;
  }
  int size(int x) { return siz[find(x)]; }
  int countFa() {
    int res = 0;
    FOR(i, 1, ln) {
      if (fa[i] == i) ++res;
    }
    return res;
  }
};

inline void solve() {
  cin >> N >> M;
  DSU dsu(N);
  FOR(i, 1, M) {
    cin >> ab[i].fi >> ab[i].se;
    if (!dsu.merge(ab[i].fi, ab[i].se)) {  // 说明这条边是多余的
      isRem[i] = true;
    }
  }
  ll ans = dsu.countFa() - 1;
  ll flag = 1;
  cout << ans << '\n';
  FOR(i, 1, M) {
    if (ans <= 0) break;
    if (isRem[i]) {  // 只有多余的边才会进入
      FOR(j, flag, N) {
        if (!dsu.same(ab[i].fi, j)) {
          flag = j + 1;
          cout << i << ' ' << ab[i].se << ' ' << j << '\n';
          dsu.merge(ab[i].fi, j);
          --ans;
          break;
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}
/*
AC
https://atcoder.jp/contests/abc392/submissions/62618534
*/

心路历程（WA，TLE，MLE……）

直接遍历还是有风险，合并还是要用dsu

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
// Problem: E - Cables and Servers
// Contest: AtCoder - Japan Registry Services (JPRS) Programming Contest 2025#1 (AtCoder Beginner Contest 392)
// URL: https://atcoder.jp/contests/abc392/tasks/abc392_e
// Memory Limit: 1024 MB
// Time Limit: 2000 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
#define SZ(a) ((int) a.size())

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;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
vector<pll> g[MAXN];
ll fa[MAXN];
bool vis[MAXN];
vector<ll> root;
vector<pll> rem[MAXN];
pll ab[MAXN];

inline ll find(ll x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void dfs(ll x,ll pa){
	vis[x]=true;
	FOR(i,0,SZ(g[x])-1){
		ll fx=g[x][i].fi;
		if(vis[fx]) {
			// cerr<< fx <<' '<<pa<<'\n';
			if(fx!=pa) rem[find(fx)].pb({ab[g[x][i].se].se,g[x][i].se});
			continue;
		}
		fa[fx]=find(x);
		dfs(fx,x);
	}
}

inline void solve(){
	cin>>N>>M;
	FOR(i,1,M){
		ll a,b;
		cin>>a>>b;
		ab[i].fi=a,ab[i].se=b;
		if(a!=b){
			g[a].pb({b,i});
			g[b].pb({a,i});
		}else{
			g[a].pb({b,i});
		}
	}
	FOR(i,1,N){
		fa[i]=i;
	}
	
	FOR(i,1,N){
		if(vis[i]) continue;
		// cerr<<"OK\n";
		dfs(i,0);
	}
	set<ll> disCot;
	FOR(i,1,N){
		if(fa[i]==i) root.push_back(i),disCot.insert(i);
	}
	cout<<SZ(root)-1<<'\n';
	if(SZ(root)-1==0) return;
	disCot.erase(1);
	FOR(i,0,root.size()-1){
		if(disCot.empty()){
			break;
		}
		ll ri=root[i],start=0;
		if(SZ(rem[ri])>0){
			if(disCot.find(ri)!=disCot.end()){
				if(ri!=1) cout<<rem[ri][0].se<<' '<<rem[ri][0].fi<<' '<<1<<'\n',start=1;
				disCot.erase(ri);
			}
		}
		FOR(j,start,SZ(rem[ri])-1){
			if(disCot.empty()) return;
			cout<<rem[ri][j].se<<' '<<rem[ri][j].fi<<' '<< *disCot.begin()  <<'\n';
			disCot.erase(disCot.begin());	// 一定要在删之前判断是否为空
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	
	// FOR(i,1,N){
		// cerr<<i<<":\n";
		// FOR(j,0,SZ(rem[i])-1){
			// cerr<<rem[i][j].fi<<' '<< rem[i][j].se<<'\n';
		// }
		// cerr<<'\n';
	// }	
	return 0;
}
/*
WA*9
https://atcoder.jp/contests/abc392/submissions/62570130
排除返祖边处理问题
8 8
1 2
1 3
1 3
4 5
5 6
6 8
8 7
7 5

1
3 3 4


排除连接问题（有的联通块未连接）
6 5
1 2
1 2
1 3
5 6
5 6

2
2 2 4
5 6 1


*/

Posted on Edited on

思路讲解

AC代码

AC
https://vjudge.net/solution/58198800

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
// Problem: A/B
// Contest: Virtual Judge - HDU
// URL: https://vjudge.net/problem/HDU-1576
// Memory Limit: 32 MB
// Time Limit: 1000 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>(1e6)+10,INF=static_cast<ll>(5e18)+3,mod=9973;

ll N,B,T,A[MAXN];

void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){	// x，y都是反的
		x=1,y=0;
	}else{
		exgcd(b,a%b,y,x);
		y-=a/b*x;	// 实际是y=x1-a/b*y1	但实际上因为我们在上面反了一下，所以这里也要反一下
	}
}
// (ax-1)%m=0
inline void solve(){
	// 其实就是要求B的逆元
	cin>>N>>B;
	ll x_,y_;
	exgcd(B,mod,x_,y_);	// x_就是B的逆元
	// (A/B)%mod = (A/B)%mod *(bk)%mod=(Ak)%mod
	ll ans=(N*x_)%mod;
	if(ans<0) ans+=mod;
	cout<< ans <<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://vjudge.net/solution/58198800
*/

心路历程（WA，TLE，MLE……）

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;
}
/*

*/

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

赛时在草稿纸上画的图