Codeforces Round 526

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
C (线段树+LCA+树的遍历->树上链状合并+MEX)

CF #526 Div1 C Max Mex

大意

给一个n个点的树,树上的点上带有值,这些值为0到n-1的排列

Q个询问:

询问1.(参数点的坐标) 交换两个点上的值

询问2.(无参数) 在树上找一条简单路径,使该简单路径上MEX最大,输出该最大值

(2<=n<=200'000)

(1<=q<=200'000)

MEX: 返回集合中最小未出现的自然数 如MEX({0,1,2,4,8,16}) = 3

解法

线段树维护值[v1 -> vn] 这一段是否可能 在一条简单路径上,如果可能,那么记录这条简单路径的端点坐标

保存和更新,利用线段树更新的log级别,和LCA 来进行树上线段的合并

关于合并 举例解释:

如果我们的线段树要合并[l1->r1][l2->r2] , 其中l2=r1+1

通过递归处理先得到

[l1->r1]这一段值,对应在树上的简单路径的端点坐标为vl1和vr1

[l2->r2]这一段值,对应在树上的简单路径的端点坐标为vl2和vr2

注意到 前序遍历 和 后续遍历的特征,如果 点A是B的祖先,那么前序遍历A<B, 且后序遍历A>B

那么有如果这4个端点,在从根到某个叶子的一条链上(当且仅当),则这四个端点的 前序遍历的偏序关系 正好 和后续遍历相反.

所以 我们可以通过对这4个点排序, 前序最小值对应的点 是否和 后续最大值对应的点 相同.如果相同,那么这4个点在一个链上返回[找到的最深点,最潜点] O(1)

以上是 存在从根下来的链经过4个端点.

下面考虑是否存在一个跨某节点连接 该节点两个子链的简单路径,经过4个端点

(假设dfs的子节点枚举从左向右,便于描述)

注意到,如果有祖先关系,那么前序的最大值为深度最深的点,如果是非祖先关系,那么 前序的最大值为最右侧的点,也就有了 前序最大是最右侧最深的点(假设叫RV)

对称的,后序遍历最小为最左侧最深的一个点.(假设叫LV)

那么 实际要考察的就是四个端点是否都在从LV到RV的这样一条简单路径上,

那么也就是LCA+判断点是否在链上,走一波O(log 树的深度)

如果失败,则用记录不可合并[any way -1也好 额外字段也好]

线段树更新,就日常更新就好了

查询,0是必定可以进链的

那么 尝试把0 和 (0-n/2) 左半合并(因为链合并有幂等性 不用考虑0和0自己冲突)

如果可以合并,就把合并后的和右半合并

如果不行,则 合并目标 = 合并目标的左半; O(log n)

相关知识

线段树(建立&更新&查询),老生常谈了[CF 入门必会],[相对于后缀数组,相对更难写,但能维护更多的状态]

合并树上的链(LCA,dfs 前序 后序遍历 特点,求一个点是否在一个树中的一条链上(类似LCA))

LCA, 求树上点的最近公共祖先:(基于fa[点i][幂次k] = 点i的2^k祖先),实现O(log(树高的))的时间复杂度

代码

code

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

using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i, a, n) for (int i=a;i<n;i++)
#define iif(c, t, f) ((c)?(t):(f))
#define per(i, a, n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int N = 200010;
int n;
struct vertex {
  int dep;
  int v;
  int _in;
  int _out;
} i2v[N];
int v2i[N];

const int Log = 22;
int fa[N][Log + 1]; // fa[0][any] = 0 的性质很好
vector<int> child[N];

pair<int, int> T[N << 2];

void dfs(int i, int dep, int &idx) {
  i2v[i].dep = dep;
  i2v[i]._in = idx++;
  for (auto item:child[i])
    dfs(item, dep + 1, idx);
  i2v[i]._out = idx++;
}

int Jump(int x, int d) {
  if (d < 0)
    return x;
  per(i, 0, Log + 1){
    if ((d >> i) & 1)
      x = fa[x][i];
  }
  return x;
}

int LCA(int l, int r) {
  int d = i2v[l].dep - i2v[r].dep;
  if (d < 0) {
    swap(l, r);
    d = -d;
  }
  l = Jump(l, d);
  if (l == r)
    return l;
  per(i, 0, Log + 1){
    if (fa[l][i] != fa[r][i]) {
      l = fa[l][i];
      r = fa[r][i];
    }
  }
  return fa[l][0];
}


bool onpath(int idx, int l_idx, int r_idx) {
  int anc = LCA(l_idx, r_idx);
  if (i2v[anc].dep > i2v[idx].dep)
    return false;
  return
    Jump(l_idx, i2v[l_idx].dep - i2v[idx].dep) == idx ||
    Jump(r_idx, i2v[r_idx].dep - i2v[idx].dep) == idx;
}

pair<int, int> mergeT(const pair<int, int> &v1, const pair<int, int> &v2) {
  int arr[] = {v1.fi, v1.se, v2.fi, v2.se};
  rep(i, 0, 4){
    if (arr[i] == -1)
      return {-1, -1};
  }
  int l_leaf = arr[0];
  rep(i, 0, 4) {
    if (i2v[arr[i]]._out < i2v[l_leaf]._out)
      l_leaf = arr[i];
  }

  int r_leaf = arr[0];
  rep(i, 0, 4) {
    if (i2v[arr[i]]._in > i2v[r_leaf]._in)
      r_leaf = arr[i];
  }

  if (l_leaf == r_leaf) { // 所有点在从根向下的一条链上
    int rt = arr[0];
    rep(i, 0, 4) {
      if (i2v[arr[i]].dep < i2v[rt].dep)
        rt = arr[i];
    }
    return {l_leaf, rt};
  } else { // 链跨过了某节点连接某节点的两个子链
    rep(i, 0, 4) {
      if (!onpath(arr[i], l_leaf, r_leaf))
        return {-1,-1};
    }
  }
  return {l_leaf, r_leaf};
}

pair<int, int> initSeg(int o, int l, int r) {
  if (l == r)
    return T[o] = {v2i[l], v2i[r]};
  int mid = (l + r) / 2;
  return T[o] = mergeT(
      initSeg(o << 1, l, mid),
      initSeg(o << 1 | 1, mid + 1, r));
}

void updateSeg(int o, int l, int r, const int &val) {
  if (l == r) {
    T[o] = {v2i[val], v2i[val]};
    return;
  }
  int mid = (l + r) / 2;
  if (val <= mid)
    updateSeg(o << 1, l, mid, val);
  else
    updateSeg(o << 1 | 1, mid + 1, r, val);
  T[o] = mergeT(T[o << 1], T[o << 1 | 1]);
}

int query(int o, int l, int r, const pair<int, int> &now) {
  if (l == r)
    return mergeT(now, T[o]).fi == -1 ? l : l + 1;
  int mid = (l + r) / 2;
  auto tmp = mergeT(now, T[o << 1]);
  if (tmp.fi == -1)
    return query(o << 1, l, mid, now);
  else
    return query(o << 1 | 1, mid + 1, r, tmp);
}

int main() {
  cin >> n;
  rep(i, 1, n + 1) {
    scanf("%d", &i2v[i].v);
    v2i[i2v[i].v] = i;
  }
  rep(i, 2, n + 1) {
    scanf("%d", &fa[i][0]);
    child[fa[i][0]].pb(i);
  }
  rep(j, 1, Log + 1) {
    rep(i, 1, n + 1) {
      fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
  }
  int idx = 1;
  dfs(1, 1, idx);

  initSeg(1, 0, n - 1);

  int Q;
  cin >> Q;
  while (Q--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int i, j;
      scanf("%d %d", &i, &j);
      swap(v2i[i2v[i].v], v2i[i2v[j].v]);
      swap(i2v[i].v, i2v[j].v);
      updateSeg(1, 0, n - 1, i2v[i].v);
      updateSeg(1, 0, n - 1, i2v[j].v);
    } else {
      pair<int, int> st = {v2i[0], v2i[0]};
      printf("%d\n", query(1, 0, n - 1, st));
    }
  }
  return 0;
}