记录编号	590083	评测结果	AAAAAAAAAA
题目名称	天才魔法少女琪露诺爱计数	最终得分	100
用户昵称	liuyiche	是否通过	通过
代码语言	C++	运行时间	0.996 s
提交时间	2024-07-09 16:10:01	内存使用	4.52 MiB

#include <bits/stdc++.h>
            
using namespace std;
 
typedef long long ll;
 
int n, l, r;
ll t; 
ll h[100010];
ll f[100010];
ll mod = 998244353;
int L[205];
int R[205];
int blog[10010];
ll sum[205];
ll cnt[10010];

inline void build()
{
    int block = sqrt(10005);
    int num = 10005/block;
    if(10005%block != 0)  num++;
    for(int i = 1; i <= num; ++i)
    {
        L[i] = (i-1)*block+1;
        R[i] = i*block;    
    }  
    R[num] = 10005;
    for(int i = 1; i <= 10005; ++i)
        blog[i] = (i-1)/block+1;
}

inline void add(int x, ll num)
{
    cnt[x] += num;
    cnt[x] %= mod;
    sum[blog[x]] += num;
    sum[blog[x]] %= mod;
}

inline ll query(int x, int y)
{
    ll ans = 0;
    if(blog[x] == blog[y])
        for(int i = x; i <= y; ++i)
        {
            ans += cnt[i];
            ans %= mod;
        }
    else
    {
        for(int i = x; i <= R[blog[x]]; ++i)
            ans += cnt[i], ans %= mod;
        for(int i = L[blog[y]]; i <= y; ++i)
            ans += cnt[i], ans %= mod;
        for(int i = blog[x]+1;i < blog[y]; ++i)
        {
            ans += sum[i];
            ans %= mod;
        }
    }
    return ans;
}
    
int main()
{
    freopen("cirnoisclever.in", "r", stdin);
    freopen("cirnoisclever.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
            
    cin >> n >> l >> r >> t;
    build();
    f[1] = 1;
    for(int i = 1; i <= n; ++i)
    {
        cin >> h[i];
        if(i <= l)
            continue;
        add(h[i-l],f[i-l]);
        if(i-r-1 > 0)
            add(h[i-r-1],-f[i-r-1]);
        f[i] = (query(max((ll)1,h[i]-t),min((ll)10000,h[i]+t))%mod+mod)%mod;
    }
    cout << f[n];    
    
   	return 0;
}