记录编号	406365	评测结果	AAAAAAAAAA
题目名称	天才魔法少女琪露诺爱计数	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2017-05-18 15:59:45	内存使用	1.46 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
const int MAXN = 1e5 + 10;
const int MOD = 998244353;
 
inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp)) tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}
 
inline int lowbit(int x);
inline void update(int i, int k);
inline int sum(int i);
 
int N, L, R, T, maxh;
int h[MAXN];
int f[MAXN];
int s[MAXN];
 
int main(){ 
#ifndef LOCAL
	freopen("cirnoisclever.in", "r", stdin);
	freopen("cirnoisclever.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	N = in(), L = in(), R = in(), T = in();
 
	for(int i = 1; i <= N; ++i){ 
		h[i] = in();
		if(h[i] > maxh) maxh = h[i];
	}
 
	f[1] = 1;
	update(h[1], f[1]);
 
	for(int i = L + 1, l, r, lh, hh; i <= N; ++i){ 
		r = i - L + 1;
		l = max(0, i - R);
		lh = max(1, h[i] - T);
		hh = min(maxh, h[i] + T);
 
		f[i] = (sum(hh) - sum(lh - 1) + MOD) % MOD;
		update(h[l], -f[l]);
		update(h[r], f[r]);
	}
 
	printf("%d\n", f[N]);
	return 0;
}
 
inline int lowbit(int x){ 
	return x & (~x + 1);
}
 
inline void update(int i, int k){ 
	if(!i) return ;
	while(i <= maxh){ 
		s[i] += k;
		while(s[i] < 0) s[i] += MOD;
		s[i] %= MOD;
		i += lowbit(i);
	}
 
	return ;
}
 
inline int sum(int i){ 
	int sum = 0;
	while(i){ 
		sum = (sum + s[i]) % MOD;
		i -= lowbit(i);
	}
 
	return sum;
}