RMQ
# include <stdio.h>
# include <string.h>
# define N 100005
# define L 18
int n,k;
int a[N<<1], s[N<<1], r[N<<1][L];
void init(void)
{
int i;
// memset(a, 0, sizeof(a));
// memset(s, 0, sizeof(s));
// memset(r, 0, sizeof(r));
scanf("%d%d", &n, &k);
s[0] = 0;
for (i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
s[i] = s[i-1]+a[i];
r[i][0] = i;
}
for (; i <= 2*n; ++i)
{
a[i] = a[i-n];
s[i] = s[i-1]+a[i];
r[i][0] = i;
}
}
int Max_t(int x, int y)
{
return s[x]>=s[y] ? x:y;
}
void pre(void)
{
int i, j, l;
for (j = 1, l = 1; l*2 <= n*2; l*=2, ++j)
for (i = 1; i+l*2 <= 2*n+1; ++i)
r[i][j] = Max_t(r[i][j-1], r[i+l][j-1]);
}
int rmq(int s, int t)
{
int j = 0, l = 1;
while (l*2 <= t-s+1) l*=2, ++j;
return Max_t(r[s][j], r[t-l+1][j]);
}
void solve(void)
{
int i, ans = -0x7FFFFFFF, tmp, ti, tj;
for (i = 1; i <= n; ++i)
{
tmp = rmq(i, i+k-1);
if (s[tmp]-s[i-1] > ans)
{
ans = s[tmp]-s[i-1];
ti = i, tj = tmp;
}
}
ti = (ti+n-1)%n+1;
tj = (tj+n-1)%n+1;
if (ti == tj) ans = a[ti], printf("%d %d %d\n", ans, ti, tj);
else printf("%d %d %d\n", ans, ti, tj);
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
init();
pre();
solve();
}
return 0;
}
posted on 2012-08-28 08:24
yajunw 閱讀(184)
評(píng)論(0) 編輯 收藏 引用