C++(g++ 7.5.0) 解法, 执行用时: 1517ms, 内存消耗: 125132K, 提交时间: 2023-07-24 20:30:58

#include <iostream>
#include <cstring>

using namespace std;
using i64 = long long;

const int N = 1000010;

int n, m;
int w[N], f[N][21];
int a[N], b[N];

int maxp(int a, int b) {
  return w[a] > w[b] ? a : b;
}

void init() {
  for (int j = 0; j <= __lg(n); j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      if (!j) f[i][j] = i;
      else f[i][j] = maxp(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int ask(int l, int r) {
  int k = __lg(r - l + 1);
  return maxp(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
  cin.tie(0)->sync_with_stdio(false);
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++) {
      a[i] = b[i] = 0;
      cin >> w[i];
    }
    init();
    auto solve = [&](auto self, int l, int r) -> void {
      if (l > r) return;
      int mid = ask(l, r), val = w[mid];
      if (r - mid > mid - l) {
        for (int i = mid; i >= l; i--) {
          int lower = mid, upper = min(r, i + val - m - 1);
          if (lower <= upper) b[lower]++, b[upper + 1]--;
        }
      } else {
        for (int i = mid; i <= r; i++) {
          int lower = max(l, i + 1 + m - val), upper = mid;
          a[i] += max(0, upper - lower + 1); 
        }
      } 
      self(self, l, mid - 1), self(self, mid + 1, r); 
    };
    solve(solve, 1, n);
    for (int i = 1; i <= n; i++) b[i] += b[i - 1];
    for (int i = 1; i <= n; i++) {
      cout << a[i] + b[i] << " \n"[i == n];
    }
  }
  return 0;
}

C++ 解法, 执行用时: 1108ms, 内存消耗: 62004K, 提交时间: 2021-05-20 14:05:42

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[1000015];
int stk[1000015];
int L[1000015];
int R[1000015];
ll cf[1000015];
void clear(int n){
	for (int i = 0; i <= n + 5; i++){
		cf[i] = 0;
		L[i] = 0;
		R[i] = 0;
		stk[i] = 0;
		a[i] = 0;
	}
}
int main(){
	int n, m;
	while (cin >> n >> m){
		int top = 0;
		clear(n);
		for (int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= n; i++){
			while (top>0 && a[i] >= a[stk[top]]){
				top--;
			}
			L[i] = stk[top]+1;
			stk[++top] = i;
		}
		top = 0;	
		for (int i = 1; i <= n + 5; i++)stk[i] = 0;
		stk[0] = n+1;
		for (int i = n; i >= 1; i--){
			while (top>0 && a[i] > a[stk[top]]){
				top--;
			}
			R[i] = stk[top]-1;
			stk[++top] = i;
		}
		int p;
		ll res = 0;
		int Max;
		for (int i = 1; i <= n; i++){
			p = a[i] - m;
			int l = i;
				for (int j = L[i]; j <= i; j++){
					int r = min(j + p-1,R[i]);
					if (l>r)continue;
					cf[l] += 1; cf[r + 1] -= 1;
				}
	
		}
		for (int i = 1; i <= n; i++){
			cf[i] = cf[i - 1] + cf[i];
			printf("%lld ",cf[i]);
		}
		printf("\n");
	}
}