思路
好久之前的了，忘记什么题目了
可以到我这里做luogu
反正就是hdu数据太水，导致自己造的数据都过不去，而hdu却A了
好像是维护了最大值和次大值，然后出错的几率就小了很多也许是自己写错了，忘记了
留坑待补
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int maxn = 1e5 + 7;
int n, l, T, cnt,a[maxn];
ll f[maxn];
int read()
{
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
struct node {
int l, r;
ll ma,flag;
} e[maxn << 2];
void pushup(int rt) {
e[rt].ma = max(e[ls].ma, e[rs].ma);
}
void build(int l, int r, int rt) {
e[rt].l = l, e[rt].r = r;
if (l == r) {
e[rt].ma = -1LL;
e[rt].flag=0;
return;
}
int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
pushup(rt);
}
void modfity(int L, ll k, int rt) {
if (e[rt].l == e[rt].r) {
if (e[rt].ma == k) e[rt].flag++;
else if (e[rt].ma < k) {
e[rt].ma = k;
e[rt].flag = 0ll;
}
return;
}
int mid = (e[rt].l + e[rt].r) >> 1;
if (L <= mid) modfity(L, k, ls);
else modfity(L, k, rs);
pushup(rt);
}
void delet(int L, ll k, int rt) {
if (e[rt].l == e[rt].r) {
if (k == e[rt].ma) {
if (e[rt].flag >= 1) e[rt].flag--;
else e[rt].ma = -1;
}
return;
}
int mid = (e[rt].l + e[rt].r) >> 1;
if (L <= mid) delet(L, k, ls);
else delet(L, k, rs);
pushup(rt);
}
ll query(int L, int R, int rt) {
if (L <= e[rt].l && e[rt].r <= R) {
return e[rt].ma;
}
int mid = (e[rt].l + e[rt].r) >> 1;
ll ans = -1LL;
if (L <= mid) ans = max(ans, query(L, R, ls));
if (R > mid) ans = max(ans, query(L, R, rs));
return ans;
}
int main() {
T=read();
for (; T--;) {
n=read(),l=read();
memset(f, -1, sizeof(f));
for (int i = 1; i <= n; ++i) {
a[i]=read();
}
build(1, 1e5, 1);
for (int i = 1; i <= n; ++i) {
if ((i - l) > 1) {
delet(a[i - l - 1] + 1, f[i - l - 1] - a[i - l - 1], 1);
}
if (a[i] == 1) {
if (i > l) {
f[i] = -1LL;
continue;
} else f[i] = (ll)a[i] * a[i];
} else {
ll tmp = query(1, a[i], 1);
if (tmp == -1LL) {
if (i > l) {
f[i] = -1LL;
continue;
} else
f[i] = a[i] * a[i];
} else {
f[i] = (ll)a[i] * a[i] + tmp;
}
}
modfity(a[i] + 1, f[i] - a[i], 1);
}
if (f[n] == -1) printf("Case #%d: No solution\n", ++cnt);
else printf("Case #%d: %lld\n", ++cnt, f[n]);
}
return 0;
}
/*
区间大小一定
求给点区间大小的小于a[i]的max
按照a[i]的权值建一颗线段树求max
区间类似于queue，删点 即可
可是删点会有几率GG掉，记录size也会GG掉
*/