Note
In the first sample any group of three points meets our conditions.
In the second#include<stdio.h>#include<string.h>#include<algorithm>#include<math.h>#include<iostream>#include<stdlib.h>#include<set>#include<map>#include<queue>#include<vector>#define inf 2000000000#define PI acos(-1.0)#define lson(x) (x<<1)#define rson(x) ((x<<1)|1)#define rep(i,a,b) for(int i=a;i<=b;i++)#define drep(i,a,b) for(int i=a;i>=b;i–)using namespace std;typedef long long ll;int a[100100],n,d;int minx[100100][30];int maxx[100100][30];void init_RMQ(int n) {rep(i,1,n)maxx[i][0]=minx[i][0]=a[i];for(int j = 1; j < 20; ++j)for(int i = 1; i <= n; ++i)if(i + (1 << j) – 1 <= n){maxx[i][j] = max(maxx[i][j – 1], maxx[i + (1 << (j – 1))][j – 1]);minx[i][j] = min(minx[i][j – 1], minx[i + (1 << (j – 1))][j – 1]);}}int getmax(int x,int y){if(x>y)swap(x,y);int k=log((y-x+1)*1.0)/log(2.0);return max(maxx[x][k],maxx[y-(1<<k)+1][k]);}int getmin(int x,int y){if(x>y)swap(x,y);int k=log((y-x+1)*1.0)/log(2.0);return min(minx[x][k],minx[y-(1<<k)+1][k]);}int main(){scanf("%d%d",&n,&d);rep(i,1,n)scanf("%d",&a[i]);init_RMQ(n);int l=1;int r=3;long long ans=0;rep(i,3,n){r=i;while(getmax(l,r)-getmin(l,r)>d)l++;if(r-l+1>=3){//printf("%d %d\n",l,r);ans+=(r-l)*1LL*(r-l-1)/2LL;}}printf("%I64d\n",ans);}s sample only 2 groups of three points meet our conditions:{-3, -2, -1}and{-2, -1, 0}.
In the third sample only one group does:{1, 10, 20}.
这题也可以用rmq做，然后依次枚举l,r
，有一些喷着香水闻不到的空气，有一些在写字楼里永远遇不见的人。
