「 ZJOI 2019 」 선분 수 - 선분 수

Description
링크 입 니 다.
Solution
이 문 제 는 매번 12 \ frac {1} {2} 21 실행 1 동작 으로 볼 수 있 습 니 다. t a g tag 배열 의 합 에 대한 기대 곱 하기 2 p 2 ^ p 2p (p p p 는 1 작업 횟수 입 니 다.
기대 하 는 선형 성에 따라 각 노드 의 t a g tag tag 를 1 1 1 1 로 계산 하 는 기대 f i fi fi, g i gi gi 는 i i 에서 뿌리 까지 의 경 로 는 t a g = 1 tag = 1 tag = 1 tag = 1 의 확률 이 있 음 을 나타 낸다.[l, r] [l, r] [l, r] 를 l o g log 개의 선분 트 리 구간 으로 나 누 어 각 구간 이 답 에 미 치 는 영향 을 고려 하면 이 구간 에서 뿌리 까지 의 경로 에 있 는 점 (그 자체 포함 되 지 않 음) 의 f i ← f i 2, g i ← g i 2 f 를 발견 할 수 있 습 니 다.i \gets \frac{f_i}{2},g_i \ \ gets \ \ frac {g i} {2} fi ← 2fi, gi ← 2gi, 이 경로 에 가 까 운 점 의 f i ← f i + g i 2, g i fi \gets \frac{f_i+g_i}{2},g_i fi ← 2fi + gi, gi 는 변 하지 않 습 니 다. 이 구간 자체 f i ← f i + 1 2 fi \ gets \ \ frac {f i + 1} {2} fi ← 2fi + 1, 그 하위 트 리 의 g i ← g i + 1 2gi \gets \frac{g_i+1}{2} gi​←2gi​+1​。
여기 서 의 수정 은 모두 O (l o g) O (log) O (log) 등급 이 고 폭력 적 으로 수정 하면 됩 니 다.g i g진짜.i'=1-g_진짜.i'\gets=\frac{g_i'}{2} gi′​←=2gi′​​

#include 
using namespace std;

inline int gi()
{
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	int sum = 0;
	while('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

typedef long long ll;
const int maxn = 100005, mod = 998244353;

int n, m, P = 1, inv[maxn], f[maxn << 2], g[maxn << 2], lzy[maxn << 2], ans;

#define mid ((l + r) >> 1)
#define lch (s << 1)
#define rch (s << 1 | 1)

void build(int s, int l, int r)
{
	g[s] = 1;
	if (l == r) return ;
	build(lch, l, mid);
	build(rch, mid + 1, r);
}

inline void mdf_f(int x, int v) {ans = (ans - f[x] + mod) % mod; f[x] = (ll)(f[x] + v) * inv[1] % mod; ans = (ans + f[x]) % mod;}
inline void mdf_g(int x, int v) {g[x] = (ll)g[x] * inv[v] % mod; lzy[x] += v;}
inline void push_down(int s)
{
	if (!lzy[s]) return ;
	mdf_g(lch, lzy[s]); mdf_g(rch, lzy[s]);
	lzy[s] = 0;
}

void modify(int s, int l, int r, int ql, int qr)
{
	if (ql <= l && r <= qr) return mdf_f(s, 1), mdf_g(s, 1), void();
	push_down(s);
	if (ql <= mid) modify(lch, l, mid, ql, qr);
	else mdf_f(lch, mod + 1 - g[lch]);
	if (mid < qr) modify(rch, mid + 1, r, ql, qr);
	else mdf_f(rch, mod + 1 - g[rch]);
	mdf_f(s, 0); g[s] = (ll)(g[s] + 1) * inv[1] % mod;
}

int main()
{
	n = gi(); m = gi();
	inv[0] = 1; inv[1] = (mod + 1) >> 1;
	for (int i = 2; i <= n; ++i) inv[i] = (ll)inv[i - 1] * inv[1] % mod;
	
	build(1, 1, n);
	for (int op, l, r, i = 1; i <= m; ++i) {
		op = gi(); 
		if (op == 1) l = gi(), r = gi(), P = (P << 1) % mod, modify(1, 1, n, l, r);
		else printf("%lld
", (ll)ans * P % mod);
	}
	
	return 0;
}