题目链接
Problem Description
Prefix Sum is a useful trick in data structure problems.
For example, given an array A of length n and m queries.
Each query gives an interval [l,r] and you need to calculate $ \sum_{i=l}^r A_i $. How to solve this problem in O(n+m)?
We can calculate the prefix sum array B in which Bi is equal to $ \sum_{i=l}^r A_i $ . And for each query, the answer is Br-Bl-1.
Since Rikka is interested in this powerful trick, she sets a simple task about Prefix Sum for you:
Given two integers n,m, Rikka constructs an array A of length n which is initialized by Ai = 0. And then she makes m operations on it.
There are three types of operations:
- 1 L R w, for each index i ∈ [L,R], change Ai to Ai + w.
- 2, change A to its prefix sum array. i.e., let A’ be a back-up of A, for each i ∈ [1,n], change Ai to .
- 3 L R, query for the interval sum ∑i=lrAi .
Input
The first line contains a single number t(1≤ t ≤ 3), the number of the testcases.
For each testcase, the first line contains two integers n,m(1 ≤ n,m ≤ 1e5).
And then m lines follow, each line describes an operation(1 ≤ L ≤ R≤ n, 0 ≤ w ≤ 1e9).
The input guarantees that for each testcase, there are at most 500 operations of type 3.
Output
For each query, output a single line with a single integer, the answer modulo 998244353.
Sample intput
1
100000 7
1 1 3 1
2
3 2333 6666
2
3 2333 6666
2
3 2333 6666
Sample Output
13002
58489497
12043005
题意:
有一个数列初始值设为0，有三种操作，区间加w，所有值改为前缀和，区间和查询。
思路:
官方题解：
考虑对得到的数列进行差分。那么我们的区间[L,R]可以看成是上一次求和前的在L点的单点+W，和在R点的单点减。
那么我们只需要记录当前这一场查询的时候前面共进行了多少次前缀和，然和对于每次的查询操作，我们计算之前的每一场的区间加法对答案的贡献。而每个数对答案的贡献就是上面的组合数乘上当前的数值大小。
对于每一次的区间查询就是两次单点查询的值相减。
分块代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int maxn = 2e5 + 50;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
LL inv[maxn], fi[maxn];
struct ss{
int k,x,v;
ss(int _k = 0, int _x=0, int _v=0)
{k = _k,x = _x, v = _v;};
}a[maxn];
template <class T>
inline bool scan_d(T &ret) {
char c; int sgn;
if(c = getchar(),c == EOF) return 0;
while(c != '-' && (c < '0' || c > '9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c-'0');
while(c = getchar(),c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
inline void out(LL x) {
if(x > 9) out( x / 10);
putchar( x % 10 + '0');
}
LL qpow(LL x, LL n){
LL ans = 1;
x = x % mod;
while(n){
if(n&1) ans = ans * x % mod;
x = x * x % mod;
n >>= 1;
}return ans;
}
void init(){
fi[0] = 1;
for(int i = 1; i < maxn; ++i) fi[i] = fi[i-1] * i % mod;
inv[maxn-1]=qpow(fi[maxn-1],mod-2);
for(int i=maxn-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
inline LL C(int n, int m){
if(n >= 0){
if(n >= m) return fi[n] * inv[m] % mod * inv[n-m] % mod;
return 0;
}n = m-n-1;
int flag = 1;
if(m&1) flag = -1;
return (mod + flag* fi[n]*inv[m] % mod* inv[n-m] % mod) % mod;
}
inline LL solve(int k, int n, int x){
LL ans = 0;
for(int i = 1; i <= n;++i){
if(a[i].x == x) ans += a[i].v;
else if(a[i].x < x){
ans = (ans + 1LL*a[i].v*C(k-a[i].k + x - a[i].x - 1, x-a[i].x) % mod) % mod;
}
}return ans;
}
int main(){
int t;
init();
scan_d(t);
while(t--){
int n,m;
scan_d(n);
scan_d(m);
int k =0, cnt = 0;
while(m--){
int op,l,r,v;
scan_d(op);
if(op == 2){ k++; continue;}
scan_d(l);
scan_d(r);
if(op == 1){
scan_d(v);
a[++cnt] = ss(k,l,v);
a[++cnt] = ss(k,r+1,mod-v);
}else out( (solve(k+2,cnt,r) - solve(k+2,cnt,l-1) + mod) % mod),puts("");
}
}return 0;
}
|