AT_abc444_e [ABC444E] Sparse Range

题目描述

给你一个长度为 N 的整数序列 $A_1,\dots,A_N$ 和一个正整数 D。

求满足以下两个条件的整数对 (L,R) 的个数：

• $1 \leq L \leq R \leq N$。
• $A_L,A_{L+1},\dots,A_R$ 中任意两个元素的差至少为 D。
  • 即对任意$ L \leq i < j \leq R $的整数对 (i,j) 都满足$ |A_i-A_j|\geq D$。

输入格式

输入内容由标准输入法提供，格式如下

N D
$A_1 \dots A_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

5 3
3 1 4 1 5

输出 #1

8

输入输出样例 #2

输入 #2

9 1
1 2 3 4 5 6 7 8 9

输出 #2

45

输入输出样例 #3

输入 #3

6 1000000000
123456789 234567891 987654321 321987654 1000000000 1

输出 #3

6

说明/提示

样例解释 #1

(1,1),(2,2),(3,3),(4,4),(5,5),(2,3),(3,4),(4,5) 八对满足条件。

数据范围

• $2\leq N \leq 4\times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq D \leq 10^9$

代码

// Sunshine, sunshine, ladybugs awake!  
// Clap your hooves and do a little shake!  
#include <bits/stdc++.h>  
#define int long long  
#define endl '\n'  
using namespace std;  
  
using PII=pair<int,int> ;  
const int MAXN=200010;  
const int mod=998244353;  
const int INF=0x3f3f3f3f3f3f3f3f;  
  
int a[MAXN];  
  
void solve() {  
    int q;cin>>q;  
    int mx=-1;  
    while(q--){  
        int x;cin>>x;  
        a[1]++;  
        a[x+1]--;  
        mx=max(mx,x+1);  
    }  
        for(int i=1;i<=mx;i++){  
        a[i]+=a[i-1];  
    }  
            int pos=1;  
    while(pos<=mx||a[pos]>0){  
        if(a[pos]>=10){  
            a[pos+1]+=a[pos]/10;  
            a[pos]%=10;  
        }pos++;  
    }  
        pos--;  
    while (pos > 1 && a[pos] == 0) {  
        pos--;  
    }  
        for(int i=pos;i>=1;i--){  
        cout<<a[i];  
    }  
}  
  
signed main() {  
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);  
    //int t;cin >> t;while (t--)     solve();  
    return 0;  
}