EDU95

(Updated: )
(10 mins to read)

D. Trash Problem

有n堆物品排成一条线，可以将同一位置的所有物品同时移动到相邻的位置，q次操作，每次可以添加一堆物品或者删除一堆物品，并询问将所有物品移动成小于等于2堆的最小代价$n \leq 10^5,q \leq 10^5$第一反应应该是中位数，但要发现每次必须同时移动同一位置的所有物品，那么如果移成一堆，答案就是最大坐标$x_n$​-最小坐标$x_1$​，考虑移成两堆，只要枚举一个分割点i，然后前面的代价是$x_i-x_1$​，后面的代价是$x_n-x_{i+1}$​，所以最小代价就是最大坐标-最小坐标-相邻坐标的最大差值。利用multiset动态维护即可tips:可以用rbegin来指向最后一个元素，比--end方便点

E. Expected Damage

有n个怪物，第i个怪物的伤害为$d_i$​，现在有一个盾牌，有属性a和b，当$a\gt 0$时，可以免疫$\lt b$的伤害，而$\geq b$的伤害会使$a-1$（不会受到伤害），而当$a=0$时，会受到所有的伤害。现在有m种盾牌，对于每种需要回答在n!种打怪方式下，受到的伤害的期望$n \leq 2\times 10^5,m \leq 2\times 10^5$考虑每种怪物的贡献，容易发现可以分成伤害$<b$和$\geq b$两类计算最好的做法是从整体上考虑定义ge为伤害$\geq b$的怪物数量，le为$<b$的怪物数量，将d排序后lowerbound即可对于伤害$\geq b$的ge个怪物，排在前a个是没有伤害的，因为会被盾牌挡掉，所以有贡献的概率就是$\frac{ge-a}{ge}$，再乘上这些怪物的伤害和即可对于伤害$\lt b$的le个怪物，必须保证前面有至少a个伤害$\geq b$的怪物，可以固定住ge个怪物的位置，那么现在有ge+1个空位，前a个是没有贡献的，所以有贡献的概率就是$\frac{ge+1-a}{ge+1}$​，再乘上一个前缀和即可

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
int n, m, d[N], sum[N], inv[N];
void init()
{
  inv[0] = inv[1] = 1;
  for(int i=2; i<=n; i++) inv[i] = 1ll*(mod-mod/i)*inv[mod%i]%mod;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  init();
  for(int i=1; i<=n; i++) cin >> d[i];
  sort(d+1, d+n+1);
  for(int i=1; i<=n; i++) sum[i] = (sum[i-1] + d[i])%mod;
  for(int i=1; i<=m; i++)
  {
    int a, b;
    cin >> a >> b;
    int le = lower_bound(d+1, d+n+1, b) - d - 1;
    int ge = n - le;
    int x = (ge < a ? 0 : 1ll*(ge-a)*inv[ge]%mod*(sum[n]-sum[le])%mod);
    int y = (ge < a ? 0 : 1ll*(ge+1-a)*inv[ge+1]%mod*sum[le]%mod);
    printf("%d\n", ((x+y)%mod+mod)%mod);
  }
  return 0;
}

G. Three Occurrences

给出一个数组a，定义一个区间是好的，当且仅当每个数恰好出现0次或者3次，询问好区间的个数$n\leq 5\times 10^5, 1\leq a_i \leq n$考虑固定左端点为i，那么$a_i$​出现0次和3次就是两个连续的区间，我们对$1-n$的每个数维护它的合法区间，如果是合法的就让这段区间的每个数都等于1，我们可以用一颗线段树来维护。从后往前枚举左端点，对于$a_i$​，我们先删除它之前的合法区间(两段区间-1)，然后再加上它当前的合法区间(两端区间+1)，只需要查询左端点-n中大小等于n的值的个数即可(显然最大值$\leq n$，所以维护最大值以及最大值个数即可)$O(n\log n)$这题还有一种更加普适的哈希做法，而且复杂度是$O(n)$的，先咕

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
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
const int N = 5e5 + 5;
int n, a[N];
vector<int> p[N];
struct seg
{
  int l, r, mx, cnt, tag;
  seg() {}
  seg(int _l, int _r) : l(_l), r(_r), mx(0), cnt(0), tag(0) {}
}t[N<<2];
void pull(int p)
{
  t[p].mx = max(t[p<<1].mx, t[p<<1|1].mx);
  t[p].cnt = 0;
  if(t[p].mx==t[p<<1].mx) t[p].cnt += t[p<<1].cnt;
  if(t[p].mx==t[p<<1|1].mx) t[p].cnt += t[p<<1|1].cnt;
}
void setv(int p, int v)
{
  t[p].mx += v;
  t[p].tag += v;
}
void push(int p)
{
  setv(p<<1, t[p].tag); setv(p<<1|1, t[p].tag);
  t[p].tag = 0;
}
void build(int p, int l, int r)
{
  t[p] = seg(l, r);
  if(l==r)
  {
    t[p].mx = n, t[p].cnt = 1;
    return;
  }
  int mid = (l+r)>>1;
  build(p<<1, l, mid); build(p<<1|1, mid+1, r);
  pull(p);
}
void upd(int p, int x, int y, int v)
{
  int l = t[p].l, r = t[p].r;
  if(l>=x && r<=y)
  {
    setv(p, v);
    return;
  }
  if(t[p].tag) push(p);
  int mid = (l+r)>>1;
  if(x<=mid) upd(p<<1, x, y, v);
  if(y>mid) upd(p<<1|1, x, y, v);
  pull(p);
}
void chk(pii &a, pii b)
{
  if(a.fi==b.fi) a.se += b.se;
  else if(a.fi<b.fi) a = b;
}
pii ask(int p, int x, int y)
{
  int l = t[p].l, r = t[p].r;
  if(l>=x && r<=y) return {t[p].mx, t[p].cnt};
  if(t[p].tag) push(p);
  int mid = (l+r)>>1; pii ans = {0, 0};
  if(x<=mid) chk(ans, ask(p<<1, x, y));
  if(y>mid) chk(ans, ask(p<<1|1, x, y));
  return ans;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for(int i=1; i<=n; i++) cin >> a[i];
  build(1, 1, n);
  int64_t ans = 0;
  for(int i=1; i<=n; i++) p[i].push_back(n+1);
  for(int i=n; i>=1; i--)
  {
    int sz = p[a[i]].size();
    if(sz>=4) upd(1, p[a[i]][sz-3], p[a[i]][sz-4]-1, -1);
    int suf = p[a[i]][sz-1];
    p[a[i]].push_back(i);
    ++sz;
    if(sz>=4) upd(1, p[a[i]][sz-3], p[a[i]][sz-4]-1, 1);
    upd(1, i, suf-1, -1);
    auto cur = ask(1, i, n);
    if(cur.fi==n) ans += cur.se;
  }
  cout << ans << '\n';
  return 0;
}