AcWing 4281. 序列查询新解
原题链接
简单
转化为区间
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long ll;
const int M = 1e5 + 10;
int n, N;
int a[M];
PII f[M], g[M];
int main() {
scanf("%d%d", &n, &N);
int pre = 0, cur;
for (int i = 0; i < n; i++) {
scanf("%d", &cur);
f[i] = {pre, cur - 1};
pre = cur;
}
f[n] = {pre, N - 1};
int r = N / (n + 1), cnt = -1;
for (int i = 0; i < N; i += r) g[++cnt] = {i, i + r - 1};
ll res = 0;
for (int i = 0, j = 0; i <= n && j <= cnt; )
if (g[j].y >= f[i].y) {
if (g[j].x >= f[i].x) res += (ll)(f[i].y - g[j].x + 1) * abs(i - j);
else res += (ll)(f[i].y - f[i].x + 1) * abs(i - j);
i++;
} else {
if (g[j].x >= f[i].x) res += (ll)(g[j].y - g[j].x + 1) * abs(i - j);
else res += (ll)(g[j].y - f[i].x + 1) * abs(i - j);
j++;
}
printf("%lld", res);
return 0;
}