题意
Problem Link
\(n \leq 5 \times 10^5\)
题解
第一条注意的就是这个是条件概率!
所以每个位置分开算概率是不对的, 所以这不是sb题。
所以得维护\((x, y)\)表示\(a_x = a_y\)的概率。
然后分类讨论一下就好了。所以还是sb题
/*
QiuQiu /qq
____ _ _ __
/ __ \ (_) | | / /
| | | | _ _ _ | | _ _ / / __ _ __ _
| | | | | | | | | | | | | | | | / / / _` | / _` |
| |__| | | | | |_| | | | | |_| | / / | (_| | | (_| |
\___\_\ |_| \__,_| |_| \__, | /_/ \__, | \__, |
__/ | | | | |
|___/ |_| |_|
*/
#include <bits/stdc++.h>
using namespace std;
class Input {
#define MX 1000000
private :
char buf[MX], *p1 = buf, *p2 = buf;
inline char gc() {
if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MX, stdin);
return p1 == p2 ? EOF : *(p1 ++);
}
public :
Input() {
#ifdef Open_File
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
}
template <typename T>
inline Input& operator >>(T &x) {
x = 0; int f = 1; char a = gc();
for(; ! isdigit(a); a = gc()) if(a == '-') f = -1;
for(; isdigit(a); a = gc())
x = x * 10 + a - '0';
x *= f;
return *this;
}
inline Input& operator >>(char &ch) {
while(1) {
ch = gc();
if(ch != '\n' && ch != ' ') return *this;
}
}
inline Input& operator >>(char *s) {
int p = 0;
while(1) {
s[p] = gc();
if(s[p] == '\n' || s[p] == ' ' || s[p] == EOF) break;
p ++;
}
s[p] = '\0';
return *this;
}
#undef MX
} Fin;
class Output {
#define MX 1000000
private :
char ouf[MX], *p1 = ouf, *p2 = ouf;
char Of[105], *o1 = Of, *o2 = Of;
void flush() { fwrite(ouf, 1, p2 - p1, stdout); p2 = p1; }
inline void pc(char ch) {
* (p2 ++) = ch;
if(p2 == p1 + MX) flush();
}
public :
template <typename T>
inline Output& operator << (T n) {
if(n < 0) pc('-'), n = -n;
if(n == 0) pc('0');
while(n) *(o1 ++) = (n % 10) ^ 48, n /= 10;
while(o1 != o2) pc(* (--o1));
return *this;
}
inline Output & operator << (char ch) {
pc(ch); return *this;
}
inline Output & operator <<(const char *ch) {
const char *p = ch;
while( *p != '\0' ) pc(* p ++);
return * this;
}
~Output() { flush(); }
#undef MX
} Fout;
#define cin Fin
#define cout Fout
#define endl '\n'
using LL = long long;
using pii = pair<int, int>;
const int P = 998244353;
int power(int x, int k) {
int res = 1;
while(k) {
if(k & 1) res = 1ll * res * x % P;
x = 1ll * x * x % P; k >>= 1;
}
return res;
}
inline int Mod(int x) { return x + ((x >> 31) & P); }
inline void pls(int &x, int v) { x = Mod(x + v - P); }
inline void dec(int &x, int v) { x = Mod(x - v); }
const int N = 1e5 + 10;
int n, m;
struct Node {
Node *ls, *rs;
int l, r, p;
Node() {}
Node(int _l, int _r) : l(_l), r(_r), p(0), ls(NULL), rs(NULL) {}
inline void down(int q) {
p = (1ll * p * (P + 1 - q) + 1ll * q * (P + 1 - p)) % P;
}
} ;
struct SegmentTree1 {
Node *root;
SegmentTree1() { root = NULL; }
void modify(Node *&x, int l, int r, int L, int R, int p) {
if(x == NULL) x = new Node(l, r);
if(L <= l && r <= R) { x -> down(p); return ; }
int mid = (l + r) >> 1;
if(L <= mid) modify(x -> ls, l, mid, L, R, p);
if(R > mid) modify(x -> rs, mid + 1, r, L, R, p);
return ;
}
void query(Node *x, int l, int r, int pos, int &p) {
if(x == NULL) return ;
// cerr << x -> p << endl;
p = (1ll * p * (P + 1 - x -> p) + 1ll * x -> p * (P + 1 - p) ) % P;
int mid = (l + r) >> 1;
if(pos <= mid) query(x -> ls, l, mid, pos, p);
else query(x -> rs, mid + 1, r, pos, p);
}
void Modify(int l, int r, int L, int R, int p) {
modify(root, l, r, L, R, p);
}
void Query(int l, int r, int pos, int &p) {
query(root, l, r, pos, p);
}
} ;
struct SegmentTree2 {
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
SegmentTree1 tr[N << 2];
void modify(int x, int l, int r, int L1, int R1, int L2, int R2, int p) {
if(L1 <= l && r <= R1) {
//cerr << l << ' ' << r << endl;
//cerr << x << endl;
tr[x].Modify(1, n, L2, R2, p); return ;
}
int mid = (l + r) >> 1;
if(L1 <= mid) modify(ls(x), l, mid, L1, R1, L2, R2, p);
if(R1 > mid) modify(rs(x), mid + 1, r, L1, R1, L2, R2, p);
}
void query(int x, int l, int r, int px, int py, int &p) {
tr[x].Query(1, n, py, p);
if(l == r) return ;
int mid = (l + r) >> 1;
if(px <= mid) query(ls(x), l, mid, px, py, p);
else query(rs(x), mid + 1, r, px, py, p);
}
} ;
SegmentTree1 Tree1;
SegmentTree2 Tree2;
int main() {
cin >> n >> m;
while(m --) {
int opt, l, r; cin >> opt >> l >> r;
if(opt == 1) {
int p = power(r - l + 1, P - 2);
if(l > 1) Tree2.modify(1, 1, n, 1, l - 1, l, r, p);
if(r < n) Tree2.modify(1, 1, n, l, r, r + 1, n, p);
Tree1.Modify(1, n, l, r, P + 1 - p);
pls(p, p);
Tree2.modify(1, 1, n, l, r, l, r, p);
if(l > 1) Tree1.Modify(1, n, 1, l - 1, 1);
if(r < n) Tree1.Modify(1, n, r + 1, n, 1);
}
else {
int ans = 0;
if(l == 1)
Tree1.Query(1, n, r, ans);
else
Tree2.query(1, 1, n, l - 1, r, ans);
cout << (P + 1 - ans) % P << endl;
}
}
return 0;
}