共计 3264 个字符，预计需要花费 9 分钟才能阅读完成。
DAY16 共 3 题：
- 奇♂妙拆分（简略数学）
- 区区区间间间（枯燥栈）
- 小 AA 的数列（位运算 dp）
🎈 作者：Eriktse
🎈 简介：19 岁，211 计算机在读，现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换 C ++/Python 算法。（优质好文继续更新中……）🚀
🎈 浏览原文取得更好浏览体验：https://www.eriktse.com/algorithm/1119.html
奇♂妙拆分（简略数学）
依据贪婪的想法，若要使得因子尽可能多，那么因子该当尽可能小，大于根号 n 的因子至少一个，从小到大枚举 [1, sqrt(n)] 的所有整数，如果 i 可能整除 n 就作为一个因子。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
int n;cin >> n;
set<int> st;
for(int i = 1;i <= n / i; ++ i)
if(n % i == 0)st.insert(i), n /= i;
st.insert(n);
cout << st.size() << '\n';}
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;cin >> _;
while(_ --)solve();
return 0;
}区区区间间间（枯燥栈）
题意：给定一个数组，求所有 子区间的最大值与最小值的差 的和。
如果暴力枚举必定不行，单单是子区间个数就有 n ^ 2 个，所以咱们应该思考每一个元素对答案的奉献，也就是说咱们须要晓得某个元素 a[i] 它会 在多少个区间里作为最大值，在多少个区间里作为最小值。
咱们预处理出四个数组，别离是 lmax[], rmax[], lmin[], rmin[] 示意点 i 作为最大值的左右最远地位，和作为最小值的左右最远地位（lmax[i] = j，示意在区间 [j, i] 中的最大值都是a[i]，其余的三个数组相似定义）。
用枯燥栈能够解决出这四个数组，一下以求 lmax[] 举例，保护一个 枯燥不增栈 ，栈内寄存的是 下标。
初始时栈内仅有一个a[0] = inf。
当咱们遇到一个 a[i] 时，一直地判断栈顶元素，如果栈顶元素比 a[i] 小，阐明这个栈顶该当弹出。
当更新结束后，此时的栈顶的左边相邻地位就是 a[i] 往左的最远的地位了，因为此时栈顶是 a[i] 往左的第一个大于等于 a[i] 的地位，那么这两头的元素都会小于a[i]。
其余的三个数组相似，留神，如果咱们解决 lmax 用的是枯燥不增栈，那么解决 rmax 就该当用枯燥递增栈，而不是枯燥不减栈，否则可能呈现区间反复示意或没有归属的问题（本人思考）。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9, inf =8e18;
int a[N], stk[N], top, lmax[N], rmax[N], lmin[N], rmin[N];
void solve()
{
int n;cin >> n;
for(int i = 1;i <= n; ++ i)cin >> a[i];
a[0] = a[n + 1] = inf;
top = 0;
stk[++ top] = 0;
for(int i = 1;i <= n; ++ i)
{while(top && a[i] > a[stk[top]])top --;
lmax[i] = stk[top] + 1;
stk[++ top] = i;
}
top = 0;
stk[++ top] = n + 1;
for(int i = n;i >= 1; -- i)
{while(top && a[i] >= a[stk[top]])top --;
rmax[i] = stk[top] - 1;
stk[++ top] = i;
}
a[0] = a[n + 1] = -inf;
top = 0;
stk[++ top] = 0;
for(int i = 1;i <= n; ++ i)
{while(top && a[i] < a[stk[top]])top --;
lmin[i] = stk[top] + 1;
stk[++ top] = i;
}
top = 0;
stk[++ top] = n + 1;
for(int i = n;i >= 1; -- i)
{while(top && a[i] <= a[stk[top]])top --;
rmin[i] = stk[top] - 1;
stk[++ top] = i;
}
int ans = 0;
for(int i = 1;i <= n; ++ i)
{ans += a[i] * (rmax[i] - i + 1) * (i - lmax[i] + 1);
ans -= a[i] * (rmin[i] - i + 1) * (i - lmin[i] + 1);
}
cout << ans << '\n';
}
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;cin >> _;
while(_ --)solve();
return 0;
}小 AA 的数列（位运算 | 前缀和）
这道题一看有点懵，感觉不是很好解决，但仍然是套路题。
看到异或，咱们应该想把每一个二进制位拆离开，实际上这里约 32 位二进制位能够先认为是互相独立的，对于每一位都计算出奉献，而后依照位权重加和即可。
异或题的套路根本都是拆分二进制，整体思考起来比较复杂，拆分后会简略很多。
先不论L, R。
如果咱们思考数组 1 2 3 4 5 的第 0 位：
获取第 0 位后失去 b 数组：1 0 1 0 1。
因为咱们要失去区间内 1 的个数，所以解决一个异或前缀和 p[] 是自然而然的，而后咱们枚举每一位作为左端点，看看会失去一个怎么的式子：
$$sum=\sum_{j=i + 1}^{j += 2, j \le n}p[j]\oplus p[i-1]$$
咱们晓得异或其实就是 % 2 的加法，也是 % 2 减法，所以咱们将 异或前缀和改为一般前缀和 p[]，以上的柿子能够转化为：
$$sum=\sum_{j=i + 1}^{j += 2, j \le n}[(p[j] – p[i-1]) (mod 2)]$$
那么咱们就能够对 p 再做一个前缀和 p2，然而p2 的步长应为 2。
而后下面的柿子就等价于（其中 l, r 为j的上上限，须要保障与 i - 1 奇偶性雷同，j的个数为(r - l + 2) / 2）:
$$sum=| p2[r] – p2[l – 1] – p[i – 1] * ((r – l + 2) / 2))|$$
因为这个 p2 存在 p2[-1] 的状况，所以咱们做个小小的便宜，不便代码的编写（其实你想要特判也行，只是不太不便，也容易出错）。
留神一下其余细节即可。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 109, p = 1e9 + 7, T = 100;
int a[N], b[N], p1[N], p2[N];
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, l, r;cin >> n >> l >> r;
for(int i = 1;i <= n; ++ i)cin >> a[i];
int ans = 0;
for(int w = 0;w <= 32; ++ w)
{for(int i = 1;i <= n; ++ i)b[i] = a[i] >> w & 1;
for(int i = 1;i <= n; ++ i)p1[T + i] = (b[i] + p1[T + i - 1]) % 2;
for(int i = 1;i <= n; ++ i)p2[T + i] = p1[T + i] + p2[T + i - 2];
int sum = 0;
for(int i = 1;i <= n; ++ i)
{int j1 = max(i + 1, l + i - 1), j2 = min(n, r + i - 1);
if((j1 - i) % 2 == 0)j1 ++;
if((j2 - i) % 2 == 0)j2 --;
if(j2 < j1)continue;
sum += abs(p2[T + j2] - p2[T + j1 - 2] -
p1[T + i - 1] * ((j2 - j1) / 2 + 1));
}
ans = (ans + (1ll << w) * sum % p) % p;
}
cout << ans << '\n';
return 0;
}🎈 本文由 eriktse 原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬
