bzoj 4129: Haruna’s Breakfast (树上莫队 + 修改)

https://www.lydsy.com/JudgeOnline/problem.php?id=4129

Description

 Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵

树上，每个结点都有一样食材，Shimakaze要考验一下她。

每个食材都有一个美味度，Shimakaze会进行两种操作：

1、修改某个结点的食材的美味度。

2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。

请你帮帮Haruna吧。

Input

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。

第二行包括n个整数a1...an，代表每个结点的食材初始的美味度。

接下来n-1行，每行包括两个整数u，v，代表树上的一条边。

接下来m 行，每行包括三个整数

0 u x 代表将结点u的食材的美味度修改为 x。

1 u v 代表询问以u，v 为端点的链的mex值。

思路:

这个题是 莫队 + 分块.
分块里维护的是 莫队区间的答案.
树上莫队,首先要分块,用 dfs + stack 把节点分块.
然后我们莫队维护的区间.就是 l 到 r 的路径,但是这个路径不包括 lca(l,r).
最后计算的时候,我们要 加上 lca(l,r),

我们来考虑一下带修改莫队的流程.
我们有 ans 来记录莫队维护区间的答案.
知道 莫队维护 的区间是什么.
Query 记录 要询问的区间,修改了多少次, 和 id,
Change 记录 修改的位置,当前的值,之前的值.

当我们要计算询问的答案的时候,
1.首先要回溯时间,修改到正确的时间,然后修改单个节点,要判断这个单个节点是不是在莫队维护的区间内,如果是,那么我们就需要更新答案,因为这会对答案造成能影响.
2.我们再移动l r,到正确的位置,这个移动,一定会影响答案.我们要修改答案.
 

 

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
vector<int>e[N];
int blo[N], block, B, n, m, cntq, cntc, s[N], now[N], l, r, t;
int fa[N][20], dep[N], st[N], top, ans[N];
int L[N], R[N], dfn;
bool vis[N];
struct Query {
    int l, r, tim, id;
    bool operator < (Query A) const {
        if (blo[A.l] != blo[l]) return l < A.l;
        if (blo[A.r] != blo[r]) return r < A.r;
        return tim < A.tim;
    }
} q[N];
struct Change {
    int pos, New, Old;
} c[N];
void init() {
    int x, y, op;
    scanf("%d%d", &n, &m);
    block = pow(n, 0.45);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
        s[i]++;
        now[i] = s[i];
    }
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &op, &x, &y);
        if (op) {
            q[++cntq] = (Query) {
                x, y, cntc, cntq
            };
        } else {
            c[++cntc] = (Change) {x, ++y, now[x]}, now[x] = y;
        }
    }
}
void dfs(int u, int fu) {
    dep[u] = dep[fu] + 1;
    fa[u][0] = fu;
    for (int i = 1; i < 20; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    int len = e[u].size();
    int bottom = top;
    for (int i = 0; i < len; ++i) {
        int v = e[u][i];
        if (v == fu) continue;
        dfs(v, u);
        if (top - bottom >= block) {
            B++;
            while(top != bottom) blo[st[top--]] = B;
        }
    }
    st[++top] = u;
}
int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 19; i >= 0; --i)
        if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; --i)
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
struct Dateblock {  //这个是另外一个分块,我们用分块来计算答案. 分块维护的是莫队计算的区间.
    int n, blo[N], block, sum[500], num, vis[N], l[500], r[510];
    void init() {
        block = sqrt(n);
        num = (n - 1) / block + 1;
        for (int i = 1; i <= n; ++i)
            blo[i] = (i - 1) / block + 1;
        for (int i = 1; i <= num; ++i)
            l[i] = (i - 1) * block + 1, r[i] = i * block;
        r[num] = n;
    }
    void add(int v) {
        if(v <= n) sum[blo[v]] += ((++vis[v]) == 1);
    }
    void del(int v) {
        if (v <= n) sum[blo[v]] -= ((--vis[v]) == 0);
    }
    int mex() {
        for (int i = 1; i <= num; ++i)
            if (r[i] - l[i] + 1 != sum[i])
                for (int j = l[i]; j <= r[i]; ++j)
                    if (vis[j] == 0) return j;
        return -1;
    }
} data;

void going(int u, int d) { // 回溯时间的过程中,我们要判断修改的点是不是在当前区间里.不在区间就不会影响答案.
    if (vis[u]) data.del(s[u]), data.add(d);
    s[u] = d;
}
void act(int u) {  // 修改区间答案.
    if (vis[u]) data.del(s[u]), vis[u] = 0;
    else data.add(s[u]), vis[u] = 1;
}
void move(int x, int y) {  //修改路径
    if (dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) act(x), x = fa[x][0];
    while(x != y) act(x), act(y), x = fa[x][0], y = fa[y][0];
}
void Mo() {
    l = 1, r = 1, t = 0;
    for (int i = 1; i <= cntq; ++i) {
        while(t < q[i].tim) going(c[t + 1].pos, c[t + 1].New), t++; //回溯时间,确定修改的位置.
        while(t > q[i].tim) going(c[t].pos, c[t].Old), t--;

        if (l != q[i].l) move(l, q[i].l), l = q[i].l; // 修改 l 到 q.l 的路径
        if (r != q[i].r) move(r, q[i].r), r = q[i].r; // 修改 r 到 q.r 的路径.
        int tmp = LCA(l, r);//我们莫队维护的区间是去掉 lca 的值,
        act(tmp);  //这个时候我们加上 lca 的值,
        ans[q[i].id] = data.mex() - 1;
        act(tmp); // 然后我们把 lca 的值去掉.
    }
}
int main() {
    init(); dfs(1, 0);   B++;
    while(top) blo[st[top--]] = B;
    sort(q + 1, q + cntq + 1);
    data.n = n + 1;
    data.init();
    Mo();
    for (int i = 1; i <= cntq; ++i)
        printf("%d\n", ans[i]);
    return 0;
}