2020夏の牛客多校訓練キャンプ第9回(C)Groundhog and Gaming Time(数学の期待、線分の木、逆元)

Groundhog and Gaming Time
原題はこちらをご覧ください
タイトルの説明
P K U W C 2019 d a y 2 PKUWC 2019 day 2 PKUWC 2019 day 2夜、n{n}n人の同級生はS o e t d i t,T X 114596673,Z P A Y A U R,G r o u n d h o g Soetdit,TX 1145966773,ZPAYAUR,Groundhog Soetdit,TX 114596673,ZPAYAUR,Groundhog Groundhog彼らは夜明けまで一晩分担する.その夜、彼らは次々とインターネットを利用した.[i][i][i][i][i,R i][L_i,R_i][Li,Ri]から[i][i][i][i,R_i][Li,Ri]がオンラインになる.しかし、ある人は彼らの先生が夜来ると報告した.誰もが1 2frac{1}{2}21の可能性を持ってメッセージを受信し、そのメッセージを受信した人は夜インターネットを利用しません.彼らが利用できるゲーム時間は、すべてのプレイヤーがオンラインになっているときです.そこで,利用可能な時間モードの二乗に対する期待は,n{n}n個のセグメント[L i,R i][L_i,R_i][Li,Ri]があり,各セグメントが1 2frac{1}{2}21を選択する可能性があるという問題を考え始めた.問題は計算∣[L a 1,R a 1]∩[L a 2,R a 2]∩⋯∩[L a m,R a m]∣2|[L_{a_1},R_{a_1}]cap[L_{a_2},R_{a_{a_2}]capcdotscap[L_{a_m},R_{a_m}|^2∣[La1,Ra1]∩[La2,Ra2]∩[Lam,Ram]∣[Lam,Ram]∩[Lam,Ram]ジルコニウム2 m o d mod mod 998244353{998244353}998244353の期待値.a i a_i aiは,選択したi t h{i^{th}}ith番目のセグメントの数を表す.
説明を入力:
最初の行には、学生数を表す整数n{n}nが含まれます.次のn{n}n行はそれぞれ2つの整数L i,R i L_を含むi,R_i Li,Ri,これはi i番目の学生のゲーム時間を表す.
出力の説明:
出力行には、解答モード998244353{998244353}998244353が含まれる.
サンプル入力:

6
2 2
1 2
1 4
1 5
3 5
3 6

サンプル出力:

405536771

考え方:
期待を求める方法はいろいろありますが、この問題ではdpを期待して期待を求める方法を選びます.まずデータが大きいため,まずデータを離散化し,次に左右の端点昇順に並べ替え,各セグメントの答えへの寄与を考慮する必要がある.区間Aがb線分に現れるとすると,P(A)=2 a−1 2 nP(A)=frac{2^a−1}{2^n}P(A)=2 n 2 a−1は全選択できないので1を減らす.従って、E(A)=2 a−1 2 n∗∣A∣(E(A)=frac{2^a−1}{2^n}*|A|(E(A)=2 n 2 a−1∗A∣(2つの'|'はsizeを表すこともできるそう))では、n n n本の線分の全てにおいてP i P_i Piの寄与(a i(a_i(ai線分はAを含む)A):ΣE(Q)∗P i∣sum E(Q)*|P_i| ∑E(Q)∗∣Pi​∣ = ∑ j ( 2 b j − 1 2 n ∗ ∣ Q j ∣ ) ∗ ∣ P i ∣ =\sum_j(\frac{2^{b_j}-1}{2^n}*|Q_j|)*|P_i| =∑j​(2n2bj​−1​∗∣Qj​∣)∗∣Pi​∣ = ∑ j ( 2 b j 2 n ∗ ∣ Q j ∣ ) ∗ ∣ P i ∣ − ∣ P i ∣ ∗ m x =\sum_j(\frac{2^{b_j}}{2^n}*|Q_j|)*|P_i|-|P_i|*mx=Σj(2 n 2 bj
A C AC AC C o d e Code Code:

#include 
#define ll long long
using namespace std;
const int mod = 998244353;
const int MAXN = 1e6+5;
const int N = 1e9 + 1;
ll a[MAXN << 2], b[MAXN << 2], trl[MAXN], trr[MAXN], l[MAXN];
ll r[MAXN], lsh[MAXN], cnt, ans;
int n;
ll ksm (ll a, ll b) {
	ll ret = 1;
	while (b){
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}//       
bool cmp1 (int x, int y){ return l[x] < l[y]; }
bool cmp2 (int x, int y){ return r[x] < r[y]; }
void build_tree (int pos, int l, int r){//     
	a[pos] = lsh[r + 1] - lsh[l];
	b[pos] = 1;
	if (l == r) return;
	int mid = l + r >> 1;
	build_tree (pos << 1, l, mid);
	build_tree (pos << 1 | 1, mid + 1, r);
}
void f (int pos, int l, int r, ll num, int x, int y){//   [l,r]    *num 
	if(l <= x && r >= y){
		a[pos] = a[pos] * num % mod;
		b[pos] = b[pos] * num % mod;
		return;
	}
	int mid = x + y >> 1;
	if (l <= mid) f (pos << 1, l, r, num, x, mid);
	if (r > mid) f (pos <<1 | 1, l, r, num, mid + 1, y);
	a[pos] = (a[pos << 1] + a[pos << 1 | 1]) * b[pos] % mod;//b[pos]  lazy  ，          。 
}
int main (){
	lsh[1] = 0;
	lsh[2] = N;//         ，                
	cnt = 2;
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i){
		scanf("%lld%lld", l + i ,r + i);
		lsh[++cnt] = l[i];
		lsh[++cnt] = ++r[i];
	}
	sort (lsh + 1, lsh + cnt + 1);
	cnt = unique(lsh + 1, lsh + cnt + 1) - lsh - 1;//    
	build_tree(1, 1, cnt - 1);//    ，i         [i,i+1]    
	for (int i = 1; i <= n; ++i){
		l[i] = lower_bound(lsh + 1, lsh + cnt + 1, l[i]) - lsh;//      
		r[i] = lower_bound(lsh + 1, lsh + cnt + 1, r[i]) - lsh;
	}
	for (int i = 1; i <= n; ++i) trl[i] = trr[i] = i;
	sort (trl + 1, trl + n + 1, cmp1);//         
	sort (trr + 1, trr + n + 1, cmp2);//         
	int t1 = 1, t2 = 1; 
	for (int i = 1; i < cnt; ++i){//    [i,i+1]，                。                  
	// m   ，  a       [i,i+1]。   a         ，           。
	//a   ， b       [j,j+1],   [j,j+1]   =  *(2^b-1)/2^n。  -1 /2^n      
		for (; t1 <= n && l[trl[t1]] <= i; ++t1)//         i       
			f(1, l[trl[t1]], r[trl[t1]] - 1, 2, 1, cnt - 1);//    ，        *2 
		for (;t2 <= n && r[trr[t2]] <= i; ++t2)//         i       
			f(1, l[trr[t2]], r[trr[t2]] - 1, ksm(2, mod - 2), 1, cnt - 1);//    ，        -2 
		ans = (ans + a[1] * (lsh[i + 1] - lsh[i])) % mod;//    ，  ans=sum(    *   ) 
	}//        ，                ，   =  *(2^b-1)/2^n  -1 
	ans = (ans + mod - 1ll * N * N % mod) % mod;//              
	for (int i = 1; i <= n; ++i)
		ans = ans * ksm(2, mod - 2) % mod;// 2^n，     
	printf("%lld
", ans);
}