Atcoder abc248

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
G(欧拉函数,DP,树上DP)Ex(线段树,单调队列,连续段计数)

https://atcoder.jp/contests/abc248/tasks

G - GCD cost on the tree

n点无向树

点i上有值ai

C(u,v) = 简单路径u..v上 点个数 乘 点上ai的gcd

求所有点对的 C的和,mod 998244353

范围

n 1e5

ai [1,1e5]

8s

2048mb

我的思路

显然暴力算 至少要 n^2

注意到的是 Ai很小, 如果能变成 不同gcd结果的贡献值的和 就好了

有点想做容斥, 但容斥的代价函数并不能用当前gcd

如果选定一个点必定经过, 那么可能的gcd都是它的因数, 虽然这里log了,但是要找路径还是n, 这样依然是n^2 以上

再看贡献count(u..v) * gcd(a[u]...a[v])

可以转化成, u 会贡献了覆盖了u的线段次数, 每次都是u的因子

那么每个 v1…u…v2 在u上的贡献是 gcd(gcd(v1..u),gcd(v2..u)), 且v1,v2 不在u的同一个分叉上

f[child v0] = sum c0[g] x^g

f[child v1] = sum c1[g] x^g

sf[v1,v2] = f[v1] + f[v2]

ans += sf[0..i-1] * f[vi] (k[gcd(g0,g1)] += k0[g0] * k1[g1]`

= ((E+f[0]+f[1]+…+f[i]) ^ 2 - E^2 - f[0]^2 -f[1]^2 -…-f[i]^2)/2

换根dp ???

题解

欧拉函数

$\phi(n) = $ 小于等于n与n互质的数的个数

$n = \sum_{d|n} count(gcd(x,n) == d)$ ( 就是1到n之间 按照gcd的结果为d的个数统计

$n = \sum_{d|n} count(gcd(\frac{x}{d},\frac{n}{d}) == 1)$

$n = \sum_{d|n} \phi(\frac{n}{d})$

$n = \sum_{d|n} \phi({d})$ 也就是n的所有因数的phi的和

原文问题

$ans = \sum_{u\neq v, u < v} dis(u,v) gcd(path(u,v))$

$= \sum_{u\neq v, u < v} dis(u,v) \sum_{d | gcd(path(u,v))} \phi(d)$

考虑对$\phi(d)$ 做次数统计,

$= \sum_{d} \phi(d) \sum_{u\neq v, u < v, d|gcd(path(u,v))} dis(u,v)$

也就是, 路径上都是d的倍数的路径长度和

于是按照d对原图进行拆分成多个联通块, 注意到这样拆分不要d去找点,而是点直接得到d, 这样才能保证复杂度

这样一个联通块中做所有路径长度和的统计

同样和我上面的一样, 既然是路径长度统计, 相当于, 每一条路径, 上面每个点贡献+1

所以等于 每个点 被覆盖的边的条数, 就是树上DP了

代码

https://atcoder.jp/contests/abc248/submissions/35150044

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

const int N = 1e5;

int a[N+10];
vector<int> G[N+10]; // G[u] = {v}
vector<int> ys2i[N+10]; // ys2i[因数] = {点id}
bool vis[N+10];
int siz[N+10]; // 当前子树大小

int dfs1(int u,int fa,int d) { // return 子树大小
  vis[u] = true;
  siz[u] = 1;
  for(auto v:G[u]) if(v!=fa && a[v]%d==0) siz[u] += dfs1(v,u,d);
  return siz[u];
}

mint dfs2(int u, int fa, int sz/*联通块总大小*/, int d){
  vis[u] = false;
  mint r = 0;
  mint pre = sz - siz[u] + 1; // 父方向 节点数 包括u; 树上换根 + 前缀和dp
  r += pre;
  for(auto v : G[u]) if(v!=fa && a[v]%d==0){
    r += pre * siz[v]; // 当前v级子树的点和 前面点覆盖了u的路径数
    pre += siz[v];
    r += dfs2(v, u, sz, d);
  }
  return r;
}

int phi[N+10]; // phi(i)
int main() {
  { // calc phi
    iota(phi,phi+N+1,0);
    vector<bool> p(N+1,0); // prime vis
    rep(i,2,N+1) if(!p[i]) for(int j=i;j<=N;j+=i){ // j = ki
      p[j] = true;
      (phi[j] /= i) *= (i-1);
    }
  }
  int n = read();
  {
    vector<vector<int>>ys(N+1); // ys[i] = {i的因数}
    rep(i,1,N+1) for(int j=i;j<=N;j+=i) ys[j].push_back(i); // 计算因子
    rep(i,0,n) {
      a[i] = read(); // 0-index
      for(auto x:ys[a[i]]) ys2i[x].push_back(i);
    }
    rep(i,1,n){
      int u = read()-1;
      int v = read()-1;
      G[u].push_back(v);
      G[v].push_back(u);
    }
  }
  mint ans = 0;
  rep(d,1,N+1){ // \phi(d) * 路径上全是d的倍数的路径长度和 = \phi(d) * sum(每个点被边覆盖的次数)
    mint r = 0;
    for(auto u:ys2i[d]) if(!vis[u]) dfs1(u,u,d);
    for(auto u:ys2i[d]) if(vis[u]) r += dfs2(u,u,siz[u],d); 
    ans += phi[d] * r;
  }
  rep(i,0,n) ans -= a[i]; // 去掉单点
  printf("%d\n", ans.val());
  return 0;
}

Ex - Beautiful Subsequences

给 1-N的排列p 和 k

问有多少区间[l..r]

max(p[l..r])-min(p[l..r]) <= r-l+k

范围

n 1.4e5

k [0..3]

6s

1024mb

我的思路

k很小

k=0 时的意义就是 [l..r]对应的值也是连续的一段

就是连续段计数问题

这个用 单调栈 + 线段树

到r时, 点l表示 l..r的情况

= max(a[l]..a[r]) - min(a[l]..a[r]) + l - r

所以初始化, 所有 点=l

每次r移动, 等价于全部-1

max 用单调递减栈维护, 对多个连续区间的max 做增量运算, (不要修改, 因为修改没法维护最小值

min 用单调递增栈维护, 对多个连续区间的min 做增量运算

每次贡献 = 最小值出现的次数(最小值一定为零,因为长度1的时候=0, 且不会小于0

每个线段树节点状态就是 (对应区间最小值,和最小值的个数, lazy未下降的增量)

那么这个题,似乎也可以这样搞, 把维护的最小值和最小值的个数,变成最小的值,和它与 +0,+1+2+3 的个数就行了?

代码

https://atcoder.jp/contests/abc248/submissions/35152743

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

#define SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r

ll read(){ll r;scanf("%lld",&r);return r;}
const int N = 140000;
const int K = 4;
int a[N+10];
struct node{ // 维护 max[l..r] - min[l..r] + l - r
  int min; // 最小值
  int lazy; // lazy tag未向下传递的add
  array<int,K> cnt = {0,0,0,0}; // 最小值+0,+1,+2,+3出现的次数
}t[N*4+10];

// merge {min,count array}
pair<int,array<int,K>> merge(const pair<int,array<int,K> >&mc0,const pair<int,array<int,K>>&mc1){
  auto [m0,c0] = mc0;
  auto [m1,c1] = mc1;
  int m = min(m0,m1);
  array<int,K> c = {0,0,0,0};
  rep(i,0,K) if(m0+i<m+K) c[m0+i-m] += c0[i];
  rep(i,0,K) if(m1+i<m+K) c[m1+i-m] += c1[i];
  return {m,c};
}

void range_add(int o,int v){
  t[o].min+=v;
  t[o].lazy+=v;
}

void down(int o){
  if (!t[o].lazy) return;
  range_add(SEG_L,t[o].lazy);
  range_add(SEG_R,t[o].lazy);
  t[o].lazy=0;
}

void build(int o,int l,int r){
  if (l==r) {
    t[o].min = l;
    t[o].cnt[0] = 1;
    return;
  }
  build(SEG_L_CHILD);
  build(SEG_R_CHILD);
  tie(t[o].min,t[o].cnt) = merge({t[SEG_L].min,t[SEG_L].cnt},{t[SEG_R].min,t[SEG_R].cnt});
}

void add(int o, int l,int r,int ql,int qr,int v){
  if (ql <= l && r <= qr) return range_add(o,v);
  down(o);
  if (ql<=mid) add(SEG_L_CHILD,ql,qr,v);
  if (qr> mid) add(SEG_R_CHILD,ql,qr,v);
  tie(t[o].min,t[o].cnt) = merge({t[SEG_L].min,t[SEG_L].cnt},{t[SEG_R].min,t[SEG_R].cnt});
}

pair<int,array<int,K>> query(int o,int l,int r,int ql,int qr){ // {min, count array}
  if (ql <= l && r <= qr) return {t[o].min,t[o].cnt};
  down(o);
  auto ret = pair(0,array<int,K>{0,0,0,0}); // {min, count array}
  if (ql<=mid) ret = merge(ret,query(SEG_L_CHILD,ql,qr));
  if (qr> mid) ret = merge(ret,query(SEG_R_CHILD,ql,qr));
  return ret;
}

int main(){
  int n = read();
  int k = read();
  rep(i,0,n) a[i] = read();

  build(SEG_ROOT);
  ll ans = 0;
  vector<int> mx; // 区间最大值 下标, 单调递减栈 维护
  vector<int> mn; // 区间最小值 下标, 单调递增栈 维护
  rep(i,0,n){
    for(;mx.size()&&a[mx.back()]<a[i];mx.pop_back())add(SEG_ROOT,mx.size()>1?mx[mx.size()-2]+1:0,mx.back(),a[i]-a[mx.back()]); // [a[mx.size()-2]+1...a[mx.back()]] 全部增量
    mx.push_back(i);
    for(;mn.size()&&a[mn.back()]>a[i];mn.pop_back())add(SEG_ROOT,mn.size()-1?mn[mn.size()-2]+1:0,mn.back(),a[mn.back()]-a[i]);
    mn.push_back(i);
    auto [_,c] = query(SEG_ROOT,0,i);
    rep(j,0,k+1) ans += c[j];
    add(SEG_ROOT,0,n-1,-1); // r增加, 全部-1
  }
  printf("%lld\n",ans);
  return 0;
}

总结

G

欧拉函数, 不会啊

$n = \sum_{d|n} \phi(d)$

Ex

惊了,我竟然能ac红题, 虽然我觉得G,我不会phi,更难, 这个就是个连续段计数的变形

参考

官方题解

51 nod 1810 连续区间

Codeforces 526F

Codeforces 997E