RMQ
# include <stdio.h>
# include <string.h>
![](/Images/OutliningIndicators/None.gif)
# define N 100005
# define L 18
![](/Images/OutliningIndicators/None.gif)
int n,k;
int a[N<<1], s[N<<1], r[N<<1][L];
![](/Images/OutliningIndicators/None.gif)
void init(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
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)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d", &a[i]);
s[i] = s[i-1]+a[i];
r[i][0] = i;
}
for (; i <= 2*n; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
a[i] = a[i-n];
s[i] = s[i-1]+a[i];
r[i][0] = i;
}
}
![](/Images/OutliningIndicators/None.gif)
int Max_t(int x, int y)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
return s[x]>=s[y] ? x:y;
}
![](/Images/OutliningIndicators/None.gif)
void pre(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
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]);
}
![](/Images/OutliningIndicators/None.gif)
int rmq(int s, int t)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
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]);
}
![](/Images/OutliningIndicators/None.gif)
void solve(void)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, ans = -0x7FFFFFFF, tmp, ti, tj;
for (i = 1; i <= n; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tmp = rmq(i, i+k-1);
if (s[tmp]-s[i-1] > ans)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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);
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int T;
scanf("%d", &T);
![](/Images/OutliningIndicators/InBlock.gif)
while (T--)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
init();
pre();
solve();
}
![](/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted on 2012-08-28 08:24
yajunw 阅读(175)
评论(0) 编辑 收藏 引用