记录编号	590022	评测结果	AAWWEEEEEE
题目名称	天才魔法少女琪露诺爱计数	最终得分	20
用户昵称	123	是否通过	未通过
代码语言	C++	运行时间	1.166 s
提交时间	2024-07-09 13:04:28	内存使用	9.47 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=100010,Mod=998244353;
struct node {
    int l,r;
    long long val=0,key,flag=0;
} tree[N];
int n,l,r;
long long ret[N],a[N],cnt[N],t,dp[N];
void pushup(int p)
{
    tree[p].val=tree[p*2].val+tree[p*2+1].val;
}
void pushdown(int p)
{
    if (tree[p].flag)
    {
        tree[p*2].flag+=tree[p].flag;
        tree[p*2+1].flag+=tree[p].flag;
        tree[p*2].val+=tree[p].flag;
        tree[p*2+1].val+=tree[p].flag;
        tree[p].flag=0;
    }
}
void bulid(int p,int l,int r)
{
    tree[p].l=l,tree[p].r=r;
    if (l==r)
    {
        if (l==1)
        {
            tree[p].val=1;
        }
        tree[p].key=ret[l];
        return ;
    }
    int mid=(l+r)/2;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tree[p].key=tree[p*2].key+tree[p*2+1].key;
}
void add(int i,int p,int l,int r,long long k)
{
    if (l>n || tree[p].l==0)
    {
        return ;
    }
    if (a[i]+t*(tree[p].r-tree[p].l+1)>tree[p].key && l<=tree[p].l && tree[p].r<=r)
    {
        tree[p].flag+=k;
        tree[p].val+=k*(tree[p].r-tree[p].l+1);
        tree[p].val%=Mod;
        return ;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if (l<=mid) add(i,p*2,l,r,k);
    if (r>mid) add(i,p*2+1,l,r,k);
    pushup(p); 
}
int print(int x,int p)
{
    if (tree[p].l==tree[p].r)
    {
        if (tree[p].l==x)
        {
            return tree[p].val;
        } 
        return 0;
    }
    pushdown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    long long val=0;
    if (x<=mid) val+=print(x,p*2);
    if (x>mid) val+=print(x,p*2+1);
    return val;
}
int main() {
    freopen("cirnoisclever.in","r",stdin);
    freopen("cirnoisclever.out","w",stdout);
    scanf("%d%d%d%lld",&n,&l,&r,&t);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    if (n<=10000 && r-l+1<=1000)
    {
        dp[1]=1;
        for (int i=1;i<=n;i++)
        {
            for (int j=i+l;j<=i+r;j++)
            {
                if (abs(a[j]-a[i])<=t)
                {
                    dp[j]+=dp[i];
                }
            }
        }
        printf("%lld",dp[n]);
        return 0;
    }
    for (int i=1;i<n;i++)
    {
        cnt[i]=a[i+1]-a[i];
    }
    for (int i=1;i<n;i++)
    {
        ret[i]=ret[i-1]+cnt[i];
    }
    bulid(1,1,n);
    for (int i=1;i<=n;i++)
    {
        add(i,1,i+l,i+r,print(i,1));
    }
    printf("%lld",print(n,1));
}