# 分塊演算法

#### 求區間最值,用法其實很簡單,只要把原長度的資料,分成√n塊,每塊裡面放√n個資料,總資料數為√n*√n

## 建立分塊

先求出√n,再把每個區間的最大值依序更新，就完成了。

int a[MAXN]={.....};  //測資
int k=(int)sqrt(n);  //求出√n,sqrt會回傳一個小數,所以要轉型成int

vector<int> block(k+1);
for(int i=0;i<n;i++){
    block[i/k]=max(block[i/k],a[i]);
}

## 查詢
如果有塊就直接拿塊更新，剩下的則暴力找答案。

int query(int l,int r){
    int ans=INT_MIN;
    for(int i=l/k+1;i<r/k;i++){
        //對完整的塊搜block並更新最大值
        ans=max(ans,block[i]);
    }
    for(int i=l;i<=r;i++){
        //對最左邊不滿足一個完整個塊作暴力搜
        if(i/k!=l/k) break;  //直到下一個完整的塊
        ans=max(ans,a[i]);  //更新最大值
    }
    for(int i=r;i>=l;i--){
        //對最右邊不滿足一個完整個塊作暴力搜
        if(i/k!=r/k) break;  //直到下一個完整的塊
        ans=max(ans,a[i]);   //更新最大值
    }
    return ans;
}

ZJ 539

#include <bits/stdc++.h>
using namespace std;

int query(int l,int r,int k,vector<int>& block,vector<int>& a){
  int ans=0;
  for(int i=l;i<=r;i++){
        if(i/k!=l/k) break;
        ans=max(ans,a[i]);
    }
    for(int i=r;i>=l;i--){
        if(i/k!=r/k) break;
        ans=max(ans,a[i]);
    }
    for(int i=l/k+1;i<r/k;i++){
        ans=max(ans,block[i]);
    }
  return ans;
}

int main(){
  cin.sync_with_stdio(0),cin.tie(0);

  int n,m,l,r,x;
  cin >> n;
  
  int k=(int)sqrt(n);
  vector<int> block(k+1);
  vector<int> a(n);

  for(int i=0;i<n;i++){
    cin >> a[i];
    block[i/k]=max(block[i/k],a[i]);
  }

  cin >> m;
  while(m--){
    cin >> l >> r;
    l--,r--;
    if(l>r) swap(l,r);
    cout << query(l,r,k,block,a) << '\n';
  }
  return 0;
}