51nod1275连续子段的差异(单调队列)

原题链接

1275 连续子段的差异

题目来源&＃xff1a; Codility

基准时间限制&＃xff1a;1 秒 空间限制&＃xff1a;131072 KB 分值: 80 难度&＃xff1a;5级算法题

 收藏

 关注

#include
#include
#include
#include
#define maxn 50005
using namespace std;
typedef long long ll;int deq1[maxn], deq2[maxn];
int num[maxn];
ll f(int n){return ((ll)n &＃43; 1) * n / 2;
}
int main(){// freopen("in.txt", "r", stdin);int n, k, l1 &＃61; 0, r1 &＃61; 0, l2 &＃61; 0, r2 &＃61; 0;int pre &＃61; 0;ll ans &＃61; 0, d &＃61; 0;scanf("%d%d", &n, &k);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)scanf("%d", num&＃43;i);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){while(l1 !&＃61; r1 && num[deq1[r1-1]] num[i])r2--;deq1[r1&＃43;&＃43;] &＃61; i;deq2[r2&＃43;&＃43;] &＃61; i;if(abs(num[deq1[l1]] - num[deq2[l2]] > k)){int maxs &＃61; max(deq1[l1], deq2[l2]) - 1;ans &＃43;&＃61; f(maxs - pre);ans -&＃61; d;int sign &＃61; -1;while(l1 !&＃61; r1 && num[deq1[l1]] - num[deq2[l2]] > k){if(deq1[l1] > deq2[l2]){l2&＃43;&＃43;;sign &＃61; 0;}else if(deq1[l1] }