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

Log_x · 2017-05-28 18:23:04 · 题解

刚学分块，来发一波分块题解。

因为最值都可以直接暴力合并，分块写起来也很简便，预处理部分只要O(n)的复杂度，而询问只是拆成几个块暴力合并。

而神奇的是，分块询问O(m * 根号n)的瓶颈复杂度竟然跑得炒鸡快。

代码：

// mex[i][j] / mix[i][j] 分别表示块i ~ 块j的最大/最小值

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int Maxn = 0x3f3f3f3f;
const int N = 5e4 + 5, M = 255;
int a[N], bl[M], br[M], mex[M][M], mix[M][M];
int n, Q, S, s;
template <class T> inline T Max(const T a, const T b) {return a > b? a : b;}
template <class T> inline T Min(const T a, const T b) {return a < b? a : b;}
template <class T> inline void CkMax(T &a, const T b) {if (a < b) a = b;}
template <class T> inline void CkMin(T &a, const T b) {if (a > b) a = b;}
template <class T> inline void Swap(T &a, T &b) {a ^= b; b ^= a; a ^= b;}
inline int get()
{
    char ch; bool f = false; int res = 0;
    while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
    if (ch == '-') f = true;
     else res = ch - '0';
    while ((ch = getchar()) >='0' && ch <= '9')
        res = (res << 3) + (res << 1) + ch - '0';
    return f? ~res + 1 : res;
}
inline void put(int x)
{
    if (x < 0)
      x = ~x + 1, putchar('-');
    if (x > 9) put(x / 10);
    putchar(x % 10 + 48);
}
inline void Init()
{
    memset(mex, -Maxn, sizeof(mex));
    memset(mix, Maxn, sizeof(mix));
    for (int i = 1; i <= s; ++i)
     for (int j = bl[i]; j <= br[i]; ++j)
      CkMax(mex[i][i], a[j]), CkMin(mix[i][i], a[j]);
    for (int i = 1; i < s; ++i)
     for (int j = i + 1; j <= s; ++j)
      CkMax(mex[i][j], Max(mex[i][j - 1], mex[j][j])),
      CkMin(mix[i][j], Min(mix[i][j - 1], mix[j][j]));
}
inline int Que(const int l, const int r)
{
    int L = (l - 1) / S + 1, R = (r - 1) / S + 1, Ma = -Maxn, Mi = Maxn;
    if (r - l < (S << 1)) // 注意特判没有完整的块的情况 
    {
        for (int i = l; i <= r; ++i)
         CkMax(Ma, a[i]), CkMin(Mi, a[i]);
        return Ma - Mi;
    }    
    if (l == bl[L]) L--;
    if (r == br[R]) R++;
    // 如果[l,r]刚好都在完整的块，这样就能直接返回块中信息，无需暴力处理，节省时间效率
    Ma = mex[L + 1][R - 1]; Mi = mix[L + 1][R - 1];
    int ed = br[L], st = bl[R];
    for (int i = l; i <= ed; ++i) CkMax(Ma, a[i]), CkMin(Mi, a[i]);
    for (int i = st; i <= r; ++i) CkMax(Ma, a[i]), CkMin(Mi, a[i]);
    return Ma - Mi;
}
int main()
{
    while (scanf("%d%d", &n, &Q) != EOF)
    {
        S = sqrt(n); s = 0;
        for (int i = 1; i <= n; ++i) a[i] = get();
        for (int i = 1; i <= n; ++i)
         if (i % S == 1) br[s] = i - 1, bl[++s] = i;
        br[s] = n; bl[s + 1] = br[s + 1] = n + 1;
        Init(); int x, y;
        while (Q--)
        {
            x = get(); y = get();
            put(Que(x, y)), putchar('\n');
        }
    }
    return 0;
}