原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-D.html
题目传送门 - https://www.nowcoder.com/acm/contest/148/D
题意
多组数据。
给定一个长度为 $n$ 初始全为 $0$ 的数列 $A$ 。$m$ 次操作，要求支持以下三种操作。
1. 区间加一个数 $v$
2. 全局修改，对于每一个 $i$ ，把 $A_i$ 改成原序列前 $i$ 项的和。
3. 区间求和。（询问次数不超过500）
$n,m\leq 10^5,v\leq 10^9$
题解
我们首先考虑在位置 $x$ 的一个数 $v$ ，在取 $k$ 次前缀和之后，对位置为 $y$ 的数的贡献为多少？
令 $L=y-x+1$ ，随便推式子或者打个表都可以得到贡献为：
$$\binom{(k-1)+(L-1)}{k-1}v$$
预处理组合数。由于询问次数 $\leq 500$ ，我们如果可以 $O(m)$ 回答每一个询问，那么就非常给力了。
由于区间修改的操作数太多了，所以我们取差分数组（一次反前缀和），在差分数组上做两次单点修改即可完成区间修改。
同理，区间询问我们不可能把每一个点的答案都算出来，我们取前缀和，于是区间询问就可以拆成两个单点询问，通过差分搞定了。
至于这个如何实现取前缀和数组，和取反前缀和数组，只需要记录一下当前的前缀和次数 $k$ 。
遇到操作 2 的时候 k++ 即可。
遇到操作 1 的时候，把单点修改的操作记下来，需要记录当前修改位置，修改值，当前修改时，取了几次前缀和。
时间复杂度 $O(mq)$ 。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=200005,mod=998244353;
int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
int Pow(int x,int y){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
int T,n,m;
struct Point{
int x,k,v;
Point(){}
Point(int _x,int _y,int _v){
x=_x,k=_y,v=_v;
}
}o[N];
int ocnt,k;
int Fac[N],Inv[N];
int C(int n,int m){
if (m<0||m>n)
return 0;
return 1LL*Fac[n]*Inv[m]%mod*Inv[n-m]%mod;
}
void add(int &x,int y){
x+=y;
if (x>=mod)
x-=mod;
}
int solve(int x){
k+=2;
int res=0;
for (int i=1;i<=ocnt;i++)
if (o[i].x<x)
res=(1LL*o[i].v*C(k-o[i].k+x-o[i].x-1,k-o[i].k-1)+res)%mod;
else if (o[i].x==x)
add(res,o[i].v);
k-=2;
return res;
}
int main(){
Fac[0]=Inv[0]=1;
for (int i=1;i<N;i++){
Fac[i]=1LL*Fac[i-1]*i%mod;
Inv[i]=Pow(Fac[i],mod-2);
}
scanf("%d",&T);
while (T--){
n=read(),m=read();
ocnt=0,k=-1;
for (int i=1;i<=m;i++){
int opt=read(),L,R,v;
if (opt==2){
k++;
continue;
}
L=read(),R=read();
if (opt==1){
v=read();
o[++ocnt]=Point(L,k,v);
o[++ocnt]=Point(R+1,k,(mod-v)%mod);
}
if (opt==3)
printf("%d\n",(solve(R)-solve(L-1)+mod)%mod);
}
}
return 0;
}