codeforces 332B B. Maximum Absurdity(rmq)

题目链接：

codeforces 332B

题目大意：

给出一个序列，让找出不互相覆盖的两个长度为k的段，问在两个段的权值和最大的情况下，按照左边段的左端点排序，右边段的左端点作为第二关键字排序，得到的第一个答案。

题目分析：

• 很水的数据结构的题目，我们只需要先利用前缀和预处理出所有长度为k的段的总权值。然后利用rmq维护区间最大值和得到这个最大值取得的段的最左位置。
• 然后我们枚举第二段的位置，然后找到在采用当前段的前提下，第一段能取得的最大最左的情况，利用rmq的查询即可。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX 200007

using namespace std;

typedef long long LL;
typedef pair<long long , int > PII;

int n,k;
LL a[MAX],b[MAX];
LL dp[MAX][30];
LL ans[MAX][30];

void make ( )
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        dp[i][0] = b[i];
        ans[i][0] = i;
    }
    for ( int j = 1 ; (1<<j) <= n ; j++ )
        for ( int i = 1 ; i+(1<<j)-1 <= n ; i++ )
        {
            dp[i][j] = max ( dp[i][j-1] , dp[i+(1<<(j-1))][j-1] );
            if ( dp[i][j-1] == dp[i][j] ) ans[i][j] = ans[i][j-1];
            else ans[i][j] = ans[i+(1<<(j-1))][j-1];
        }
}

PII query ( int l , int r )
{
   int k = (int)((log((r-l+1)*1.0))/log(2.0));
   LL maxn;
   int temp;
   maxn = max ( dp[l][k] , dp[r-(1<<k)+1][k] );
   if ( maxn == dp[l][k] ) temp = ans[l][k];
   else temp = ans[r-(1<<k)+1][k];
   return make_pair ( maxn , temp ); 
}

int main ( )
{
    while ( ~scanf ( "%d%d" , &n , &k ) )
    {
        a[0] = 0;
        for ( int i = 1 ; i <= n ; i++ )
        {
            scanf ( "%lld" , &a[i] );
            a[i] += a[i-1];
        }
        for ( int i = k ; i <= n ; i++ )
            b[i] = a[i]-a[i-k];
        make ( );
        int loc =-1;
        PII temp = make_pair ( 0 , 0 );
        for ( int i = 2*k ; i <= n ; i++ )
        {
           PII tmp = query ( k , i-k );
           if ( tmp.first + b[i] > temp.first )
           {
               temp = tmp;
               temp.first += b[i];
               loc = i;
           }
        }
        temp.second -= k-1;
        loc -= k-1;
        printf ( "%d %d\n" , (int)temp.second , loc ); 
    }
}