本文主要是介绍hdu5289 Assignment --2015多校训练赛(一)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给定一串数字，里面存在多少个区间[l, r] 使得里面的最大值与最小值之差小于k。
思路:
用RMQ预处理出所有区间的最大值与最小值之差。之后枚举左端点L, 二分处理差值小于k的最左边端点R，把所有
的R-L+1加上就是答案。
/************************************************ Author: fisty* Created Time: 2015-08-20 22:09:44* File Name : hdu5289.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
#define MAX_N 100100
int t;
int n, k;
int a[MAX_N];
int mi[MAX_N][20], ma[MAX_N][20];void RMQ()
{for (int i = 0; i < n; ++i)mi[i][0] = ma[i][0] = a[i];for (int j = 1; (1<<j) <= n; ++j)for (int i = 0; i+(1<<j)-1 < n; ++i){mi[i][j] = min(mi[i][j-1], mi[i+(1<<(j-1))][j-1]);ma[i][j] = max(ma[i][j-1], ma[i+(1<<(j-1))][j-1]);}}int query(int lt, int rt)
{int k = 0;while ((1<<(k+1)) <= rt-lt+1)k++;return max(ma[lt][k], ma[rt-(1<<k)+1][k]) - min(mi[lt][k], mi[rt-(1<<k)+1][k]);
}
int Binary_Search(int x){int l = x, r = n-1;while(r - l > 1){int mid = (l + r) / 2;if(query(x, mid) < k) l = mid;else r = mid;}if(query(x, r) < k)return r;return l;
}
void solve(){LL ans = 0;int t;for(int i = 0;i < n; i++){t = Binary_Search(i);ans += t - i + 1;}printf("%lld\n", ans);
}
int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);scanf("%d", &t);while(t--){scanf("%d%d", &n, &k);for(int i = 0;i < n; i++){scanf("%d", &a[i]);}RMQ();solve();}return 0;
}
2.线段树：
首先，以a[n]起始的区间肯定是[n, n]。
然后以a[n-1]起始的区间最长是[n-1, n]，然后考虑需不需要把区间的右值减小，也就是考虑a[n]和a[n-1]的差值是否小于k。假设最终的区间为[n-1, d(n-1)]。
于是对于以a[n-2]起始的区间，自然最长是[n-2, d(n-1)]，然后考虑需不需要把区间的右值减小，也就是考虑这个区间内是否存在某个值与a[n-2]的差值大于等于k。
以此类推，以a[i]起始的区间应为[i, min(d(i+1), p)]，其中p是i右侧最后一个满足与a[i]差值小于k的数的脚标。
采用线段树记录区间的最大值和最小值，就能查询出任意[i, n]区间里第一个满足与a[i]差值大于等于k的值的位置x，然后x-1即为最后一个满足与a[i]差值小于k的数的脚标。
/************************************************ Author: fisty* Created Time: 2015-08-21 20:26:03* File Name : hdu5289 (2).cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
//线段树版
//采用线段树记录区间的最大值和最小值，就能查询出任意[i, n]区间里第一个满足与
//Ai差值大于等于k的值的位置x，然后x-1即为最后一个满足与Ai差值小于k的数的脚标。
int n, k;
const int MAX_N = 110000;
int _max[MAX_N << 2];
int _min[MAX_N << 2];
int p = -1;
int a[MAX_N];
struct Tree{void pushup(int rt){_max[rt] = max(_max[rt<<1], _max[rt<<1|1]);_min[rt] = min(_min[rt<<1], _min[rt<<1|1]);}void build(int l, int r, int rt){_max[rt] = _min[rt] = 0;if(l == r){_min[rt] = _max[rt] = a[l];return ;}int m = (l + r) >> 1;build(lson);build(rson);pushup(rt);}void query(int a, int b, int v){query(a, b, 1, n, 1, v);}void query(int a, int b, int l, int r, int rt, int v){if(l == r){if(abs(_min[rt] - v) >= k){if(p == -1 || p > l){p = l;}}return;}int m = (l + r) >> 1;if(a <= m){if(abs(_min[rt<<1] - v) >= k || abs(_max[rt<<1] - v) >= k){query(a, b, lson, v);}}if(p == -1 && b > m){if(abs(_min[rt<<1|1] - v) >= k || abs(_max[rt<<1|1] - v) >= k){query(a, b, rson, v);}}}
}segtree;int t;
void solve(){LL ans = 1;int d[MAX_N];d[n] = n;for(int i = n-1; i >= 1; i--){p = -1;segtree.query(i, n, a[i]);if(p == -1){p = n;}else{p--;}d[i] = min(d[i+1], p);ans += d[i] - i + 1;} printf("%lld\n", ans);
}
int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);scanf("%d", &t);while(t--){scanf("%d%d", &n, &k);for(int i = 1;i <= n; i++){scanf("%d", &a[i]);}segtree.build(1, n, 1);solve();}return 0;
}
这篇关于hdu5289 Assignment --2015多校训练赛(一)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
