# Untitled

unknown
c_cpp
14 days ago
1.5 kB
1
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

void solve() {
int n, q;
cin >> n >> q;
vector<ll> a(n);
for (ll& u : a) cin >> u;

vector<ll> x(q);
for (ll& u : x) cin >> u;

vector<int> p(q);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
return x[i] < x[j];
});

vector<ll> d(n - 1);
vector<pair<ll, int>> all;
set<int> invalid;
for (int i = 0; i < n - 1; i++) {
d[i] = a[i] - a[i + 1];
all.emplace_back(d[i], i);
invalid.insert(i);
}
invalid.insert(-1);
invalid.insert(n - 1);

auto choose_2 = [&](ll x) {
return x * (x - 1) / 2;
};

ll ans = 0;
sort(all.begin(), all.end());

vector<ll> res(q);

int i = 0;
for (int j : p) {
while (i < n - 1 && all[i].first <= x[j]) {
int k = all[i].second;
int after = *invalid.upper_bound(k);
ans -= choose_2(after - k);
int before = *prev(invalid.lower_bound(k));
ans -= choose_2(k - before);
ans += choose_2(after - before);
invalid.erase(k);
i++;
}
res[j] = ans;
}

for (ll u : res) {
cout << u << ' ';
}
cout << '\n';
}

int main() {
ios::sync_with_stdio(0); cin.tie(0);
tt = 1, tc = 1; cin >> tt;
while (tt--) solve(), tc++;
}
```