LOJ#3043. 「ZJOI2019」线段树
计数转期望的一道好题……
每个点设两个变量\(p,q\)表示这个点有\(p\)的概率有标记，有\(q\)的概率到祖先的路径上有个标记
被覆盖的点$0.5p + 0.5 \rightarrow p ,0.5q + 0.5\rightarrow q $
被覆盖的点子树中的点\(p\rightarrow p,0.5q + 0.5 \rightarrow q\)
经过的点\(0.5p \rightarrow p,0.5q \rightarrow q\)
未被经过，被pushdown，\(0.5p + 0.5q \rightarrow p,q\rightarrow q\)
根本没事\(p\rightarrow p,q\rightarrow q\)
最后统计\(p\)的和，设操作次数是\(tot\)，乘上\(2^{tot}\)即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 200005
#define ba 47
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int l,r,p,q,m,a;
}tr[MAXN * 4];
const int MOD = 998244353;
int N,ans,M,tot;
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
void upd(int &x,int y) {
x = inc(x,y);
}
void upm(int &x,int y) {
x = mul(x,y);
}
int fpow(int x,int c) {
int res = 1,t = x;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
void addlz(int u,int m,int a) {
upm(tr[u].m,m);upm(tr[u].a,m);
upd(tr[u].a,a);
upm(tr[u].q,m);upd(tr[u].q,a);
}
void pushdown(int u) {
addlz(u << 1,tr[u].m,tr[u].a);
addlz(u << 1 | 1,tr[u].m,tr[u].a);
tr[u].m = 1;tr[u].a = 0;
}
void build(int u,int l,int r) {
tr[u].l = l;tr[u].r = r;tr[u].a = 0;tr[u].m = 1;
if(l == r) return;
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
}
void get_diff(int &x,int y) {
upd(ans,inc(y,MOD - x));
x = y;
}
void Modify(int u,int l,int r) {
if(tr[u].l == l && tr[u].r == r) {
get_diff(tr[u].p,mul(tr[u].p + 1,(MOD + 1) / 2));
addlz(u,(MOD + 1) / 2,(MOD + 1) / 2);
return;
}
get_diff(tr[u].p,mul(tr[u].p,(MOD + 1) / 2));
tr[u].q = mul(tr[u].q,(MOD + 1) / 2);
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) {
Modify(u << 1,l,r);
get_diff(tr[u << 1 | 1].p,mul((MOD + 1) / 2,inc(tr[u << 1 | 1].p,tr[u << 1 | 1].q)));
}
else if(l > mid) {
Modify(u << 1 | 1,l,r);
get_diff(tr[u << 1].p,mul((MOD + 1) / 2,inc(tr[u << 1].p,tr[u << 1].q)));
}
else {
Modify(u << 1,l,mid);Modify(u << 1 | 1,mid + 1,r);
}
}
void Solve() {
read(N);read(M);
int op,l,r;
build(1,1,N);
for(int i = 1 ; i <= M ; ++i) {
read(op);
if(op == 1) {
read(l);read(r);
++tot;
Modify(1,l,r);
}
else {
out(mul(ans,fpow(2,tot)));enter;
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}