posts - 16,comments - 0,trackbacks - 0

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 阅读(169) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理