给定序列
1 x v
:
2 x
:查询
就是维护一个高维前缀和,也是经典套路,无脑推式子:
于是可以将
然后我们可以考虑将
此时我们发现,对于每次询问
xxxxxxxxxx
901
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27int N, Q;
28ll A[210000];
29
30ll qpow(ll a, ll b){
31 ll ret(1), mul(a);
32 while(b){
33 if(b & 1)ret = ret * mul % MOD;
34 b >>= 1;
35 mul = mul * mul % MOD;
36 }return ret;
37}
38
39class BIT{
40private:
41 ll tr[210000];
42public:
43 int lowbit(int x){return x & -x;}
44 void Modify(int x, ll v){while(x <= N)(tr[x] += v + MOD) %= MOD, x += lowbit(x);}
45 ll Query(int x){ll ret(0); while(x)(ret += tr[x]) %= MOD, x -= lowbit(x); return ret;}
46}bit1, bit2, bit3;
47
48int main(){
49 const ll inv2 = qpow(2, MOD - 2);
50 N = read(), Q = read();
51 for(int i = 1; i <= N; ++i)
52 A[i] = read(),
53 bit1.Modify(i, A[i]),
54 bit2.Modify(i, i * A[i] % MOD),
55 bit3.Modify(i, ((ll)i * i % MOD - 3ll * i % MOD + MOD) % MOD * A[i] % MOD);
56 while(Q--){
57 int opt = read();
58 if(opt == 1){
59 int x = read(); ll v = read();
60 bit1.Modify(x, (v - A[x] + MOD) % MOD),
61 bit2.Modify(x, x * ((v - A[x] + MOD) % MOD) % MOD),
62 bit3.Modify(x, ((ll)x * x % MOD - 3ll * x % MOD + MOD) % MOD * ((v - A[x] + MOD) % MOD) % MOD);
63 A[x] = v;
64 }else{
65 ll x = read();
66 ll ret = (x * x % MOD + 3ll * x % MOD + 2) % MOD * bit1.Query(x) % MOD;
67 (ret += (-2ll * x + MOD) % MOD * bit2.Query(x) % MOD) %= MOD;
68 (ret += bit3.Query(x)) %= MOD;
69 printf("%lld\n", ret * inv2 % MOD);
70 }
71 }
72 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
73 return 0;
74}
75
76template < typename T >
77inline T read(void){
78 T ret(0);
79 int flag(1);
80 char c = getchar();
81 while(c != '-' && !isdigit(c))c = getchar();
82 if(c == '-')flag = -1, c = getchar();
83 while(isdigit(c)){
84 ret *= 10;
85 ret += int(c - '0');
86 c = getchar();
87 }
88 ret *= flag;
89 return ret;
90}
update-2022_12_08 初稿