两道还不错的WC模拟题, 另外一道就纯靠看题解猜结论了.

仙人掌毒題

被期望和仙人掌嚇到了…

Description

給你一堆仙人掌. 每次會有這樣一個詢問: 如果對當前的圖做$T$次染色, 每次選一個點, 不管黑白都刷成黑色. 問最後, 白色點互相連接(如果有邊的話), 黑色點同理, 問連通塊個數的期望.

Solution

不會做(恐懼)….就去看題解了.

首先要明白, 在仙人掌裏, 聯通塊數 = 點 - 邊 + 環. 這事對於樹來說, 環上的一條邊被多算了一次, 所以補回來就好.

然後我們就分別計算一種顏色的點期望, 邊期望, 環期望, 把兩種顏色的加起來就好了.

一個點是白點(沒有被染色)的概率$P_w$是: $(\frac{n-1}{n})^t$. 所以期望是: $nP_w$.

相應的, 黑點$P_b$就是$1 - P_w$.

然後是邊. 一條邊兩端都是白點的概率是$(\frac{n-2}{n})^t$. “黑邊”的概率就有點麻煩了, 是1 - 至少有一個點是白點的概率, 爲: $1 - 2 \times P_w + P_{we}$.

最後是環. 白環也很好算, $(\frac{n - m}{n})^t$就好了. 黑環不好算, 但我們可以容斥原理.

也就是$\begin{align}\sum_{j=0}^{m}{(-1)^j {m \choose j} (\frac{n-j}{n})^t}\end{align}$.

只要每次插入邊的時候修改一下期望就可以了.

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;

inline int rd() {
  register int x = 0, f = 0, c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return f ? -x : x;
}

const ll mod = 998244353;
const int maxn = 300005;

int n, m, t, w;
int f[maxn], ch[maxn][2], s[maxn], v[maxn]; 
int FA[maxn];
bool tag[maxn], rev[maxn], vis[maxn];
int tot;
ll inv[maxn], fac[maxn], facinv[maxn];

inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % mod;
    base = base * base % mod;
    index >>= 1;
  }
  return ret;
}
int find(int x) {
  return FA[x] == x ? FA[x] : FA[x] = find(FA[x]);
}
void init() {
  fac[0] = facinv[0] = 1;
  inv[1] = fac[1] = facinv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    fac[i] = fac[i - 1] * i % mod;
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    facinv[i] = facinv[i - 1] * inv[i] % mod;
  }
}
inline ll C(int N, int M) {
  return fac[N] * facinv[M] % mod * facinv[N - M] % mod;
}

#define lson ch[x][0]
#define rson ch[x][1]
inline int isroot(int x) {
  return ch[f[x]][0] != x && ch[f[x]][1] != x;
}
inline int getid(int x) {
  return ch[f[x]][1] == x;
}
inline void pushup(int x) {
  s[x] = s[lson] + s[rson] + v[x];
  vis[x] = vis[lson] | vis[rson] | tag[x];
}
inline void pushdown(int x) {
  if (rev[x]) {
    swap(lson, rson);
    rev[lson] ^= 1;
    rev[rson] ^= 1;
    rev[x] = 0;
  }
}
inline void rotate(int x) {
  int y = f[x], z = f[y], k = getid(x);
  if (!isroot(y))
    ch[z][ch[z][1] == y] = x;
  ch[y][k] = ch[x][k ^ 1];
  ch[x][k ^ 1] = y;
  f[ch[y][k]] = y; f[y] = x; f[x] = z;
  pushup(y);
  pushup(x);
}
void pushpath(int x) {
  if (!isroot(x)) pushpath(f[x]);
  pushdown(x);
}
void splay(int x) {
  pushpath(x);
  for (int fa = 0; !isroot(x); rotate(x)) {
    if (!isroot(fa = f[x]))
      rotate(getid(fa) == getid(x) ? fa : x);
    pushup(x);
  }
}
inline void access(int x) {
  for (int y = 0; x; y = x, x = f[x])
    splay(x), ch[x][1] = y, pushup(x);
}
inline void makeroot(int x) {
  access(x); splay(x); rev[x] ^= 1;
}
inline void link(int x, int y) {
  makeroot(x); f[x] = y;
}
inline void split(int x, int y) {
  makeroot(x); access(y); splay(y); 
}
void dfs(int x) {
  if (lson) dfs(lson);
  if (rson) dfs(rson);
  if (x > n) tag[x] = 1;
  pushup(x);
}
#undef lson
#undef rson

int main() {
  freopen("cactus.in", "r", stdin);
  freopen("cactus.out", "w", stdout);
  n = rd(); m = rd(); t = rd(); w = rd();
  init();
  //printf("%lld %lld\n", n * inv[n] % mod, C(100, 0));
  ll BASIC_WHITE_PROB = quick_power(inv[n] * (n - 1) % mod, t);
  ll BASIC_WHITE_EDGE = quick_power(inv[n] * (n - 2) % mod, t);
  ll BASIC_BLACK_EDGE = ((mod + 1 - 2ll * BASIC_WHITE_PROB % mod) % mod
                         + BASIC_WHITE_EDGE) % mod;
  ll E = 1ll * n * BASIC_WHITE_PROB % mod;
  if (w) E = (E + 1ll * n * (1 + mod - BASIC_WHITE_PROB) % mod) % mod;
  for (int i = 1; i <= n; ++i) {
    FA[i] = i;
  }

  int frm, to; 
  tot = n;
  while (m--) {
    frm = rd(); to = rd();
    int fx = find(frm), fy = find(to);
    //printf("%d %d\n", fx, fy);
    if (fx != fy) {
      //puts("new");
      FA[fx] = fy;
      v[++tot] = 1;
      link(frm, tot);
      link(tot, to);
      E = (E - BASIC_WHITE_EDGE + mod) % mod;
      if (w) E = (E - BASIC_BLACK_EDGE + mod) % mod;
      printf("%lld\n", E);
    } else {
      split(frm, to);
      if (vis[to]) printf("%lld\n", E);
      else {
        E = (E - BASIC_WHITE_EDGE + mod) % mod;
        if (w) E = (E - BASIC_BLACK_EDGE + mod) % mod;
        //printf("%lld\n", E);
        dfs(to);
        int M = s[to] + 1;
        //printf("%d\n", M);
        E = (E + quick_power((n - M) * inv[n] % mod, t)) % mod;
        //printf("%lld\n", E);
        if (w) {
          //ll tmp = 0;
          for (int i = 0; i <= M; ++i) {
            ll ret = C(M, i) * quick_power((n - i) * inv[n] % mod, t) % mod;
            //printf("%lld\n", ret);
            if (i & 1) ret = mod - ret;
            //else tmp = (tmp + ret) % mod;
            E = (E + ret) % mod;
            //printf("-%lld\n", E);
          }
          //E = (E + tmp) % mod;
        }
        printf("%lld\n", E);
      }
    }
  } 
  fclose(stdin);
  fclose(stdout);
  return 0;
}

立體幾何題

Description

給一個底面爲$n \times n$的, 單位立方體堆疊成的幾何體的主視圖和側視圖.

在沒有俯視圖的情況下, 計算最多可以有多少個立方體.

$n \le x10^5$.

Solution

思路還是很自然的, 就一路從暴力到正解.

先想暴力, 發現一個$(i,j)$的位置就是$\min{(a_i, b_j)}$. 就可以$n^2$了.

然後發現不修改的話可以排序後二分.

然後發現修改一邊也可以排序後二分.

然後發現都修改可以平衡樹上二分.

做完啦.

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;

inline int rd() {
  register int x = 0, f = 0, c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return f ? -x : x;
}

const int maxn = 2e+5 + 5;

int n, m, a[maxn], b[maxn];
ll ans;

struct Treap {
  struct node {
    int ch[2], v, siz, k, w;
    ll sum;
    node() {
      ch[1] = ch[0] = 0;
      v = w = siz = k = 0;
    }
  }t[maxn];
  int ptr, rt;

  #define lson t[p].ch[0]
  #define rson t[p].ch[1]
  inline int newnode(int val) {
    ++ptr;
    t[ptr].v = val; t[ptr].w = rand();
    t[ptr].siz = t[ptr].k = 1;
    t[ptr].sum = val;
    return ptr;
  }
  inline void pushup(int p) {
    t[p].siz = t[lson].siz + t[rson].siz + t[p].k;
    t[p].sum = t[lson].sum + t[rson].sum + 1ll * t[p].v * t[p].k;
  }
  inline void rturn(int &p) {
    int q = lson;
    lson = t[q].ch[1]; t[q].ch[1] = p; p = q;
    pushup(rson);
    pushup(p);
  }
  inline void lturn(int &p) {
    int q = rson;
    rson = t[q].ch[0]; t[q].ch[0] = p; p = q;
    pushup(lson);
    pushup(p);
  }
  void Insert(int &p, int x) {
    //printf("%d\n", p);
    if (!p) {
      p = newnode(x);
      return;
    }
    t[p].siz++; t[p].sum += x;
    if (t[p].v == x) {
      t[p].k++;
      //t[p].sum += x;
      return;
    } else if (t[p].v < x) {
      Insert(rson, x);
      if (t[rson].w < t[p].w) lturn(p);
    } else {
      Insert(lson, x);
      if (t[lson].w < t[p].w) rturn(p);
    }
  }
  void Delete(int &p, int x) {
    if (!p) return;
    if (t[p].v == x) {
      if (t[p].k > 1) t[p].k--, t[p].siz--, t[p].sum -= x;
      else {
        if (!(lson && rson)) p = lson + rson;
        else if (t[rson].w > t[lson].w)
          rturn(p), Delete(p, x);
        else lturn(p), Delete(p, x);
      }
    } else {
      t[p].siz--; t[p].sum -= x;
      if (t[p].v < x) Delete(rson, x);
      else Delete(lson, x);
    }
  }
  ll GetLower(int p, int k) {
    //printf("%d %d %d %lld\n", p, t[p].v, k, t[p].sum);
    if (!p) return 0;
    if (t[p].v == k) {
      //printf("ret %lld\n", t[p].sum - t[rson].sum);
      return t[p].sum - t[rson].sum;
    } else if (t[p].v < k) {
      ll ret = t[p].sum - t[rson].sum + GetLower(rson, k);
      //printf("ret %lld\n", ret);
      return ret;
    } else {
      ll ret = GetLower(lson, k);
      //printf("ret %lld\n", ret);
      return ret;
    }
  }
  int GetLowerSize(int p, int k) {
    if (!p) return 0;
    if (t[p].v == k) {
      return t[p].siz - t[rson].siz;
    } else if (t[p].v < k) {
      return t[p].siz - t[rson].siz + GetLowerSize(rson, k);
    } else {
      return GetLowerSize(lson, k);
    }
  }
  #undef lson
  #undef rson  
}A, B;

int main() {
  freopen("graph.in", "r", stdin);
  freopen("graph.out", "w", stdout);
  n = rd();
  for (int i = 1; i <= n; ++i) {
    a[i] = rd(); A.Insert(A.rt, a[i]);
    //printf("%d\n", A.rt);
    //printf("%d\n", A.t[A.rt].siz);
  } 
  for (int i = 1; i <= n; ++i) {
    b[i] = rd(); B.Insert(B.rt, b[i]);
    //printf("%d\n", B.rt);
  }
  for (int i = 1; i <= n; ++i) {
    ll lsum = B.GetLower(B.rt, a[i]);
    int rsiz = n - B.GetLowerSize(B.rt, a[i]);
    //printf("%lld %d\n", lsum, rsiz);
    //puts("---");
    ans += lsum + 1ll * rsiz * a[i];
  }
  printf("%lld\n", ans);
  m = rd();
  int typ, p, x;
  while (m--) {
    typ = rd(); p = rd(); x = rd();
    if (typ) {
      ll lsum = A.GetLower(A.rt, b[p]);
      int rsiz = n - A.GetLowerSize(A.rt, b[p]);
      ans -= lsum + 1ll * rsiz * b[p];
      B.Delete(B.rt, b[p]);
      b[p] = x;
      lsum = A.GetLower(A.rt, b[p]);
      rsiz = n - A.GetLowerSize(A.rt, b[p]);
      ans += lsum + 1ll * rsiz * b[p];
      B.Insert(B.rt, b[p]);
    } else {
      ll lsum = B.GetLower(B.rt, a[p]);
      int rsiz = n - B.GetLowerSize(B.rt, a[p]);
      ans -= lsum + 1ll * rsiz * a[p];
      A.Delete(A.rt, a[p]);
      a[p] = x;
      lsum = B.GetLower(B.rt, a[p]);
      rsiz = n - B.GetLowerSize(B.rt, a[p]);
      ans += lsum + 1ll * rsiz * a[p];
      A.Insert(A.rt, a[p]);
    }
    printf("%lld\n", ans);
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}