T1 触手

思路：

第一问很简单，用 st 表维护区间最小值，再用线段树做区间修改，再单点查询最终的高度，相加即可；

第二问是一个贪心，不难发现，对于所有最终的高度，覆盖一段高度连续的区间肯定是最优的。

设 \(k\) 表示连续高度的区间个数, \(num_i\) 表示第 \(i\) 个连续高度的区间的元素个数，即 \(\sum_{i=1}^k\left\lceil\dfrac{h_i}{x}\right\rceil\)

改后代码(100 pts)：

#include <bits/stdc++.h>
#define int long long 
#define rint register int 
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define mod 998244353
#define inf 0x3f3f3f3f3f3f3f3f
#define ls p<<1
#define rs p<<1|1
#define inf 0x3f3f3f3f3f3f3f3f 
using namespace std;

inline int read() {
	rint x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}

const int N = 2e5 + 10;

struct Node {
	int l, r, mx, tag;
} t[N << 2];

int n, x, a[N], st[N][30], h[N], S, ans; 

int Ask(int l, int r) {
	int k = __lg(r - l + 1);
	return min(st[l][k], st[r - (1 << k) + 1][k]);
}

void pushup(int p) {
	t[p].mx = max(t[ls].mx, t[rs].mx);
}

void brush(int p, int x) {
	t[p].mx = max(t[p].mx, x);
	t[p].tag = max(t[p].tag, x);
}

void pushdown(int p) {
	if(t[p].tag) {
		brush(ls, t[p].tag);
		brush(rs, t[p].tag);
		t[p].tag = 0;
	}
}

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	t[p].mx = -inf;
	if(l == r) return ;
	int mid = l + r >> 1;
	build(ls, l, mid); build(rs, mid + 1, r);
	pushup(p);
}

void update(int p, int l, int r, int x) {
	if(l <= t[p].l && t[p].r <= r) {
		brush(p, x);
		return ;
	}
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if(l <= mid) update(ls, l, r, x);
	if(r > mid) update(rs, l, r, x);
	pushup(p);
}

int query(int p, int l, int r) {
	if(l <= t[p].l && t[p].r <= r) {
		return t[p].mx;
	}
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1, ans = -inf;
	if(l <= mid) ans = max(ans, query(ls, l, r));
	if(r > mid) ans = max(ans, query(rs, l, r));
	pushup(p);
	return ans;
}

signed main() {
  freopen("xyx.in", "r", stdin);
  freopen("xyx.out", "w", stdout);
  n = read(), x = read();
  For(i,1,n) a[i] = read(), st[i][0] = a[i];
  for (int j = 1; (1 << j) <= n; j++) {
  	for (int i = 1; i + (1 << j) - 1 <= n; i++) {
  		st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
	build(1, 1, n);
	For(i,1,n - x + 1) update(1, i, i + x - 1, Ask(i, i + x - 1));
	For(i,1,n) h[i] = query(1, i, i), S += h[i];
	int num = 1;
	For(i,1,n+1) {
		if(h[i] == h[i+1]) num++;
		else {
			ans += ceil((double)num * 1.0 / x);
			num = 1;
		}
	}
	cout << S << '\n' << ans << '\n';
  return 0;
}