## 和除或
#容斥 #组合数学
首先，我们通过观察可以猜测 $f(X,Y)=\left\lceil{\cfrac{X+Y}{X|Y}}\right\rceil$ 的值不是 $1$ 就是 $2$，很明显我们猜对了因为打表找不出反例，因此我们需要进行思考什么情况下取 $1$ 什么情况下取 $2$。
由于这里是向上取整，因此取 $1$ 情况只有 $X+Y=X\operatorname{|}Y$ 了，也就是 $X$ 和 $Y$ 的 $1$ 位没有相交的，即 $X\operatorname{\&}Y=0$。其余所有 $X\operatorname{\&}Y\ne 0$ 的场景，都是取的 $2$。原函数的值转化为 $1+[X\operatorname{\&}Y\ne 0]$。
$
\begin{aligned}
\sum_{1\le i<j\le n}f(a_i,x_j)&=\sum_{1\le i<j\le n}1+\sum_{1\le i<j\le n}[X\operatorname{\&}Y\ne 0] \\
&=\cfrac{n(n-1)}{2}+\sum_{1\le i<j\le n}[X\operatorname{\&}Y\ne 0]
\end{aligned}
$
后面的不好计算，因此使用容斥原理。令 $P_k$ 表示第 $k$ 位都为 $1$ 的集合，我们要求的是 $|\cup_k P_k|$，根据容斥原理
$
|\cup_k P_k|=\sum|P_k|-\sum|P_k\cap P_l|+\sum|P_k\cap P_l\cap P_m|
$
令 $g(x)$ 表示满足 $a_i\operatorname{\&}x=x$ 的 $i$ 的数量，那么所有满足 $[a_i\operatorname{\&}a_j\ne 0]$ 的数对的数量为
$
\sum_{x\ne 0}(-1)^{\text{popcount(x)}-1}\times \cfrac{g(x)\times g(x)-1)}{2}
$
因此我们只需要预先计算出 $g(x)$（即多少个 $a_i$ 的子集是 $x$ 的数量）就行了。
```cpp
#include <iostream>
#include <map>
using namespace std;
using LL = long long;
const LL kMaxN = 2e5 + 5;
LL a[kMaxN], t, n, ans;
map<LL, LL> f, dp;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
f.clear(), dp.clear();
for (LL i = 1; i <= n; i++) {
cin >> a[i];
f[a[i]]++;
}
ans = n * (n - 1) / 2;
for (auto &i : f) {
for (LL j = i.first; j; j = (j - 1) & i.first) {
dp[j] += i.second;
}
dp[0] += i.second;
}
for (auto &i : dp) {
if (!i.first) {
continue;
}
if (__builtin_popcount(i.first) % 2) {
ans += i.second * (i.second - 1) / 2;
} else {
ans -= i.second * (i.second - 1) / 2;
}
}
cout << ans << '\n';
}
return 0;
}
```
## 礼物
#贪心
既然是不能有连续的长度为 $k$ 的段，那么我就找到第一个连续的长度为 $k$ 的段的位置 $l$，然后往右枚举 $r$，判断一下替换 $[l,r]$ 能否满足条件即可。
至于判断是否满足条件还是有一点复杂的，过程如下：
- $s_l\ne s_r$，否则 $s_r$ 反转过去仍然能够组成长度为 $k$ 的连续段；
- 反转的区间 $[l,r]$ 内部不能有长度为 $k$ 的连续段，因为反转操作不会破坏反转区间内的连续段；
- 如果 $s_l=s_{r+1}$ 的话，那么 $l$ 往后的连续段的长度加上 $r+1$ 往后的连续段的长度要小于 $k$，因为 $l$ 反转过去后会和 $r+1$ 拼起来。
如果以上条件都满足，那么就是有解的。
欸，但我们提交上去就会发现大样例 wa 了，被 `7 4 AABBBBB` 卡了，因为我们总是往后反转而不是往前反转，但是重新写一遍又太复杂了。
于是我就正着跑一遍贪心，反着跑一遍贪心，这样子就可以通过所有数据了，欢迎来 Hack。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int kMaxN = 2e5 + 5;
int suf[kMaxN], len[kMaxN], t, n, k;
char s[kMaxN];
bool check() {
int cnt = 1;
suf[n + 1] = 1;
len[n + 1] = 0;
for (int i = n; i >= 1; i--) {
if (s[i] == s[i + 1]) {
cnt++;
} else {
cnt = 1;
}
suf[i] = suf[i + 1] && cnt < k;
len[i] = cnt; // i 往后的相同段的长度
}
if (suf[1]) {
return 1;
}
cnt = 1;
bool ans = 0;
s[n + 1] = 'C';
for (int i = 2; i <= n; i++) {
if (s[i] == s[i - 1]) {
cnt++;
} else {
cnt = 1;
}
if (cnt >= k) {
// 反转 [i, j]
cnt = 1;
int pre = 1;
bool lead = 1;
for (int j = i + 1; j <= n; j++) {
if (s[j] == s[j - 1]) {
cnt++;
} else {
cnt = 1;
}
if (lead && s[j] == s[i]) {
pre++;
} else {
lead = 0;
}
if (cnt >= k) {
break;
}
if (s[j] == s[i]) {
continue;
}
if (suf[j + 1] && (s[i] != s[j + 1] || pre + len[j + 1] < k)) {
return 1;
}
}
break;
}
}
return 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> k >> (s + 1);
bool ans = check();
reverse(s + 1, s + n + 1);
ans |= check();
cout << (ans ? "YES" : "NO") << '\n';
}
return 0;
}
```
## 连续段的价值
#二分 #状压dp
首先答案肯定是有单调性的，如果 $ans$ 是答案的话 $ans-1$ 也可以满足，因此我们可以考虑使用二分答案。注意到 $k\le 17$，这很有状压的嫌疑。
接下来我们考虑如何对我们二分的值进行判断。假设当前二分的答案为 $x$，那么我们设 $dp_{i,j}$ 表示为当前已经满足条件的字符集位为 $i$，字符串的长度能否为 $j$，转移就是枚举一个新的字符在 $i$ 里面没出现的，然后往后遍历原始字符串找到一个长度为 $x$ 的连续段进行转移，判断函数时间复杂度 $\mathcal O(2^k k n^2)$，非常恐怖。
考虑预处理转移部分，令 $e_{i,j}$ 表示为 $i$ 字符在第 $j$ 个字符开始，往后至少要到 $e_{i,j}$，在 $[j,e_{i,j}]$ 这个段里面有长度为 $x$ 的连续 $i$ 字符段。$e$ 可以 $\mathcal O(kn)$ 预处理出来，转移就变成 $\mathcal O(1)$ 的了，判断函数时间复杂度将为 $\mathcal O(2^k kn)$，可以通过 $75$ 分。
接下来优化 dp 状态。其实我们没必要存储状态 $j$，因为对于所有 $dp_{i,j}$ 值为 $1$ 的当中，$j$ 越小的状态是越优的，而且经过相同字符的转移时不会比 $j$ 更大的状态更劣，因此我们将 $j$ 拆掉作为 $dp_i$ 的一个最优化属性。
设 $dp_i$ 表示为当前已经选择的字符集为 $i$，至少需要 $dp_i$ 长度的前缀。转移时枚举字符 $j$，由 $dp_i\rightarrow dp_{i\operatorname{|}j}+e_{j,dp_i}$。判断函数时间复杂度 $\mathcal O(kn+2^k k)$，总时间复杂度 $\mathcal O\left(\left(n+2^k\right)k\log_2\left(\cfrac{n}{k}\right)\right)$。
```cpp
#include <iostream>
using namespace std;
const int kMaxN = 2e5 + 5, kMaxK = 18;
int e[kMaxK][kMaxN], dp[1 << kMaxK], n, k, ans;
char s[kMaxN];
bool check(int x) {
for (int i = 0; i < k; i++) {
e[i][n + 1] = n + 1;
for (int j = n, cnt = 0; j >= 1; j--) {
if (s[j] == '?' || s[j] == 'a' + i) {
cnt++;
} else {
cnt = 0;
}
if (cnt >= x) {
e[i][j] = j + x - 1;
} else {
e[i][j] = e[i][j + 1];
}
}
}
fill(dp, dp + (1 << kMaxK), 1e9);
dp[0] = 0;
for (int i = 0; i < (1 << k); i++) {
for (int j = 0; j < k; j++) {
if (!(i & (1 << j)) && dp[i] < n) {
dp[i | (1 << j)] = min(dp[i | (1 << j)], e[j][dp[i] + 1]);
}
}
}
return dp[(1 << k) - 1] <= n;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> (s + 1);
for (int l = 0, r = n / k; l <= r; ) {
int m = (l + r) / 2;
if (check(m)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
cout << ans << '\n';
return 0;
}
```
## 送外卖
#线段树 #树状数组
本题我写的是暴力。
- 对于子任务 1，模拟蜗蜗的送餐操作。最初时间戳 $tm=x_l$，每次往后送餐 $tm\gets tm+t_i$，但是如果时间太早了就要等 $tm\gets \max(tm, x_{i+1})$，如果 $tm>y_{i+1}$ 就是超时了。
- 对于子任务 3，用树状数组维护 $t_i$ 的区间和，如果区间内 $t_i$ 的和超过了任意 $y-x$，那么就是超时了。
```cpp
#include <iostream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e6 + 5;
LL l[kMaxN], r[kMaxN], a[kMaxN], tr[kMaxN], t, n, q;
bool same() {
for (int i = 2; i <= n; i++) {
if (l[i] != l[i - 1] || r[i] != r[i - 1]) {
return 0;
}
}
return 1;
}
void modify(int x, int y) {
for (; x <= n; x += x & -x) {
tr[x] += y;
}
}
int query(int x) {
int res = 0;
for (; x; x -= x & -x) {
res += tr[x];
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> l[i];
}
for (LL i = 1; i <= n; i++) {
cin >> r[i];
}
for (LL i = 1; i < n; i++) {
cin >> a[i];
}
cin >> q;
if (n <= 2000 && q <= 2000) {
for (LL o, p, x, y; q; q--) {
cin >> o;
if (o == 0) {
cin >> x >> y;
LL p = l[x], ans = 1;
for (LL i = x; i < y; i++) {
p = max(l[i + 1], p + a[i]);
if (p > r[i + 1]) {
ans = 0;
break;
}
}
cout << (ans ? "Yes" : "No") << '\n';
} else if (o == 1) {
cin >> x >> y;
a[x] = y;
} else if (o == 2) {
cin >> p >> x >> y;
l[p] = x;
r[p] = y;
}
}
} else if (same()) {
fill(tr + 1, tr + n + 1, 0);
for (LL i = 1; i <= n; i++) {
modify(i, a[i]);
}
for (LL o, p, x, y; q; q--) {
cin >> o;
if (o == 0) {
cin >> x >> y;
cout << (query(y - 1) - query(x - 1) <= r[y] - l[x] ? "Yes" : "No") << '\n';
} else if (o == 1) {
cin >> x >> y;
modify(x, -a[x]);
a[x] = y;
modify(x, a[x]);
} else if (o == 2) {
}
}
}
}
return 0;
}
```