![[ACM算法竞赛日常训练]DAY16[奇♂妙拆分][区区区间间间][小AA的数列]数学 | 位运算 | 前缀和](/static/background/176.jpg "[ACM算法竞赛日常训练]DAY16[奇♂妙拆分][区区区间间间][小AA的数列]数学 | 位运算 | 前缀和")
-
小AA的数列（位运算dp）
奇♂妙拆分（简单数学）
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 阅读原文获得更好阅读体验：https://www.eriktse.com/algorithm/1119.html
奇♂妙拆分（简单数学）
i能够整除n就作为一个因子。
#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 == 0st.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就应当用单调递增栈，而不是单调不减栈，否则可能出现区间重复表示或没有归属的问题（自己思考）。
#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; ++ icin >> 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的数列（位运算 | 前缀和）
这道题一看有点懵，感觉不是很好处理，但依然是套路题。
异或题的套路基本都是拆分二进制，整体考虑起来比较复杂，拆分后会简单很多。
L, R。
1 2 3 4 5的第0位：
0位后得到b数组：1 0 1 0 1。
1的个数，所以处理一个异或前缀和p[]是自然而然的，然后我们枚举每一位作为左端点，看看会得到一个怎样的式子：
% 2的加法，也是% 2减法，所以我们将异或前缀和改为普通前缀和p[]，以上的柿子可以转化为：
p再做一个前缀和p2，但是p2的步长应为2。
l, r为j的上下限，需要保证与i - 1奇偶性相同，j的个数为(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; ++ icin >> a[i];
int ans = 0;
for(int w = 0;w <= 32; ++ w
{
for(int i = 1;i <= n; ++ ib[i] = a[i] >> w & 1;
for(int i = 1;i <= n; ++ ip1[T + i] = (b[i] + p1[T + i - 1] % 2;
for(int i = 1;i <= n; ++ ip2[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 == 0j1 ++;
if((j2 - i % 2 == 0j2 --;
if(j2 < j1continue;
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原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬
编程笔记 » [ACM算法竞赛日常训练]DAY16[奇♂妙拆分][区区区间间间][小AA的数列]数学 | 位运算 | 前缀和