Codeforces1083CMaxMex

Description

一棵\(N\)个节点的树， 每个节点上都有 互不相同的 \([0, ~N-1]\) 的数。

定义一条路径上的数的集合为 \(S\), 求一条路径使得 \(Mex(S)\) 最大。

带修改， \(M\) 次查询

Solution

用一棵权值线段树维护。

节点 \([L,R]\)存储信息：是否有一条路径包含 \([L,R]\) 内的所有数 以及 路径两个端点。

合并两个区间： 在\(4\)个点中 枚举新路径的端点， 然后判断另外两个点是否在路径上即可。

正解能 \(O(1)\) 合并， 然而这个解法需要\(O(logN)\)

所以总复杂度为 \(O(Nlog^2N)\)

Code

#include
#include
#include
#include
#include
#define up(a, b) (a = a > b ? a : b)
#define down(a, b) (a = a > b ? b : a)
#define cmax(a, b) (a > b ? a : b)
#define cmin(a, b) (a > b ? b : a)
#define Abs(a) ((a) > 0 ? (a) : -(a))
#define rd read()
#define db double
#define LL long long
using namespace std;
typedef pair P;
inline char nc(){
static char buf[1<<14],*p1=buf,*p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
return x*f;
}
const int N = 2e5 + 5;
int n, m, a[N], b[N], f[N][20], dep[N];
int timer, tin[N], tout[N];
vector to[N];
void dfs(int u) {
tin[u] = ++timer; // dfs序
for (int i = 0, up = to[u].size(); i int nt = to[u][i];
if (nt == f[u][0])
continue;
dep[nt] = dep[u] + 1;
dfs(nt);
}
tout[u] = timer;
}
inline bool isanc(int u, int v) { // 判断u是否是v的祖先
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int getlca(int u, int v) {
if (isanc(u, v))
return u;
for (int i = 19; ~i; --i)
if (f[u][i] && (!isanc(f[u][i], v)))
u = f[u][i];
return f[u][0];
}
inline bool isondownpath(int u, P v) { //判断u是否是 竖直路径v() 上的点
return isanc(v.first, u) && isanc(u, v.second);
}
inline bool isonpath(int u, P v) { //判断u是否是 路径v()上的点
int lca = getlca(v.first, v.second);
return isondownpath(u, P(lca, v.second)) || isondownpath(u, P(lca, v.first));
}
P merge(P u, P v) { //合并两条路径
if (u.first == -1 || v.first == -1)
return P(-1, -1);
int g[4] = {u.first, u.second, v.first, v.second};
for (int i = 0; i <4; ++i) {
for (int j = i + 1; j <4; ++j) {
bool flag = true;
for (int k = 0; k <4; ++k) {
if (k != i && k != j && !isonpath(g[k], P(g[i], g[j])))
flag = false;
}
if (flag)
return P(g[i], g[j]);
}
}
return P(-1, -1);
}
namespace SegT {
#define mid ((l + r) >> 1)
#define lson u <<1
#define rson u <<1 | 1
P t[N <<2];
void build(int l, int r, int u) {
if (l == r) {
t[u].first = t[u].secOnd= b[l];
return;
}
build(l, mid, lson); build(mid + 1, r, rson);
t[u] = merge(t[lson], t[rson]);
}
void update(int c, int l, int r, int u) {
if (l == r) {
t[u].first = t[u].secOnd= b[l];
return;
}
if (c <= mid)
update(c, l, mid, lson);
else update(c, mid + 1, r, rson);
t[u] = merge(t[lson], t[rson]);
}
int query(int l, int r, int u, P tmp) {
if (l == r) {
if (tmp.first == -1)
return t[u].first != -1;
P g = merge(tmp, t[u]);
return g.first != -1;
}
P g = tmp.first == -1 ? t[lson] : merge(tmp, t[lson]);
if (g.first == -1)
return query(l, mid, lson, tmp);
else return mid - l + 1 + query(mid + 1, r, rson, g);
}
}using namespace SegT;
int main()
{
n = rd;
for (int i = 1; i <= n; ++i)
a[i] = rd + 1, b[a[i]] = i;
for (int i = 2; i <= n; ++i) {
int u = rd;
f[i][0] = u;
to[u].push_back(i);
to[i].push_back(u);
}
dep[1] = 1; dfs(1);
for (int i = 1; i <20; ++i)
for (int j = 1; j <= n; ++j)
f[j][i] = f[f[j][i - 1]][i - 1];
;
build(1, n, 1);
m = rd;
for (; m; --m) {
int typ = rd;
if (typ == 1) {
int u = rd, v = rd;
swap(a[u], a[v]);
swap(b[a[u]], b[a[v]]);
update(a[u], 1, n, 1);
update(a[v], 1, n, 1);
}
else printf("%d\n", query(1, n, 1, P(-1, -1)));
}
}