http://www.lightoj.com/volume_showproblem.php?problem=1093

?

題意：給定序列，問長度為d的區間最大值和最小值得差最大是多少。

思路：可以使用線段樹做，由于固定區間長度，還可以使用單調隊列。

/** @Date : 2016-12-06-18.39* @Author : Lweleth (SoungEarlf@gmail.com)* @Link : https://github.com/* @Version :*/#include<bits/stdc++.h> #define LL long long #define PII pair #define MP(x, y) make_pair((x),(y)) #define fi first #define se second #define PB(x) push_back((x)) #define MMG(x) memset((x), -1,sizeof(x)) #define MMF(x) memset((x),0,sizeof(x)) #define MMI(x) memset((x), INF, sizeof(x)) using namespace std;const int INF = 0x3f3f3f3f; const int N = 1e5+20; const double eps = 1e-8;struct yuu {int l, r;int ma;int mi; }tt[N << 2];int a[N];void pushup(int p) {tt[p].ma = max(tt[p << 1].ma, tt[p << 1 | 1].ma);tt[p].mi = min(tt[p << 1].mi, tt[p << 1 | 1].mi); }void build(int l, int r, int p) {tt[p].l = l;tt[p].r = r;tt[p].ma = 0;tt[p].mi = INF;if(l == r){tt[p].ma = tt[p].mi = a[l];return ;}int mid = (l + r) >> 1;build(l , mid, p << 1);build(mid + 1, r, p << 1 | 1);pushup(p); }void updata(int l, int r, int v, int p) {if(l <= tt[p].l && r >= tt[p].r){return ;}int mid = (tt[p].l + tt[p].r) >> 1;if(l <= mid)updata(l, r, v, p << 1);if(r > mid)updata(l, r, v, p << 1 | 1);pushup(p); }PII query(int l, int r, int p)//直接返回pair會超時 {//cout <<tt[p].ma <<"~" <<tt[p].mi << endl;if(l <= tt[p].l && r >= tt[p].r)return MP(tt[p].ma, tt[p].mi);int mid = (tt[p].l + tt[p]. r) >> 1;PII ans;ans.fi = 0;ans.se = INF;if(l <= mid){ans.fi = max(ans.fi, query(l, r, p << 1).fi);ans.se = min(ans.se, query(l, r, p << 1).se);}if(r > mid){ans.fi = max(ans.fi, query(l, r, p << 1 | 1).fi);ans.se = min(ans.se, query(l, r, p << 1 | 1).se);}return ans; }int queryma(int l, int r, int p) {if(l <= tt[p].l && r >= tt[p].r)return tt[p].ma;int mid = (tt[p].l + tt[p].r) >> 1;int ma = 0;if(l <= mid)ma = max(ma, queryma(l, r, p << 1));if(r > mid)ma = max(ma, queryma(l, r, p << 1 | 1));return ma; }int querymi(int l, int r, int p) {if(l <= tt[p].l && r >= tt[p].r)return tt[p].mi;int mid = (tt[p].l + tt[p].r) >> 1;int mi = INF;if(l <= mid)mi = min(mi, querymi(l, r, p << 1));if(r > mid)mi = min(mi, querymi(l, r, p << 1 | 1));return mi; } int main() {int T;int cnt = 0;cin >> T;while(T--){int n, d;scanf("%d%d", &n, &d);for(int i = 1; i <= n; i++){scanf("%d", a + i);}build(1, n, 1);//cout << query(2, 3, 1) << endl;int ma = 0;for(int i = 1; i + d - 1 <= n; i++){//PII x = query(i, i + d - 1, 1);ma = max(queryma(i, i + d - 1, 1) - querymi(i, i + d - 1, 1), ma);//cout << ma <<endl;}printf("Case %d: %d\n", ++cnt, ma);}return 0; }

轉載于:https://www.cnblogs.com/Yumesenya/p/6139555.html

總結

以上是生活随笔為你收集整理的LightOJ 1093 - Ghajini 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。