概率啊啊啊啊啊……

Description

见原题

Solution

题解咕了, 就写点大致思考路径吧.

经过题解的一番推导(::反向树状数组的性质), 发现我们需要查两个点相同的概率.

并且每一次$Add$操作会对不同的段产生不同的影响, 而且同时随左端点和右端点变化, 也就是要二维结构了. 同时发现我们的概率运算符合交换律和结合律, 可以在线段树做.

同时考虑标记永久化, 但记得在查询时一路上的答案都要算进来.

细节比较多.

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
#include <bits/stdc++.h>
#define mod 998244353

using namespace std;
typedef long long ll;

const int maxn = 1e+5 + 5;

int id[maxn << 2], ls[maxn << 8], rs[maxn << 8], tot;
int n, m;
ll sp[maxn << 8];

ll CalcPro(const ll &PEqual, const ll &PRemain) {
  return (PEqual * PRemain % mod + (1 - PEqual + mod) * (1 - PRemain + mod) % mod) % mod;
}
ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = (ret * base) % mod;
    index >>= 1;
    base = (base * base) % mod; 
  }
  return ret;
}
void update(int &cur, int l, int r, int L, int R, ll v) {
  if (!cur) cur = ++tot, sp[cur] = 1;
  if (L <= l && r <= R) {
    sp[cur] = CalcPro(sp[cur], v);
    return;
  }
  int mid = (l + r) >> 1;
  if (L <= mid) update(ls[cur], l, mid, L, R, v);
  if (R > mid) update(rs[cur], mid + 1, r, L, R, v);
}
ll query(int cur, int l, int r, int p) {
  if (!cur) return 1;
  if (l == r) return sp[cur];
  int mid = (l + r) >> 1;
  if (p <= mid) return CalcPro(sp[cur], query(ls[cur], l, mid, p));
  else return CalcPro(sp[cur], query(rs[cur], mid + 1, r, p));
}
void ext_update(int cur, int l, int r, int L, int R, int qx, int qr, ll v) {
  if (L <= l && r <= R) {
    update(id[cur], 1, n, qx, qr, v);
    return;
  }
  int mid = (l + r) >> 1;
  if (L <= mid) ext_update(cur << 1, l, mid, L, R, qx, qr, v);
  if (R > mid) ext_update(cur << 1|1, mid + 1, r, L, R, qx, qr, v);
}
ll ext_query(int cur, int l, int r, int p, int Ip) {
  if (l == r) return query(id[cur], 1, n, Ip);
  int mid = (l + r) >> 1;
  if (p <= mid) return CalcPro(query(id[cur], 1, n, Ip), ext_query(cur << 1, l, mid, p, Ip));
  else return CalcPro(query(id[cur], 1, n, Ip), ext_query(cur << 1|1, mid + 1, r, p, Ip));
}
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}

int main() {
  n = rd(); m = rd();
  int opt, l, r;
  while (m--) {
    opt = rd(); l = rd(); r = rd();
    if (opt == 1) {
      ll Pnew = quick_power(r - l + 1, mod - 2);
      if (l > 1) 
        ext_update(1, 0, n, 1, l - 1, l, r, (1 - Pnew + mod) % mod), ext_update(1, 0, n, 0, 0, 1, l - 1, 0);
      if (r < n) 
        ext_update(1, 0, n, l, r, r + 1, n, (1 - Pnew + mod) % mod), ext_update(1, 0, n, 0, 0, r + 1, n, 0);
      ext_update(1, 0, n, l, r, l, r, (1 - (Pnew << 1) % mod + mod) % mod);
      ext_update(1, 0, n, 0, 0, l, r, Pnew);
    } else {
      printf("%lld\n", ext_query(1, 0, n, l - 1, r));
    }
  }
  return 0;
}