LightOJ 1093 - Ghajini 线段树

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
#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].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 <

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！