King of Range 2024牛客国庆集训派对day3

原题

King of Range

解析

m 的值不大, 每次时间在 n logn 以内即可

我们遍历整个数组, 以 i 为右边界, 检测是否有满足条件的左边界, 一次只加上左面的所有可能, 用两个双向队列维护两个单调栈, 一个存最大值, 一个存最小值, 这样可以帮助找到合适的左边界

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;
int n, m, k, q, l, ans;
int a[N];
void solve2()
{deque<int> qmi, qmx;l = 0, ans = 0;for(int i = 1; i <= n; i ++ ){while (!qmx.empty() && a[qmx.front()] - a[i] > k){l = max(l, qmx.front());qmx.pop_front();}while (!qmi.empty() && a[i] - a[qmi.front()] > k){l = max(l, qmi.front());qmi.pop_front();}ans += l;while (!qmx.empty() && a[qmx.back()] <= a[i]){qmx.pop_back();}qmx.push_back(i);while (!qmi.empty() && a[qmi.back()] >= a[i]){qmi.pop_back();}qmi.push_back(i);}cout << ans << "\n";
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= m; i ++ ){cin >> k;solve2();}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;while (T -- ){solve();}
}