题解 P2880 【[USACO07JAN]平衡的阵容Balanced Lineup】
Newuser
2018-06-03 22:42:51
看了下大家做法主要:
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:
```cpp
#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小站](http://www.newuser.top/2018/06/03/on%e9%a2%84%e5%a4%84%e7%90%86st%e8%a1%a8rmq%e5%ad%a6%e4%b9%a0/)