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

L_Y_T · 2018-10-14 11:12:52 · 题解

最近我有点分块中毒了

这道题我是用ST表水过去的

然后我翻了翻题解,发现分块的题解几乎没有(仅有的一篇我还看不懂 哭笑.jpg)

于是就决定自己来一发

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100000
using namespace std ;
int tag_max[maxn] , tag_min[maxn] ;//记录块内最大最小
int n , m , a[maxn] ;
int N , pos[maxn] ;//块数以及块
int l[maxn] , r[maxn] ;//刚从别的地方学到的新技能--偷懒
int query_max(int x , int y ) {//区间求最大值
    int ans = -1000 ;
    if(pos[x] == pos[y]) {
        for(int i = x ; i <= y ; i ++) ans = max(ans , a[i]) ;//暴力
    }else {
        for(int i = x ; i <= r[pos[x]] ; i ++ ) ans = max(ans,a[i]) ;//左边
        for(int i = l[pos[y]] ; i <= y ; i ++) ans = max(ans ,a[i]) ;//右边
        for(int i = pos[x] + 1 ; i <= pos[y] - 1 ; i ++) ans = max(ans,tag_max[i]) ;//中间
    }
    return ans ;
}
int query_min(int x , int y ) {//区间求最小值
    int ans = 0x7ffffff ;
    if(pos[x] == pos[y]) {
        for(int i = x ; i <= y ; i ++) ans = min(ans , a[i]) ;
    }else {
        for(int i = x ; i <= r[pos[x]] ; i ++ ) ans = min(ans,a[i]) ;
        for(int i = l[pos[y]] ; i <= y ; i ++) ans = min(ans ,a[i]) ;
        for(int i = pos[x] + 1 ; i <= pos[y] - 1 ; i ++) ans = min(ans,tag_min[i]) ;
    }
    return ans ;
}
int main() { 
    memset(tag_min,0x3f,sizeof(tag_min)) ;
    memset(tag_max,-1,sizeof(tag_max)) ;
    scanf("%d%d",&n,&m) ;N = sqrt(n) ;
    for(int i = 1 ; i <= n ; i ++) {
        pos[i] = (i-1)/N + 1 ;
    }
    for(int i = 1 ; i <= n ; i ++) l[i] = (i-1) * N + 1 , r[i] = i * N ;
    for(int i = 1 ; i <= n ; i ++) {
        scanf("%d",&a[i]) ;
        tag_max[pos[i]] = max(tag_max[pos[i]],a[i]) ;
        tag_min[pos[i]] = min(tag_min[pos[i]],a[i]) ;
    }
    for(int i = 1 ; i <= m ; i ++) {
        int x , y ;
        scanf("%d%d",&x,&y) ;
        cout << query_max(x,y) - query_min(x,y) << endl ;
    }
    return 0 ;
}

暴力分块真神奇!!

完结散花!!!