King of Range 2024牛客国庆集训派对day3
原题
解析
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();
}
}原文地址：https://blog.csdn.net/2301_81278039/article/details/142697502
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！