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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#define LL long long
#define pii pair<int, int>
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define INF (0x7fffffff)
#define MAXN (100000 + 5)
#define MAXZ (300000 + 5)
#define Aufun (998244353)
using namespace std;
struct node
{
int le, ri, zz;
set<int> hvntbeen;
} b[MAXZ << 3];
int n, m, a[MAXN], sora[MAXZ];
pii mine[MAXN];
LL ans;
queue<int> tosolve;
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].zz = 0;
if (le == ri)
return ;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
}
void xg1(int dq, int le, int ri, int zh)
{
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].hvntbeen.insert(zh);
++b[dq].zz;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
xg1(RS(dq), le, ri, zh);
else if (ri <= mi)
xg1(LS(dq), le, ri, zh);
else
xg1(LS(dq), le, mi, zh), xg1(RS(dq), mi + 1, ri, zh);
}
void xg2(int dq, int le, int ri, int zh)
{
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].hvntbeen.erase(zh);
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
xg2(RS(dq), le, ri, zh);
else if (ri <= mi)
xg2(LS(dq), le, ri, zh);
else
xg2(LS(dq), le, mi, zh), xg2(RS(dq), mi + 1, ri, zh);
}
LL fp(int bx)
{
if (!bx)
return 1;
LL re = fp(bx >> 1);
re = (re * re) % Aufun;
if (bx & 1)
re = (re << 1) % Aufun;
return re;
}
void cx(int dq, int wz, int zz, int fz)
{
fz += b[dq].hvntbeen.size(), zz += b[dq].zz;
for (set<int>::iterator i = b[dq].hvntbeen.begin(); i != b[dq].hvntbeen.end(); i++)
tosolve.push(*i);
if (b[dq].le == b[dq].ri)
{
ans = (ans + (fp(fz) - 1) * fp(zz - fz)) % Aufun;
while (ans < 0)
ans += Aufun;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
cx(LS(dq), wz, zz, fz);
else
cx(RS(dq), wz, zz, fz);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &mine[i].first, &mine[i].second), sora[++sora[0]] = mine[i].first, sora[++sora[0]] = mine[i].second;
for (int i = 1; i <= m; i++)
scanf("%d", &a[i]), sora[++sora[0]] = a[i];
sort(sora + 1, sora + sora[0] + 1);
sora[0] = unique(sora + 1, sora + sora[0] + 1) - sora - 1;
js(1, 1, sora[0]);
for (int i = 1; i <= n; i++)
{
mine[i].first = lower_bound(sora + 1, sora + sora[0] + 1, mine[i].first) - sora;
mine[i].second = lower_bound(sora + 1, sora + sora[0] + 1, mine[i].second) - sora;
xg1(1, mine[i].first, mine[i].second, i);
}
sort(a + 1, a + m + 1);
for (int i = 1; i <= m; i++)
{
a[i] = lower_bound(sora + 1, sora + sora[0] + 1, a[i]) - sora;
cx(1, a[i], 0, 0);
while (!tosolve.empty())
{
int dq = tosolve.front();
tosolve.pop();
xg2(1, mine[dq].first, mine[dq].second, dq);
}
}
printf("%lld", ans);
return 0;
}
|