[Codeforces Round #153 (Div. 1) pA][deque] Points on Line

原題連結
既然是pA當然要水水的XD

對於單調隊列和序列單調性有疑問的可以先做這題

這題雙指針和deque當然是都可以的，只是我懶的開陣列(?就邊讀邊做了
(因為輸入有保證是遞增給出，不必sort)

對於點x，往「前」求出所有與他距離不超過d的點們(注意，往前這件事情很重要)
顯然這些點的距離也都不超過d（想一想，為什麼)，那麼答案就可以加上C(點數,2);

這件事情就用普通的單調隊列做就行了。

最後要注意的是注意乘法運算，不要溢出。

#define LL long long
#include<cstdio>
#include<deque>
using namespace std;
deque<LL> dq;
int main()
{
    LL n,d;
    LL ans=0;
    scanf("%I64d%I64d",&n,&d);
    for(LL i=0,x;i<n;i++)
    {
        scanf("%I64d",&x);
        while(dq.size() && x-dq.front()>d) dq.pop_front();
        if(dq.size()) ans+=(LL)(dq.size())*(dq.size()-1)/2LL;
        dq.push_back(x);
    }
    printf("%I64d\n",ans);
}