50.logtrick && 幺半群滑动窗口
满足可结合律，并且有单位元，但是没有逆元却又想要滑窗（满足上述情况的一般有and，or，gcd），这时候就使用这个数据结构吧！
查看代码
template<typename T> struct SlidingWindowAggregation {
stack<T> stack_rev, stack_pos;//序列逆序，序列正序
stack<T> aux_stack_rev, aux_stack_pos;//辅助栈,维护序列逆序以及正序的运算前缀和
T e;//单位元
T e_rev, e_pos;//当前运算前缀和
SlidingWindowAggregation(T e, function<T(T, T)> op) : e(e), e_rev(e), e_pos(e), op(op) {}
int sz = 0;
function<T(T, T)> op;//定义一种幺半群运算(满足可结合律,且有单位元)
void push(T val) {
if (stack_rev.empty()) {
push_rev(val);
transfer();
}
else {
push_pos(val);
}
sz++;
}
void popleft() {
if (sz == 0) return;
if (stack_rev.empty()) transfer();
stack_rev.pop();
aux_stack_rev.pop();
e_rev = aux_stack_rev.empty() ? e : aux_stack_rev.top();
sz--;
}
T query() {
return op(e_rev, e_pos);
}
int size() { return sz; }
void push_rev(T val) {
stack_rev.push(val);
e_rev = op(val, e_rev);
aux_stack_rev.push(e_rev);
}
void push_pos(T val) {
stack_pos.push(val);
e_pos = op(e_pos, val);
aux_stack_pos.push(e_pos);
}
void transfer() {
while (stack_pos.size()) {
push_rev(stack_pos.top());
stack_pos.pop();
}
while (aux_stack_pos.size()) {
aux_stack_pos.pop();
}
e_pos = e;
}
};
100271. 或值至少为 K 的最短子数组 II - 力扣（LeetCode）
思考，异或怎么办？见字符串专题，字典树第一题。
查看代码
class Solution {
public:
int minimumSubarrayLength(vector<int>& a, int k) {
int n = a.size();
a.insert(a.begin(), 0);
int res = 1e9;
SlidingWindowAggregation<int> swa(0, [](int a, int b) {return a | b;});
for (int i = 1, j = 1;i <= n;i++) {
swa.push(a[i]);
while (j <= i && swa.query() >= k) res = min(res, i - j + 1), swa.popleft(), j++;
}
if (res == 1e9) return -1;
return res;
}
};2654. 使数组所有元素变成 1 的最少操作次数 - 力扣（LeetCode）
计算gcd=1的最短连续子数组即可。
查看代码
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
int g = 0;
for (auto i : nums) g = gcd(g, i);
if (g > 1) return -1;
int o = count(nums.begin(), nums.end(), 1);
if (!o) {
int res = 1e9;
SlidingWindowAggregation<int> swa(0, [](int a, int b) {return gcd(a, b);});
for (auto i : nums) {
swa.push(i);
while (swa.size() && swa.query() == 1) {
res = min(res, swa.size());
swa.popleft();
}
}
return res - 1 + n - 1;
}
else return n - o;
}
};1521. 找到最接近目标值的函数值 - 力扣（LeetCode）
用板子滑窗即可
查看代码
class Solution {
public:
int closestToTarget(vector<int>& a, int target) {
SlidingWindowAggregation<int> swa((1 << 25) - 1, [](int a, int b) {return a & b;});
int n = a.size();
a.insert(a.begin(), 0);
int res = (1 << 25) - 1;
for (int i = 1;i <= n;i++) {
swa.push(a[i]);
while (1) {
int t = swa.query();
res = min(res, abs(t - target));
if (t <= target) {
swa.popleft();
}
else {
break;
}
}
}
return res;
}
};由于gcd变化至多$logn$次，因此用st表预处理后二分即可。
查看代码
void Solve(int TIME) {
int n;cin >> n;
vi a(n + 1);for (int i = 1;i <= n;i++) cin >> a[i];
StaticTable st(a);
unordered_map<int, int> res;
for (int i = 1;i <= n;i++) {
for (int j = i;j <= n;) {
int val = st.query(i, j);
int l = j, r = n;
while (l <= r) {
int mid = l + r >> 1;
if (st.query(i, mid) == val) l = mid + 1;
else r = mid - 1;
}
int ans = l - 1;
res[val] += ans - j + 1;
j = ans + 1;
}
}
int q;cin >> q;
while (q--) {
int x;cin >> x;
cout << res[x] << endl;
}
}
同上
查看代码
class Solution {
public:
int subarrayBitwiseORs(vector<int>& a) {
unordered_set<int> st;
int n = a.size();a.insert(a.begin(), 0);
StaticTable table(a);
for (int i = 1;i <= n;i++) {
for (int j = i;j <= n;) {
int val = table.query(i, j);
int l = j, r = n;
while (l <= r) {
int mid = l + r >> 1;
if (table.query(i, mid) == val) l = mid + 1;
else r = mid - 1;
}
st.insert(val);
j = l;
}
}
return st.size();
}
};
D. New Year Concert (codeforces.com)
注意到gcd是单调不增的，而区间长度是单调递增的，故两者至多一个交点，于是转化为区间选点问题。预处理st表后，二分。
查看代码
void Solve(int TIME) {
int n;cin >> n;
vi a(n + 1);for (int i = 1;i <= n;i++) cin >> a[i];
StaticTable st(a);
vi f(n + 1);
for (int i = 1;i <= n;i++) {
f[i] = f[i - 1];
int l = 1, r = i;
while (l <= r) {
int mid = l + r >> 1;
if (st.query(mid, i) <= i - mid + 1) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
int ans = l - 1;
if (1 <= ans && ans <= i && st.query(ans, i) == i - ans + 1) {
f[i] = max(f[ans - 1] + 1, f[i]);
}
}
for (int i = 1;i <= n;i++) cout << f[i] << " \n"[i == n];
}
2411. 按位或最大的最小子数组长度 - 力扣（LeetCode）
同样是st表预处理
查看代码
class Solution {
public:
vector<int> smallestSubarrays(vector<int>& a) {
int n = a.size();a.insert(a.begin(), 0);
vi b(n + 2);for (int i = n;i >= 1;i--) b[i] = b[i + 1] | a[i];
vi res;
StaticTable st(a);
for (int i = 1;i <= n;i++) {
int l = i, r = n;
while (l <= r) {
int mid = l + r >> 1;
if (st.query(i, mid) == b[i]) r = mid - 1;
else l = mid + 1;
}
res.push_back(r + 1 - i + 1);
}
return res;
}
};蓝桥杯2021年第十二届国赛真题-和与乘积 - C语言网 (dotcpp.com)
由于乘积二分可能会爆，特判太麻烦，考虑用原地去重的trick做。由于有$1$的存在，并且这里超出范围就可以剪枝去掉，所以数组中同时存在的数字不会很多。
上面的题也都可以用这个方式。
查看代码
void Solve(int TIME) {
int n;cin >> n;
vi a(n + 1);for (int i = 1;i <= n;i++) cin >> a[i];
int sum = 0;
unordered_map<int, int> mp;
mp[0] = 0;
for (int i = 1;i <= n;i++) {
sum += a[i];
mp[sum] = i;
}
vc<ai3> st;
int res = 0;
int now = 0;
for (int i = 1;i <= n;i++) {
now += a[i];
for (auto& [x, l, r] : st) x = x * a[i];
st.push_back({ a[i],i,i });
int k = 0;
for (int j = 0;j < st.size();j++) {
if (st[j][0] == st[k][0]) {
st[k][2] = st[j][2];
}
else {
st[++k] = st[j];
}
}
st.resize(k + 1);
vc<ai3> nst;
for (auto j : st) {
if (j[0] <= sum) nst.push_back(j);
}
swap(st, nst);
for (auto [x, l, r] : st) {
if (mp.count(now - x) && l <= mp[now - x] + 1 && mp[now - x] + 1 <= r) {
res++;
}
}
}
cout << res << endl;
}标签：int,res,Trick2,rev,pos,st,stack From： https://www.cnblogs.com/mrsuns/p/18145921