Portal
很容易想到贪心+线段树查询维护
UVa上这题是假数据 O(nk)暴力都能0ms AC...
此外输入可能是空文件 坑！！！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
struct node { int l, r, minv, minp, lz; } tree[maxn << 2];
struct Min
{
int v, p;
Min(int v, int p) { this->v = v; this->p = p; }
bool operator < (const Min& x) const { return v == x.v ? p > x.p : v < x.v; }
};
inline const int read()
{
int 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 << 3) + (x << 1) + ch - '0'; ch = getchar(); }
return x * f;
}
inline int ls(int id) { return id << 1; }
inline int rs(int id) { return id << 1 | 1; }
void push_up(int id)
{
if (tree[rs(id)].minv <= tree[ls(id)].minv)
{
tree[id].minv = tree[rs(id)].minv;
tree[id].minp = tree[rs(id)].minp;
}
else
{
tree[id].minv = tree[ls(id)].minv;
tree[id].minp = tree[ls(id)].minp;
}
}
void push_down(int id)
{
if (tree[id].lz)
{
tree[ls(id)].minv -= tree[id].lz;
tree[ls(id)].lz += tree[id].lz;
tree[rs(id)].minv -= tree[id].lz;
tree[rs(id)].lz += tree[id].lz;
tree[id].lz = 0;
}
}
void build(int id, int l, int r)
{
tree[id].l = l;
tree[id].r = r;
tree[id].lz = 0;
tree[id].minv = 0x3f3f3f3f;
if (l == r)
{
tree[id].minv = read();
tree[id].minp = l;
return;
}
int mid = (l + r) >> 1;
build(ls(id), l, mid);
build(rs(id), mid + 1, r);
push_up(id);
}
Min query(int id, int l, int r)
{
if (tree[id].l == l && tree[id].r == r) return Min(tree[id].minv, tree[id].minp);
push_down(id);
int mid = (tree[id].l + tree[id].r) >> 1;
if (r <= mid) return query(ls(id), l, r);
if (l > mid) return query(rs(id), l, r);
return min(query(ls(id), l, mid), query(rs(id), mid + 1, r));
}
void update(int id, int l, int r, int sub)
{
if (tree[id].l == l && tree[id].r == r)
{
tree[id].minv -= sub;
tree[id].lz += sub;
return;
}
push_down(id);
int mid = (tree[id].l + tree[id].r) >> 1;
if (r <= mid) update(ls(id), l, r, sub);
else if (l > mid) update(rs(id), l, r, sub);
else
{
update(ls(id), l, mid, sub);
update(rs(id), mid + 1, r, sub);
}
push_up(id);
}
int main()
{
int t = 0;
scanf("%d", &t);
while (t--)
{
int n = read(), k = read();
build(1, 1, n);
ll res = 0;
for (int i = 1; i <= n - k + 1; )
{
Min m = query(1, i, i + k - 1);
int minv = m.v, minp = m.p;
if (minv > 0)
{
res += minv;
update(1, i, i + k - 1, minv);
}
i = minp + 1;
}
printf("%lld\n", res);
}
return 0;
}