涂鸦* CCPC wannafly-布布扣-bubuko.com

输入描述

第一行三个整数 $\leq n,m \leq 10^3,1 \leq q \leq 2 \times 10^5)n,m,q(1≤n,m≤103,1≤q≤2×105)。$

接下来 $l_i,r_i(1 \leq l_i \leq r_i \leq m)li?,ri?(1≤li?≤ri?≤m)，表示第 ii 行的属性。$

接下来 $lx_i,ly_i,rx_i,ry_i(1 \leq lx_i \leq rx_i \leq n, 1 \leq ly_i \leq ry_i \leq m)lxi?,lyi?,rxi?,ryi?(1≤lxi?≤rxi?≤n,1≤lyi?≤ryi?≤m)，表示一个矩形。$

输出描述

输出一行一个整数表示答案，棋盘上黑色格子数量的期望对 $\frac{x}{y}yx?，输出 x \times y^{-1} \mod 998244353x×y−1mod998244353。$

样例输入 1

样例输出 1

831870299

对于某一个点来说，它被染成黑点的概率是 $\frac{(x - l + 1) \cdot (r - x + 1) \cdot 2}{(r - l + 1) \cdot (r - l + 2)}$

然后二维BIT维护矩形，最后将所有未被矩形覆盖的期望加起来即可。

BIT本身维护的就是一个前缀和，所以说在查询每个点的被覆盖的次数的时候

只需查询这一个点即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 1010
 6 const ll p = (ll)998244353;
 7 const ll MOD = (ll)998244353;
 8 int n, m, q;
 9 ll inv[N];
10 int ans[N][N];
11 
12 namespace BIT
13 {
14     int a[N][N];
15     void init() { memset(a, 0, sizeof a); }
16     void update(int x, int y, int v)
17     {
18        // for (int i = x; i > 0; i -= i & -i)
19                     for (int i = x; i <=n ; i += i & -i)
20                             for (int j = y; j <=m; j += j & -j)
21 
22           //  for (int j = y; j > 0; j -= j & -j)
23                 a[i][j] += v;
24     }
25     int query(int x, int y)
26     {
27         int res = 0;
28       //  for (int i = x; i < N; i += i & -i)
29             for(int i=x;i;i-=i&(-i))
30                 for(int j=y;j;j-=j&(-j))
31                  res += a[i][j];
32           //  for (int j = y; j < N; j += j & -j)
33     //   cout<<"que: "<<x<<" "<<y<<" " <<res<<endl;
34         return res;
35     }
36     void update(int x1, int y1, int x2, int y2)
37     {
38       /*  update(x1 - 1, y1 - 1, 1);
39         update(x1 - 1, y2, -1);
40         update(x2, y1 - 1, -1);
41         update(x2, y2, 1);
42 
43         */
44 
45 
46         update(x1, y1, 1);
47         update(x1 , y2+1, -1);
48                 update(x2+1, y1 , -1);
49          update(x2 +1, y2 +1, 1);
50 
51     }
52 }
53 
54 int main()
55 {
56     inv[1] = 1;
57     for (int i = 2; i < N; ++i) inv[i] = inv[p % i] * (p - p / i) % p;
58     while (scanf("%d%d%d", &n, &m, &q) != EOF)
59     {
60         memset(ans, 0, sizeof ans); BIT::init();
61         for (int i = 1, l, r; i <= n; ++i)
62         {
63             scanf("%d%d", &l, &r);
64             for (int j = l; j <= r; ++j)
65                 ans[i][j] = 2ll * (j - l + 1) %p * (r - j + 1) %p * inv[r - l + 1] % p * inv[r - l + 2] % p;
66             //cout << ans[i][l] * (r - l + 1) * (r - l + 2) / 2 % p << endl;
67         }
68         for (int qq = 1; qq <= q; ++qq)
69         {
70             int x1, x2, y1, y2;
71             scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
72             BIT::update(x1, y1, x2, y2);
73         }
74         ll res = 0;
75 
76    /*     for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
77         {
78              int t=BIT::query(i,j);
79             cout<<i<<" "<<j<<" "<<t<<endl;
80         }*/
81         for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
82         {
83             int t=BIT::query(i,j);//-BIT::query(i-1,j)-BIT::query(i,j-1)+BIT::query(i-1,j-1);
84            // cout<<i<<" "<<j<<" "<<t<<endl;
85             if (!t)
86         {
87            // cout << i << " " << j << endl;
88             res = (res + ans[i][j]) % p;
89         }
90 
91 
92         }
93         printf("%lld\n", res);
94 
95     }
96     return 0;
97 }