题解 P2880 【[USACO07JAN]平衡的阵容Balanced Lineup】

· · 题解

看了下大家做法主要:

1.朴素STable O（nlogn)预处理+O（q)询问。

2.线段树O(n)预处理+O(qlogn)询问。

这里提供O（n)预处理+期望O（q)询问的方法。

首先我们分块，块的大小是(log2(n)) （这个块长是有用的），然后一个一个分块。然后我们处理以下的几个数组。

minqianzhui[n] , maxqianzhui[n]，minhouzhui[n] , maxhouzhui[n] 分别是前缀最小值和前缀最大值，后缀最小值和后缀最大值。这里的前缀后缀是针对分块后的数组来说的。也就是对于一个块内的前后缀。

以及fkminn[][] ,fkmaxx[]， 这里是对块与块之间建立朴素ST表RMQ，fkminn[x][0]即对于x块的最小值，fkmaxx[x][2]，即对于[x,x+(1<<2)-1]这几个块里面的最大值。（这里的建立时间复杂度小于O（n））

之后我们就可以了乱搞了！考虑到[l,r]区间，如果l到r之间不是同一个块内，那么我们可以O（1）找出中间块的最大最小值，以及通过后缀l和前缀r找出来。

只有当不是一个块的时候，我们就暴力乱扫吧！由于一个块的长度为logn，所以实际上最差也不会差到qlogn。

数据可能卡你始终一个块？绝不可能。题目数据范围肯定不可能一直出在一个小范围—–不然岂不是暴力都可以过？

所以可以达到期望时间复杂度预处理O（n）+O (q)啦！

这道题数据范围较小看不出来orz orz

code:

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50005;
int n,q;
int a[maxn];
int blk,ks;
int fk[maxn];
int minqianzhui[maxn],minhouzhui[maxn],maxqianzhui[maxn],maxhouzhui[maxn];//前缀最大\小值，后缀最大\小值 
int logg[maxn];
int fkminn[maxn][20],fkmaxx[maxn][20];//分块rmq
int main()
{
    scanf("%d%d",&n,&q);
    logg[0]=-1;
    for(int i=1;i<=n;i++) logg[i] = logg[i>>1]+1;//预处理log2 
    blk = logg[n];
    int j=1;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        fk[i] = j;
        if(fk[i]==fk[i-1]) 
        { 
            minqianzhui[i]=min(minqianzhui[i-1],a[i]);
            maxqianzhui[i]=max(maxqianzhui[i-1],a[i]);
        } 
        else
        {
            minqianzhui[i]=maxqianzhui[i]=a[i];
        }
        if(!(i%blk)) j++;
    }
    if(n%blk) ks=j;
    else ks=j-1;
    for(int i=n;i;i--)
    {
        if(fk[i]==fk[i+1])
        {
            minhouzhui[i]=min(minhouzhui[i+1],a[i]);
            maxhouzhui[i]=max(maxhouzhui[i+1],a[i]);
        }
        else
        {
            minhouzhui[i]=maxhouzhui[i]=a[i];
        }
    }
    for(int i=1;i<=ks;i++)
    {
        fkminn[i][0] = minhouzhui[blk*(i-1)+1];
        fkmaxx[i][0] = maxhouzhui[blk*(i-1)+1];
    }
    for(int j=1;j<=logg[ks];j++)
    {
        for(int i=1;i+(1<<j)-1<=ks;i++)
        {
            fkminn[i][j] = min( fkminn[i][j-1] , fkminn[i+(1<<(j-1))][j-1]  ); //对分块间rmq 
            fkmaxx[i][j] = max( fkmaxx[i][j-1] , fkmaxx[i+(1<<(j-1))][j-1] );
        }
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int fa = fk[l], fb =fk[r];
        if(fa!=fb)
        {
            fa+=1; fb-=1;
            int mmi=0x3f3f3f3f,mmx=-0x3f3f3f3f;
            if(fa<=fb)
            {
            int k = logg[fb-fa+1];
            mmi = min(fkminn[fa][k],fkminn[fb-(1<<k)+1][k]);
            mmx = max(fkmaxx[fa][k],fkmaxx[fb-(1<<k)+1][k]);
            }
            mmi = min(mmi,min(minhouzhui[l],minqianzhui[r]));
            mmx = max(mmx,max(maxhouzhui[l],maxqianzhui[r]));
            printf("%d\n",mmx-mmi);
        }
        else 
        {
            int mmi = 0x3f3f3f3f,mmx = -0x3f3f3f3f;
            for(int i=l;i<=r;i++) mmi=min(mmi,a[i]),mmx=max(mmx,a[i]);
            printf("%d\n",mmx-mmi);
        }
    } 
}

//本蒟蒻博客，欢迎来玩啊：Newuser小站