2020牛客暑期多校训练营（第九场）C.Groundhog and Gaming Time

发表于 | 阅读数

每个线段被选到概率为$1/2$,求所有线段被选到的交的长度的平方的期望。

公式化的离散化线段变成左开右闭

然后考虑每个区间的贡献，$(x1+x2)\times (x1+x2)=x1(x1+x2)+x2(x1+x2)$

所以需要计算所有其他可行区间的总和。

线段需要包含$x_i$，则维护下左端点在$[0,i+1]$-右端点$[0,i+1]$这些线段即可。

如果一个线段被覆盖了$k$次，显然这个线段贡献为$2^k-1$，$-1$即$len_i\times\sum len_j$

用线段树维护区间修改乘，区间和。即可。

代码 
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 998244353;
const int P = 998244353, gi = 3;
// const double pi = acos(-1.0);
int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

int qpow(int a, int x, int mo)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * a * res % mo;
        a = 1ll * a * a % mod;
        x >>= 1;
    }
    return res;
}
int li[N], num;
const int SEN = 4e5 + 10;
struct segmentTree
{
    int sum[SEN << 2], lazy[SEN << 2];
    void addtag(int pos, int l, int r, int w)
    {
        lazy[pos] = 1ll * lazy[pos] * w % mod;
        sum[pos] = 1ll * sum[pos] * w % mod;
    }
    void pushdown(int pos, int l, int r)
    {
        if (lazy[pos] != 1)
        {
            int w = lazy[pos];
            int mid = (l + r) >> 1;
            addtag(pos << 1, l, mid, w);
            addtag(pos << 1 | 1, mid + 1, r, w);
            lazy[pos] = 1;
        }
    }
    void pushup(int pos)
    {
        sum[pos] = inc(sum[pos << 1 | 1], sum[pos << 1]);
    }
    void build(int pos, int l, int r)
    {
        sum[pos] = 0;
        lazy[pos] = 1;
        if (l == r)
        {
            sum[pos] = li[l + 1] - li[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(pos << 1, l, mid);
        build(pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
    void update(int ql, int qr, int w, int pos, int l, int r)
    {

        if (ql <= l && r <= qr)
        {
            addtag(pos, l, r, w);
            return;
        }
        pushdown(pos, l, r);
        int mid = (l + r) >> 1;

        if (ql <= mid)
            update(ql, qr, w, pos << 1, l, mid);
        if (qr > mid)
            update(ql, qr, w, pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }
} t;
int l[N], r[N];
bool cmp1(int x, int y)
{
    return l[x] < l[y];
}
bool cmp2(int x, int y)
{
    return r[x] < r[y];
}
int x[N], y[N];
int main()
{
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        l[i] = read();
        r[i] = read();
        r[i]++;
        li[++num] = r[i];
        li[++num] = l[i];
    }
    sort(1 + li, 1 + li + num);
    num = unique(1 + li, 1 + li + num) - li - 1;
    for (int i = 1; i <= n; i++)
        l[i] = lower_bound(li + 1, li + 1 + num, l[i]) - li,
        r[i] = lower_bound(li + 1, li + 1 + num, r[i]) - li;
    num--;
    t.build(1, 1, num);
    for (int i = 1; i <= n; ++i)
        x[i] = y[i] = i;
    sort(x + 1, x + 1 + n, cmp1);
    sort(y + 1, y + 1 + n, cmp2);
    int cnt1 = 1, cnt2 = 1;
    int ans = 0;
    int inv2 = qpow(2, mod - 2, mod);
    for (int i = 1; i <= num; i++)
    {

        while (cnt1 <= n && l[x[cnt1]] <= i)
            t.update(l[x[cnt1]], r[x[cnt1]] - 1, 2, 1, 1, num), cnt1++;
        while (cnt2 <= n && r[y[cnt2]] <= i)
            t.update(l[y[cnt2]], r[y[cnt2]] - 1, inv2, 1, 1, num), cnt2++;

        ans = inc(1ll * t.sum[1] * (li[i + 1] - li[i]) % mod, ans);
    }

    ans = del(ans, 1ll * (li[num + 1] - li[1]) * (li[num + 1] - li[1]) % mod);
    ans = 1ll * ans * qpow(inv2, n, mod) % mod;
    cout << ans << endl;
}