d668 - 奇怪的老闆
題目描述
題目描述了老闆會隨機詢問員工薪資區間的最大值和最小值之差。給定 N 個員工的薪資，以及 Q 個查詢，每個查詢包含一個區間 [a, b]，要求計算該區間內員工薪資的最大值和最小值之差。
解題思路
此題的核心在於高效地處理多個區間查詢。由於需要頻繁查詢區間的最大值和最小值，直接遍歷區間效率過低。因此，使用 Segment Tree (線段樹) 是一種合適的解決方案。
- 建立 Segment Tree: 使用給定的員工薪資建立一個 Segment Tree。每個節點儲存對應區間的最小值和最大值。
- 查詢: 對於每個查詢 [a, b]，使用 Segment Tree 查詢該區間的最大值和最小值。
- 計算差值: 計算查詢到的最大值和最小值之差，並輸出結果。
Segment Tree 允許在 O(log N) 的時間內查詢區間的最大值和最小值，從而有效地處理大量的查詢。
複雜度分析
- 時間複雜度: O(N + Q log N)
- 建立 Segment Tree 需要 O(N) 時間。
- 每個查詢需要 O(log N) 時間，總共 Q 個查詢需要 O(Q log N) 時間。
- 空間複雜度: O(N)
- Segment Tree 需要 O(N) 空間儲存。
程式碼
#include <iostream>
#define maxv 100000000
#define minv -100000000
using namespace std;
int num[50001],n,q,a,b;
int nc=0;
struct node{
int l,r;
int min,max;
node *left, *right;
};
node tree[100000];
void build(node *now,int l,int r){
now->l = l;
now->r = r;
if(l==r){
now->min=now->max=num[l];
return;
}
++nc;
now->left = tree+nc;
++nc;
now->right = tree+nc;
int m=(l+r)>>1;
build(now->left,l,m);
build(now->right,m+1,r);
now->max = max(now->left->max, now->right->max);
now->min = min(now->left->min, now->right->min);
}
int ans_max , ans_min;
void query(node *rt, int l, int r){
if(rt->l == l && rt->r == r){
ans_max = ans_max > rt->max ? ans_max : rt->max;
ans_min = ans_min < rt->min ? ans_min : rt->min;
return ;
}
int m = (rt->l + rt->r) >> 1;
if(r <= m){
query(rt->left, l, r);
}else if(l > m){
query(rt->right, l, r);
}else{
query(rt->left, l, m);
query(rt->right, m + 1, r);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> q;
for(int i=0;i<n;i++)
cin >> num[i];
build(tree,0,n);
while(cin >> a >> b){
ans_max=minv;
ans_min=maxv;
query(tree,a-1,b-1);
cout << ans_max-ans_min << "\n";
}
}