YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 4k 所需閱讀時間 ≈ 13 分鐘
B, DP,分治,前缀和,数学

题目

https://atcoder.jp/contests/agc056/tasks/agc056_b

一个长度为n的排列

对于q个查询构成的大小为q向量有多少种

其中每次查询排列[l..r] 中最大值的下标

n <= 300

查询不重复, 合法(l < r)

题解

考虑把数字从大到小放入排列的位置.

假设把N放在位置pos,那么有三类区间

  1. 包含pos的
  2. 完全在pos左侧
  3. 完全在pos右侧

那么显然对于所有查询区间包含pos的,返回都是pos

而对剩余的,如果把左侧位置的所有值保持相对顺序,右侧位置的所有值保持相对顺序, 然后调整值让左侧所有值大于右侧所有值, 对于输出的q维向量没有变化.(因为相对顺序不变,左侧和右侧内部,原来哪个位置大还是哪个大,且都在pos单侧互不影响), 因此不妨我们选定pos后如此调整

先不考虑重复

那么设计状态dp[i][j][pos] = 在[i..j]中, pos为最大值, 且属于[i..j]中某个完整区间的 方案数

那么注意到上面,当我们选定了pos, 就是把区间划分成[i..pos-1]pos[pos+1..j]

原题的答案变为 sum(dp[0][n-1][pos = 0..n-1])

其中注意到,我们在对于无效的pos结果为0, 例如 pos不属于[i..j]中任何一个完整区间, 其对应的情景是最大值不属于任何一个区间,那么 这个位置删掉都行 更不用考虑值了

那么上面的转移方程有

dp[0][n-1][pos] = sum(dp[0][pos-1][0..pos-1]) * sum(dp[pos+1][n-1][pos+1..n-1])

也就是 左侧 和 右侧分别独立计算.

而这个计算规则实际上和原问题是同一个问题. 因此可以看成是分治

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

其中 sum为零时,记为1,属于空方案

引理: 分治中数值的大小无影响,只有输出有影响

因为隔离性,假设右侧不动,来考虑左侧的排列数值变化,但产出向量不变,对结果有什么影响.

假设左侧存在[1..2][3..4] 非重叠 或者 [1..2][2..3]重叠区间或其它任何状态, 那么可能不同的值,有相同的向量产生

一旦左侧的产出向量确定了, 注意到转移方程的剩余部分,一个是pos,那一定比左侧都大,而右侧根据它们的隔离性,比左侧都小,所以转移方程的任何剩余向量也不会受到影响.

所以, 转移方程只与单侧的向量产生相关, 与具体值无关

上面的东西,看上去搞个前缀和,再for(len)for(左端点i)for(最大值下标pos) 就搞完了

重复

基本的东西有了,下面是精确计算值

正如上面的例子[1..2][3..4]

如果是1234 输出是(2,4)

如果是3412 输出也是(2,4)

而对于dp来说,一个是按照 第4位 开始划分,一个是按照第2位开始划分的. 有重复的问题

同样,对于[1..2][2..3] 来说

如果312 和 213 也会重复.分别是第1位和第3位最大进行讨论的, 而它们的输出都是(1,3)

注意, 这里 132 和231 不会重复统计

一个办法是容斥(本文不会提到

另一个就是发现其数学性质

当在[i..j] 中 pos是最大值的下标 且属于其中某个完整区间时

如果[i..pos-1] 中的最大值 在idx, 且idx和pos 在[i..j] 中不属于任何同一个完整区间, 那么 让idx变为 [i..j]中的最大值, pos改为次大值,总输出向量不变

证明

因为前面假设过, value[pos] > 所有左侧值 > 所有右侧值,所以pos最大,idx次大

交换以后,value[idx] > value[pos] > 其它左侧值 > 所有右侧值

按情况讨论区间

  1. pos右侧的所有区间,因为包含的内容全在右侧值中,所以都不受影响
  2. 包含pos的所有区间, 原本输出pos, 因为不包括idx,现在pos次大,所以依然输出pos
  3. pos左侧所有区间, 只有idx变大了,但对于所有左侧区间来说,相对顺序都没有变化, 所以左侧的也都没有变

所以总的向量没有变

以上证明了,如果[i..pos-1]中的最大值和pos在[i..j]中不属于同一个完整区间,那么会被重复统计. 所以

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

要改为

dp[i][j][p] = sum(dp[i][p-1][f(p)..p-1]) * sum(dp[p+1][j][p+1..j])

f(p) = 最小的 在[i..j]中和p属于同一个完整区间的

不漏从dp过程中已经保证了,上面我们只是提到了去重,而并不能说明所有重复都没有了.下面证明所有重复都没有了

即是证明 任何输出向量,只会被至多统计一次

不妨设某个 输出被统计了两次.

根据统计过程, 如果它在首次被不同的最大值下标统计了,那么

  1. 这两个下标属于同一个区间,和下标是最大值矛盾,一个区间只有一个下标是最大值
  2. 这两个下标不属于任何同一个区间,那么根据上面的变化, 只会统计在左侧为更大值

代码

基于 heno239 的代码 https://atcoder.jp/contests/agc056/submissions/27693073

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define per(i, a, n) for (ll i = n - 1; i >= a; i--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

struct modint {
  int n;
  modint() : n(0) { ; }
  modint(ll m) {
    if (m < 0 || mod <= m) {
      m %= mod;
      if (m < 0)
        m += mod;
    }
    n = m;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) {
  return a.n == b.n;
}
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod)
    a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0)
    a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((ll)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) {
  return a += b;
}
modint operator-(modint a, modint b) {
  return a -= b;
}
modint operator*(modint a, modint b) {
  return a *= b;
}
modint operator^(modint a, ll n) {
  if (n == 0)
    return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2)
    res = res * a;
  return res;
}

ll inv(ll a, ll p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) {
  return a * modint(inv(b, mod));
}
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}

vector<int> vle[305];       // [r pos] = {l pos...} 区间右端点到左端点
modint dp[305][305][305];   // [l][r][x] = [l..r-1] 最大的是x的方案数, 其中不论l取值多少,x与[l,r-1]至少属于[l,r-1]中的一个完整区间
modint rdp[305][305][305];  // rdp[l][r][i] =  dp[l][r][0..i-1] 的前缀和

// 默认 全false, 右端点在[l+1..r]之间，长度 <= r-l 的区间是否存在
bool exi[305][305];

int cl[305];  // 计算过程中[l..r-1] 中, cl[i] = 与i同属于完整区间属于[l..r-1]的 最左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l - 1);
  }
  // 同样右端点 左端点从小到大, 方便后面二分找满足条件的左端点
  rep(i, 0, n + 1) sort(all(vle[i]));
  rep(len, 1, n + 1) {    // 枚举 长度[1..n], 因为每次划分是 左右两个更短的范围
    rep(r, len, n + 1) {  // 右端点从小到大 [len..n]
      int l = r - len;    // 左侧端点 = 右端点-长度
      int nw = r; // 遍历过程中,当前属于[l..r-1]的完整区间的最小左端点
      per(j, l + 1, r + 1) {  // j（右端点）从大到小 [l+1,r] 范围内的每个右端点
        // 第一个大于或等于某个元素的位置, 二分查找
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) {  // [nw,j] 区间小于等于 len
          nw = min(nw, vle[j][t]);
        }
        // 右端点 [j..r] 中的区间的最小左端点, 不存在的情况 r > j - 1
        cl[j - 1] = nw;
      }
      if (nw == r) {  // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;  // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r) {    // [l..r-1]
        if (x < cl[x])  // 不存在 [l,r] 之间的小区间 包含 坐标x
          continue;
        // [l..x-1]x[x+1..r-1]
        // 存在右端在 [l+1..x], 长度小于 x-l 的区间,
        // sl = sum{dp[l][x][cl[x]..x-1]}
        // 注意这里, 当[l..x-1]不存在时是1, 而[l..x-1]存在时,因为防止重复统计可能[cl[x]..x-1]是0
        modint sl = exi[l][x] ? rdp[l][x][x] - rdp[l][x][cl[x]] : (modint)1;
        // 存在右端在 [x+2..r], 长度小于 r-x-l 的区间,
        // sr = sum{dp[x+1][r][x+1..r-1]}
        // 而对于右侧 似乎可以直接判断前缀和是否非零,但实际上因为是取mod运算,可能为mod的倍数,所以还是需要一个exi的辅助数组
        modint sr =
            exi[x + 1][r] ? rdp[x + 1][r][r] - rdp[x + 1][r][x + 1] : (modint)1;
        dp[l][r][x] = sl * sr;  // [l,r-1]中 最大的下标为x, 方案数
        // 下面由此输出
        // printf("%d %lld %lld => %d %d\n",l,r,x,(int)sl,(int)sr);
      }
      rep(j, l, r) {
        // [l..r-1]
        // rdp[l][r][j] = dp[l][r][0..j-1] 前缀和
        rdp[l][r][j + 1] = rdp[l][r][j] + dp[l][r][j];
      }
    }
  }
  printf("%d", (int)rdp[0][n][n]); // [0,n-1] 最大下标[0..n-1]的方案数
  return 0;
}

例子

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
167
168
169
170
171
172
173
174
175
176
//
// [l          x-1]x[x+1          ]r
// x 是最大值
// dp[l][r][x] = 左边方案数 x 右边方案数, 其中右边的长度覆盖了x
//             = sum{dp[l][x][cl[x]..x-1]} * sum{dp[x+1][r][x+1..r-1]}
//             = x 是最大值，对左侧的影响当前 最近的是 cl[x]
//
//
// 012345678
//  xx
//   xxx
//     xxx
//      xx
//        xx
//
/*
9 5
2 3
3 5
5 7
6 7
8 9
*/
/*
l r x ==sl*sr
[l r) 左闭右开,所以 实际区间是[l..r-1]

len = 2
1 3 1 => 1 1
1 3 2 => 1 1

5 7 5 => 1 1
5 7 6 => 1 1

7 9 7 => 1 1
7 9 8 => 1 1

len = 3
0 3 1 => 1 1
0 3 2 => 1 1 (0不属于完整区间,所以没有 0 3 0

1 4 1 => 1 1
1 4 2 => 1 1 (虽然3和属于[2..4]的完整区间,但这里的区间是[1..3],3 不属于这之间的任何完整区间, 所以也没有 1,3,3

2 5 2 => 1 1
2 5 3 => 1 1
2 5 4 => 1 1

4 7 4 => 1 2 (首次包含关系 区间,一个[4..6]一个[5..6],右侧 = dp[5][7][5] + dp[5][7][6] = 1+1 = 2, 也就是[4..6] 最大值在4时,不影响右侧不包含它的区间,右侧有两种值
4 7 5 => 1 1
4 7 6 => 1 1

5 8 5 => 1 1
5 8 6 => 1 1

6 9 7 => 1 1
6 9 8 => 1 1

len = 4
0 4 1 => 1 1
0 4 2 => 1 1

1 5 1 => 1 3 (同 上面 4 7 4
1 5 2 => 1 1 (这个和下面两个都是 1 1, 但实际上有些不同, 下面两个的左边的1, 如果按照上面右侧的统计法,应该是 2 而不是1, 注意到上面算sl和sr是有区别的,一个是[cl[x]..x-1], 一个是[x+1..r], 如果一致应该是[l..x-1]而不是[cl[x]..x-1], 说面 左侧最大值, 一定要和x属于同一组,如果不同组, 让左侧更大,其它平移补位, 总输出不变. 所以下面两个都是1.
1 5 3 => 1 1
1 5 4 => 1 1 

2 6 2 => 1 1
2 6 3 => 1 1
2 6 4 => 1 1

3 7 4 => 1 2
3 7 5 => 1 1
3 7 6 => 1 1

4 8 4 => 1 2
4 8 5 => 1 1
4 8 6 => 1 1

5 9 5 => 1 2
5 9 6 => 1 2
5 9 7 => 0 1
5 9 8 => 0 1

len = 5
0 5 1 => 1 3
0 5 2 => 1 1
0 5 3 => 1 1
0 5 4 => 1 1
1 6 1 => 1 3
1 6 2 => 1 1
1 6 3 => 1 1
1 6 4 => 1 1
2 7 2 => 1 4
2 7 3 => 1 4
2 7 4 => 1 2
2 7 5 => 1 1
2 7 6 => 1 1
3 8 4 => 1 2
3 8 5 => 1 1
3 8 6 => 1 1
4 9 4 => 1 4
4 9 5 => 1 2
4 9 6 => 1 2
4 9 7 => 0 1
4 9 8 => 0 1

len = 6
0 6 1 => 1 3
0 6 2 => 1 1
0 6 3 => 1 1
0 6 4 => 1 1
1 7 1 => 1 12
1 7 2 => 1 4
1 7 3 => 1 4
1 7 4 => 1 2
1 7 5 => 1 1
1 7 6 => 1 1
2 8 2 => 1 4
2 8 3 => 1 4
2 8 4 => 1 2
2 8 5 => 1 1
2 8 6 => 1 1
3 9 4 => 1 4
3 9 5 => 1 2
3 9 6 => 1 2
3 9 7 => 0 1
3 9 8 => 0 1

len = 7
0 7 1 => 1 12
0 7 2 => 1 4
0 7 3 => 1 4
0 7 4 => 1 2
0 7 5 => 1 1
0 7 6 => 1 1
1 8 1 => 1 12
1 8 2 => 1 4
1 8 3 => 1 4
1 8 4 => 1 2
1 8 5 => 1 1
1 8 6 => 1 1
2 9 2 => 1 8
2 9 3 => 1 8
2 9 4 => 1 4
2 9 5 => 1 2
2 9 6 => 1 2
2 9 7 => 0 1
2 9 8 => 0 1

len = 8
0 8 1 => 1 12
0 8 2 => 1 4
0 8 3 => 1 4
0 8 4 => 1 2
0 8 5 => 1 1
0 8 6 => 1 1
1 9 1 => 1 24
1 9 2 => 1 8
1 9 3 => 1 8
1 9 4 => 1 4
1 9 5 => 1 2
1 9 6 => 1 2
1 9 7 => 0 1
1 9 8 => 0 1

len = 9
0 9 1 => 1 24
0 9 2 => 1 8
0 9 3 => 1 8
0 9 4 => 1 4
0 9 5 => 1 2
0 9 6 => 1 2
0 9 7 => 0 1
0 9 8 => 0 1
*/

改版

对于上面代码改了主要几个部分

把[l,r]改为左右都是闭区间了,不用考虑加减1的描述范围

把所有下标按照题目变成1-index而不是上面的0-index,因为这样也方便前缀和不用单独处理下标0

去掉了 大佬的modint, 假设没有modint的实现的情况下,直接加mod运算

https://atcoder.jp/contests/agc056/submissions/27743665

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define per(i, a, n) for (ll i = n - 1; i >= a; i--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

vector<int> vle[305];   // [r pos] = {l pos...} 区间右端点到左端点
ll dp[305][305][305];   // [l][r][x] = [l..r] 最大的是x的方案数, 其中不论l取值多少,x与[l,r]至少属于[l,r]中的一个完整区间
ll rdp[305][305][305];  // dp 前缀和
bool exi[305][305];     // 默认 全false, 在[l..r]之间 是否存在完整区间
int cl[305];            // 右端点 in [i..最右侧] = 区间的最小左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l);
  }
  rep(i, 1, n+1) sort(all(vle[i]));
  rep(len, 2, n+1) {              // 枚举 长度
    rep(r, len, n+1) {            // 右端点 从小到大
      int l = r - len + 1;        // 左侧端点 = 右端点 - 长度 +1
      int nw = r + 1;             // 左端点, 在[l..r] 中
      per(j, l, r + 1) {          // j（右端点）从大到小 [l,r] 范围内的每个右端点
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) nw = min(nw, vle[j][t]);
        cl[j] = nw;
      }
      if (nw == r+1) {            // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;           // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r+1) {            // [l..x-1]x[x+1..r]
        if (x < cl[x]) continue;  // 不存在 [l,r] 之间的小区间 包含 坐标x
        ll sl = exi[l][x-1] ? rdp[l][x-1][x-1] - rdp[l][x-1][cl[x]-1] : 1;
        ll sr = exi[x+1][r] ? rdp[x+1][r][r] - rdp[x + 1][r][x] : 1;
        dp[l][r][x] = ((sl%mod) * (sr%mod))%mod;    // [l,r-1]中 最大的下标为x, 方案数
      }
      rep(j, l, r + 1) rdp[l][r][j] = (rdp[l][r][j-1] + dp[l][r][j])%mod;
    }
  }
  printf("%lld", (rdp[1][n][n]+mod)%mod); 
  return 0;
}

参考

官方题解 https://atcoder.jp/contests/agc056/editorial/3045

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
E(线段树)

E

https://codeforces.com/contest/1609/problem/E

给你字符串只包含abc

给你q次操作,每次操作修改一个位置上的字符为’a’/‘b’/‘c’中的一种

每次操作后,问对于当前字符串,至少修改多少个字符,使字符串不包含abc子序列

子序列定义: 字符串任意位置删除任意个得到的剩余字符串

范围

字符串长度 1e5

询问次数 1e5

题解

一个可以过的方案是

seg(l,r,state) = 最少次数

其中l,r表示一个区间,通过线段树维护

state 是 5bit的状态分别对应a,b,c,ab,bc, 是否在区间中出现过

那么 线段树节点关系 是

f(根, mergestate(statel,stater)) = min(f(左节点,statel)+f(右节点,stater))

其中 产生abc的不更新 根节点状态

问题是 实现起来感觉有点卡常数 $q \cdot log(N) 32 \cdot 32 $ 的运算量 ,2464ms/3000ms 过的, 看到有些其它状态设计,状态如果更少会更快

tourist 300ms 过的

另一个想法是,实际上变成 [不存在a][不存在b][不存在c]的字符串就好了

那 操作代价(其实就是分别移除a,b,c) = count[a][0..i]+count[b][i+1..j]+count[c][j+1..end]

所以对count计算总是先a后b再c

变成了维护 f(l,r,startch, endch) = 最少代价

也就是 在区间[l,r]上 起始位置是计算startch,结束位置是计算endch

这样状态数最多3x3,根据a,b,c的顺序, 真实有效的只有6 个, 计算代价 常数就小很多

代码(前一种)

https://codeforces.com/contest/1609/submission/137409899

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
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = (i & (1 << (s[pos] - 'a'))) ? 0 : INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos])
      continue;
    // 一次修改
    rep(i, 1, (1 << 5)) {
      if (i & (1 << (ch - 'a'))) {  // 包含该bit
        t[o][i] = min(t[o][i], 1);
      }
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}

可能包含改成恰好包含快了不少

https://codeforces.com/contest/1609/submission/137444815

1216 ms/3000 ms

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
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos]){
      t[o][1<<(ch-'a')] = 0;
    }else{
      t[o][1<<(ch-'a')] = 1;
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
D(树上DP,子树点乘代价合并,总代价为n方), E(细节题，不会依然不会)

D

https://atcoder.jp/contests/arc130/tasks/arc130_d

给一个树,对节点赋值1~n,两两互不相同,

限制:树上的点要么小于它直接相邻所有点的值,要么大于它直接相邻所有点的值

求方案数.

题解

显然任意选一个为根, 大于和方案和小于的方案对称性,可以只算一个然后乘2

也可以,看成二分图,但是是求满足拓扑序的赋值方案数

注意到大于和小于关系,只需要颠倒就能实现,所以这里我们只讨论 根节点大于所有直接相邻的子节点

我们考虑树上DP

状态设计为 ans[i][j] = 节点i在它和它的所有子树节点中,排序从小到大刚好为j的方案数

对于一个选定的节点,有子树T1,T2,T3,T4,…

设它们的根节点为r1,r2,r3,r4,…

设它们的节点个数为s1,s2,s3,s4,…

那么, 我们考虑维护合并这些子树.

因为 我们这里考虑的是 当前节点要大于所有子树的根节点

所以 合并的时候维护 dp[i] = 已合并的子树中,根节点最大值恰好为i的方案数

以T1和T2为例

分成两种, T1的根更大,和T2的根更大(可以对称处理)

下面讨论 T1根更大

设r1在T1 中的位置为i(1-index)

合并后的序列为(i-1个T1中的点 和 j个T2中的点) r1 ((s1-i)个T1中的点 和 (s2-j)个T2中的点)

注意在两个子树分别的内部,顺序已经固定, 所以只有交叉的顺序不定

方案为 $C((i-1)+j,i-1) \cdot C((s1-i)+(s2-j),s1-i) \cdot ans[r1][i]$

再考虑, T2中的r2的位置,因为T1根更大,所以r2只能在前j个中

$dp[i+j] += C(i+j-1,i-1) \cdot C(s1+s2-i-j,s1-i) \cdot ans[r1][i] \cdot (ans[r2][1]+\cdots +ans[r2][j])$

右边的和可以前缀和O(1),

组合数可以预处理递推O(1),

所以

我们通过 循环一遍T1的节点数,再一遍T2的节点数数,就能得到dp, 每个+= 是O(1)

这里总代价n2,而我错误估计以为n3就没写,哭了

乍看上去,所有节点处理一次,每个节点是子树之间合并,个数的乘积是n3复杂度

实际上,考虑贡献, 一次合并子树的两个子树节点个数乘积大小的代价, 相当于,两个子树之间的节点建立一个配对关系.又因为任何两个节点至多建立两次(讨论根更大)关系,所以总代价为$O(n^2)$

代码

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 998244353
#define rep(i, a, n) for (ll i = a; i < n; i++)
 
int n;  // <=3000
vector<int> p2[3010]; // 树连接关系
// [node i][从小到大第j个] = 方案数
vector<vector<ll> > ans(3010, vector<ll>(1, 0));
 
ll qC[3010][3010]; // 预处理组合数
 
void mergeTable(const vector<ll>& arr0,
                const vector<ll>& arr1,
                vector<ll>& res) {
 
  vector<ll> presum(arr1.size(), arr1[0]);
  rep(i, 1, arr1.size()) { presum[i] = (arr1[i] + presum[i - 1]) % MOD; } // 前缀和
  // arr0 根更大 , root(arr0) > root(arr1)
  // 虽然每次代价是 子树大小之和 x arr0.size()，看起来是三次方，
  // 但实际上,从贡献角度思考 总代价n2
  rep(i, 0, arr0.size()) {
    rep(j, 0, arr1.size()) {
      // arr0: i 个 左侧， arr0.size()-i-1 个 右侧
      // arr1: j+1 个 左侧, arr1.size()-j-1 个右侧
      // res: i+j+1 个左侧, arr0.size()+arr1.size()-i-j-2 个右侧
      // presum = presumof arr1
      // 就是表达式 加上了MOD
      (res[i + j + 1] +=
       (((arr0[i] * qC[i + j + 1][i]) % MOD *
         qC[arr0.size() + arr1.size() - i - j - 2][arr0.size() - i - 1]) %
        MOD * presum[j]) %
       MOD) %= MOD;
    }
  }
}
 
void dfs(int idx, int fa/*父节点*/, int g/*大于小于关系*/) {
  vector<ll> dp = {};  // [最大的子树 根节点 位置] = 方案数
  for (auto item : p2[idx]) {
    if (item == fa)
      continue;
    dfs(item, idx, g ^ 1);
    if (g) {  // 逆向
      // 只用一次也不需要恢复了
      reverse(ans[item].begin(), ans[item].end());
    }
    if (!dp.size()) {
      dp = ans[item];
    } else {
      vector<ll> res(dp.size() + ans[item].size(), 0);
      mergeTable(dp, ans[item], res); // dp 根更大
      mergeTable(ans[item], dp, res); // ans[item] 根更大
      dp = res;
    }
  }
  ans[idx] = vector<ll>(dp.size() + 1, 0);
  if (dp.size() == 0) {
    // 叶子节点
    ans[idx][0] = 1;
  } else {
    ll cnt = 0;
    rep(i, 0, dp.size() + 1) { // 实际上也是前缀和, 当前节点 大于 所有子树根节点
      ans[idx][i] = cnt;
      (cnt += dp[i]) %= MOD;
    }
  }
  if (g) {
    reverse(ans[idx].begin(), ans[idx].end());
  }
}
 
int main() {
  rep(i, 0, 3001) {
    rep(j, 0, i + 1) {
      qC[i][j] = j == 0 ? 1 : (qC[i - 1][j] + qC[i - 1][j - 1]) % MOD;
    }
  }
 
  scanf("%d", &n);
  rep(i, 0, n - 1) {
    int u, v;
    scanf("%d %d", &u, &v);
    p2[u].push_back(v);
    p2[v].push_back(u);
  }
  dfs(1, 0, 0);
  ll res = 0;
  rep(i, 0, n) { (res += ans[1][i]) %= MOD; }
  printf("%lld\n", (2 * res) % MOD); // 大于小于对称性 乘2
  return 0;
}

submissions

官方题解

总结

  1. 可以当作知识点的: 子树全部 节点数相乘的代价,总代价是$O(n^2)$
  2. 复杂度也可以在纸上不要脑补

E

https://atcoder.jp/contests/arc130/tasks/arc130_e

一个数组，每次选最小值中的一个+1，记录下标。

形成了一个下标数组。

现在给你下标数组，求满足下标数组的字典序最小的原数组

题解

题目样例为例

1 1 4 4 2 1

如果 我们能给他们分组

1 | 1 4 | 4 2 1

那么，很容易知道合法的最小结果

1 (操作前大小为1)| 1 4 (操作前大小为2) | 4 2 1 (操作前大小为3)

我们只关心

1 | 1 4 (操作后所有为3)

所以原数组为

3-2 3-0 3-0 3-1 = 1 3 3 2

所以核心问题变成去找这个层之间的分割线

见下面代码中的注释

last(pos) = 这个位置值相同的值的上一个位置

cur[value] = 位置，辅助计算last的数组

cnt 当前层的个数

mx 上一层至少的结束的位置/当前层至少的起始位置

f(pos)= pos是有效的层级分割值，或者-1

代码

jiangly 大佬的代码 加的注释的

https://atcoder.jp/contests/arc130/submissions/27614814

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
 
// 若按照 最后一次出现的顺序排序1~n
// 最优结果的起始最小值一定是1
// 那么所有最优结果 在所有操作后 一定满足 AN-1<=A1<=A2<=A3<=...<=AN
 
int main() {
  int N, K;
  scanf("%d %d", &N, &K);
 
  vector<int> i(K);
  rep(k, 0, K) {
    scanf("%d", &i[k]);
    i[k]--;  // (0-index)
  }
 
  vector<int> last(K);  // 这个位置上同一个数上一次出现的位置 last[pos] = oldpos
  vector<int> cur(N, -1);  // 最后一次出现的位置 cur[value] = pos
  rep(k, 0, K) {
    last[k] = cur[i[k]];
    cur[i[k]] = k;
  }
 
  vector<int> f(K + 1, 0);  // 相当于找有效分割线 = 分割线的层级，从0开始
  int cnt = 0;
  int mx = -1;
  rep(k, 0, K) {
    mx = max(mx, last[k]);  // 更新最近上一组数 的最大下标
    if (last[k] == -1) {    // 当前值首次出现
      cnt++;                // 属于组的个数+1
    }
    // -1 无效值
    // 最大位置 和 当前位置之间个数小于 cnt 则 无效
    // 上一个位置无效则 无效,
    // 因为如果当前是分割线，那么当前到上一个分割线的距离一定恰好是cnt
    f[k + 1] =
        (mx >= k + 1 - cnt || f[k + 1 - cnt] == -1) ? -1 : 1 + f[k + 1 - cnt];
  }
 
  int c = -1;    // 分割最小层数
  int len = -1;  //
  rep(k, mx + 1,
      K + 1) {  // 对于最后一组分割，最后一组里各不相同，且组长度 <= cnt
    // 上一个分割线有效
    // 尚无合法的，或当前层数小于等于 上一个方案
    if (f[k] >= 0 && (c == -1 || c >= f[k])) {
      c = f[k];  // 更新层数
      len = k;   // 最后一组的起点位置
    }
  }
  // 没有有效的最后一组
  if (c == -1) {
    cout << "-1\n";
    return 0;
  }
 
  // 从最后的结果反推初始值,
  // 这里排除了最后一组，所以在最后一组之前，所有值是相等的
  vector<int> A(N, c + 1);  // 最后的结果
  rep(k, 0, len) { A[i[k]]--; }
  rep(i, 0, N) { printf("%d%c", A[i], " \n"[i == N - 1]); }
 
  return 0;
}

总结

跳表什么都会，但是能把细节分析出来，感觉是熟练度而不是什么缺失的知识点。属于这次学会了，下次可能还是不会的题。

發表於 更新於 分類於 Disqus： 文章字數： 995 所需閱讀時間 ≈ 3 分鐘
拉格朗日反演

Lagrange inversion theorem 拉格朗日反演

解决的问题

给定F(x), 找G(x) 使得 G(F(x)) = x, 也就是找反函数

这里有一点要用到,但是没有证明的是 $G(F(x)) = x$ 则 $F(G(x)) = x$, 只能说在$F(x)$的值域内$F(G(F(x)) = F(x)$即$F(G(x)) = x$可以证明, 但在值域外不知道如何证明…

结论

如果$F,G$满足

  • 0次项系数均为0: $[x^0]F(x)=[x^0]G(x)=0$
  • 1次项系数均非0: $[x^1]F(x) \neq 0,[x^1]G(x) \neq 0$

那么 $\lbrack x^n \rbrack G(x)^k = \frac{k}{n} \lbrack x^{n-k} \rbrack \left(\frac{x}{F(x)}\right)^n.$

$\lbrack x^n \rbrack G(x) = \frac{1}{n} \lbrack x^{n-1} \rbrack \left(\frac{x}{F(x)}\right)^n.$

证明

辅助lemma: 任何 $F(0)=0$(0次系数为0), $F’(0)\neq 0$ (?存在非0次的非0系数?????), 有对于$\forall k \in \mathbb{Z}$

$\lbrack x^{-1} \rbrack F’(x) F(x)^k = \lbrack k = -1\rbrack$

即$k=-1$时$-1$次系数为$1$,否则$-1$次系数为$0$

证明lemma:

对于$k\neq -1$, 显然求导法则$\displaystyle F’(x) F(x)^k = \frac{\left ( F(x)^{k+1} \right)’}{k+1}$, 所以$\le 0$的x的幂次的系数都是0

对于$k = -1$, $F(x) = \sum_{i>0} a_i x^i$

$\displaystyle \frac{F’(x)}{F(x)} = \frac{a_1+2a_2x+3a_3x^2+\cdots}{x(a_1+a_2x+a_3 x^2+\cdots}= x^{-1} \frac{1 + 2\frac{a_2}{a_1}x + \cdots}{1 + \frac{a_2}{a_1}x + \cdots}$

也就是右侧这个分式除完以后是$1+k_1x+k_2x^2+\cdots$的样子, 因此 -1 次方的系数是 1, lemma 证毕.

这里 注意到 像$\frac{1}{1-x}$这种 对应的 $x^{-1}$的系数是0,因为它虽然写在分母上，但实际是泰勒展开到正，而$\frac{1}{x}$ 是不能在0点泰勒展开成正的?而去查 1/x的泰勒展开，都是在点1的展开

因此$G(F(x))^k = x^k,k\ge 1,k\in \mathbb{Z}$, 的$G$ 满足条件

$(\sum_{i} ([x^i]G^k(x))F(x)^i)’\cdot F’(x) = kx^{k-1}$ ( 同时对$x$求导, 以及按位展开式 $G^k(x)=\sum_{i}([x^i]G^k(x))x^i$

展开$\sum_i i(\lbrack x^i\rbrack G^k(x) ) F(x)^{i-1} F’(x) = kx^{k-1}$, (基本的求导法则 $(ax^i)’ = iax^{i-1}$, 注意到前两项都是常系数 而非生成函数

$\sum_{i} i (\lbrack x^i \rbrack G^k(x)) F^{i-1-n}(x) F’(x) = kx^{k-1}F^{-n}(x).$ ( 同乘上$F^{-n}$, 这里想用lemma, 也就是$[x^{-1}]F^?(x)F’(x)$, 同时最终目标是$[x^?]G(x)$

$\lbrack x^{-1}\rbrack \left(\sum_{i} i (\lbrack x^i \rbrack G^k(x)) F^{i-1-n}(x) F’(x)\right) = \lbrack x^{-1}\rbrack \left(kx^{k-1}F^{-n}(x)\right).$ (提取$-1$次项目的系数

因为左侧$i (\lbrack x^i \rbrack G (x))$ 整个都是系数, 以及上面的lemma, 左侧只有$i-1-n=-1$即$i=n$时, $[x^{-1}]F^{i-1-n}(x)F’(x)$生成系数的内容才为$1$,其它则是$0$,

$n[x^n]G^k(x) = [x^{-1}]kx^{k-1}F^{-n}(x)$

变形一下,就有了最初要证明的$\displaystyle \lbrack x^n \rbrack G(x) = \frac{k}{n} \lbrack x^{n-k} \rbrack \left(\frac{x}{F(x)}\right)^n.$

这玩意 百科上说建立了函数方程和幂级数之间的联系 !!??

使用示例: 卡特兰数Catalan number

$c_0 = 1$

$c_{n+1} = \sum_{i=0}^n c_{i} \cdot c_{n-i}$

令$C$为以卡特兰数 1,1,2,5,14为系数的生成方程

令$F(x) = C(x) - 1$, 保证0次项系数为0, 1次系数非0

那么$F(x) = x(F(x)+1)^2$ , 根据卡特兰数本身推导的定义的到的

令$G(x) = \frac{x}{(x+1)^2}$

那么有$G(F(x)) = \frac{F(x)}{(F(x)+1)^2} = x$

那么$c_n$ 就有了

因此

$\begin{aligned} [x^n]F(x) &= \frac{1}{n} \lbrack x^{n-1} \rbrack \left(\frac{x}{G(x)}\right)^n \\ &= \frac{1}{n} \lbrack x^{n-1} \rbrack (x + 1)^{2n} \\ &= \frac{1}{n} \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}, \end{aligned}$

相关

https://atcoder.jp/contests/abc222/editorial/2765

abc222ex

拉格朗日反演

超理论坛 拉格朗日反演

洛谷 拉格朗日反演

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
D Sum of Min of xor(分治,bits,xor)

D

https://atcoder.jp/contests/arc127/tasks/arc127_d

题目大意,(atcoder 的这个题没有“背景”，直接去看原题，就是题意

给等长数组A,B, 对于两两坐标i,j, 计算$min(A_i \oplus A_j, B_i \oplus B_j )$

求所有min的和

范围

$n \leq 250000 , A_i,B_i < 2^{18}$

想

先做一些简单的分析,N 有点大，$N^2$的话肯定超时, 那么基本范围是$N , N log(N)$ 左右的

$2^{18} = 262144$

min(x,y)+max(x,y) = x+y

一些 $\oplus$ 的常见知识, $(A \oplus B) = (A + B) \bmod 2$, 其中加和模采取 每位不进位且允许超过2的任意值, 这个好处是能计数

例如 5 = 101,7=111, 9 = 1001

$(0,1,0,1)+(0,1,1,1)+(1,0,0,1) = (1,2,1,3) $

$(1,2,1,3) \bmod 2 = (1,0,1,1) $

所以$5 \oplus 7 \oplus 9 = 11$, 同时我们知道最高位1个1，2个0

a < b 那么 $a \oplus b$ 的最高位1出现在b

反过来

$a \oplus b$ 最高位出现在b , 那么 a < b

(归纳法易证

$a \oplus (b+c+d+e+\cdots) =$ 后面部分通过上面按位不进位加和统计的每一位 0 个数 或1个数，在看与a对应位是否相等

通过前缀和或者扫描记录当前， 长度为n的数组的两两$\oplus$的和 的时间复杂度O(N) 就能完成

综上，我们可以直接算出 min， 也可以去算max然后拿总和减去min

算法

把所有数看成18位，不足高位补零

我们 关心$(A_i \oplus A_j) \oplus (B_i \oplus B_j) $ 的最高位的bit从哪里来，这样我们就知道哪个最大了

$(A_i \oplus A_j) \oplus (B_i \oplus B_j) = (A_i \oplus B_i) \oplus (A_j \oplus B_j) $

令$C_i = A_i \oplus B_i$

w = 18

把$C_i$分类成两组, 一组是 第$w$位为$1$的，另一组是$w$位为$0$的

每组内，循环这个方法并且w-1

对于组之间的，

$C_i$的$w$位为1, $C_j$的$w$位为0 , 对于高于w位的，因为通过上面的分治，两边保持一致，也就是$\oplus$以后都是0了不需要考虑

对于$w$位为1 里面我们还可以分类为 $A_i$ 的w位是0或1两类

$G_{x,y}$ w位是x，A的w位是y

$G_{1,0},G_{0,0}$, 高位1来自B的$\oplus$

$G_{1,0}, G_{0,1}$, 高位1来自A的$\oplus$

$G_{1,1}, G_{0,0}$, 高位1来自A的$\oplus$

$G_{1,1}, G_{0,1}$, 高位1来自B的$\oplus$

也就是分组的时间复杂度就是$2^L$

下面考虑

$G_{i_0,i_1,i_2,\cdots} $ 与 $G_{j_0,j_1,j_2,\cdots}$ 中 如果高位来自A的$\oplus$

那么贡献为

$ \sum B_{i_?} \oplus B_{j_?}$

也就是，上面想求总和提到过的方法, 通过按位计数，拿着一块求和的单个复杂度为$O(L\cdot size(G))$, 总复杂度为$O(L\cdot N)$

然后注意处理$C_i$ 一致的组，这样的组里面，两两的异或值相同, 也需要上面的按位计数的求和

Code

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>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back

int A[250010];
int B[250010];

const int L = 18;

// 两两xor和 A[i0[?]]
ll xorSum(vector<int> & i0){
  if(i0.size() == 0)return 0;
  vector<int> bits = vector<int>(20,0);
  ll ans = 0;
  rep(i,0,i0.size()){
    if(i > 0){
      rep(b,0,L){
        ans += ((A[i0[i]]>>b) % 2)?
          ((ll)1 << b) * (i - bits[b]):
          ((ll)1 << b) * (bits[b]);
      }
    }
    rep(b,0,L){
      bits[b]+=(A[i0[i]]>>b)%2;
    }
  }
  return ans;
}

// 任意左Arr[i0[?]] xor 任意右Arr[i1[?]] 的和
ll xorSum(vector<int> & i0,vector<int> & i1, int * Arr){
  if(i0.size() == 0 || i1.size() == 0)return 0;
  vector<int> bits = vector<int>(20,0);
  rep(i,0,i0.size()){
    rep(b,0,L){
      bits[b]+=(Arr[i0[i]]>>b)%2;
    }
  }
  ll ans = 0;
  rep(i,0,i1.size()){
    rep(b,0,L){
      ans += ((Arr[i1[i]]>>b) % 2)?
        ((ll)1 << b) * (i0.size() - bits[b]):
        ((ll)1 << b) * (bits[b]);
    }
  }
  return ans;
}

// pwr 以上的位， idxs里面 A[i]^B[i] 两两相等
ll f(int pwr,vector<int> & idxs){
  if(pwr < 0){
    // (Ai xor Aj) xor (Bi xor Bj) = (Ai xor Bi) xor (Aj xor Bj) = 0
    return xorSum(idxs);
  }
  // groups
  vector<int> gC[2] = {{},{}}; // w 位的 C
  vector<int> gCA[2][2] = {{{},{}},{{},{}}};// w 位 C 和 A的 零一
  for(auto i:idxs){
    int C = A[i]^B[i];
    gC[(C>>pwr)%2].pb(i);
    gCA[(C>>pwr)%2][(A[i]>>pwr)%2].pb(i);
  }
  ll ans = 0;
  rep(i,0,2){
    if(gC[i].size() < 2) continue;
    ans += f(pwr-1,gC[i]);
  }
  // bit
  rep(bA0,0,2){
    rep(bA1,0,2){
      ans += (bA0 ^ bA1)?
        xorSum(gCA[0][bA0],gCA[1][bA1], B):
        xorSum(gCA[0][bA0],gCA[1][bA1], A);
    }
  }
  return ans;
}

int main(){
  int n;
  cin>>n;
  rep(i,0,n){
    scanf("%d",A+i);
  }
  rep(i,0,n){
    scanf("%d",B+i);
  }
  vector<int>idxs;
  rep(i,0,n){
    idxs.pb(i);
  }
  printf("%lld",f(L,idxs));
  return 0;
}

Ref

https://atcoder.jp/contests/arc127/editorial/2697

0%