正题

题目大意

求有多少个长度在\(l,r\)之间，值域是\([1,n]\)的严格上升子序列

\(1\leq T,n\leq 10^5,1\leq l\leq r\leq 10^5\)

解题思路

先转换成两个前缀和的差，那么相当于我们要快速求

的值。

考虑到我们有组合数恒等式\(\binom n m=\binom{n-1}{m-1}+\binom{n-1}{m}\)。

如果我们知道了\(F(n,m)=\sum_{i=0}^m\binom{n}{i}\)，那么有\(F(n+1,m)=2F(n,m)-\binom{n}{m}\)（也就是相当于复制一份左移一位相加）。

然后\(F(n,m)\)都可以\(O(1)\)移动\(n,m\)了，直接上莫队。

时间复杂度：\(O(n\sqrt n)\)

code

#include
#include
#include
#define ll long long
using namespace std;
const ll N=5e5+10,P=998244353,T=500;
struct node{
	ll id,r,x;
}a[N];
ll n,m,fac[N],inv[N],ans[N];
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
bool cmp(node x,node y){
	if(x.x/T==y.x/T)
		return x.ra[i].x)x--,sum=(P+1)/2*(sum+C(x,r))%P;
		while(ra[i].r)(sum-=C(x,r))%=P,r--;
		(ans[abs(a[i].id)]+=sum*(a[i].id/abs(a[i].id))%P)%=P;
	}
	for(ll i=1;i<=m;i++)
		printf("%lld\n",(ans[i]+P)%P);
	return 0;
}