250610 模拟赛 T2 题解

题意

给定一棵 \(n\) 个点，以 \(1\) 为根的有根树，第 \(i\) 个点的点权初始为 \(a_i\)。你需要进行 \(q\) 次修改，每次修改给定两个点 \(x,y\)，表示交换 \(a_x,a_y\)。你需要在每次操作之后回答一个问题：

记 \(S_u\) 表示 \(u\) 子树内所有点的点权组成的序列，从小到大排好序的结果。记所有 \(S_u\) 中字典序最小的一个为 \(L\)，问 \(\sum{[S_u=L]u}\)。

\(n,q\le 2\times 10^5,\ a_i\le 10^9\)

题解

首先注意，\(L\) 肯定是 \(S_1\) 的一个前缀。并且，当且仅当存在一个叶子节点的权值等于 \(1\) 时，\(L=[1]\)；其余情况 \(S_u=L\) 的 \(u\) 有且仅有一个。先特判掉叶子的情况。

考虑一个节点 \(u\) 成为答案的条件。容易发现，因为我们只有交换操作，所以 \(S_1\) 是不会改变的。又因为 \(L\) 必须是 \(S_1\) 的前缀，而且 \(L\) 的长度等于答案节点的子树大小，因此一个节点 \(u\) 成为答案当且仅当 \(S_u=S_1[1\sim sz_u]\)。记 \(T_u=S_1[1\sim sz_u]\)。

考虑 \(S_u\) 和 \(T_u\) 匹配的情形：

S[u]:   1 1 1 1  2 2 2  3 3 3 3  4 4 4
T[u]: [ 1 1 1 1  2 2 2  3 3 3 3  4 4 4 ] 4 4 4  5 5 5 5 ...

而不匹配的情形：

1-4 的数量太少
S[u]:   1 1 1 1  2 2    3 3      4              5 5 ...
T[u]: [ 1 1 1 1  2 2 2  3 3 3 3  4 4 4 ] 4 4 4  5 5 5 5 ...

4 太多
S[u]:   1 1 1 1  2 2 2  3 4 4 4  4 4 4
T[u]: [ 1 1 1 1  2 2 2  3 3 3 3  4 4 4 ] 4 4 4  5 5 5 5 ...

\(T_u\) 形如值域上一段前缀，再加上下一个数的一段。记 \(sc[i]\) 表示（离散化之后）\(S_1\) 中小于等于 \(i\) 的数字的数量，\(ac[u]\) 表示最大的满足 \(sc[i]<sz[u]\) 的颜色 \(i\)。例子中，\(ac[i]=3\)。

匹配时，子树内 \(\le ac\) 的数字数量等于 \(sc[ac]\)，并且 \(ac+1\) 的数量等于 \(sz[u]-sc[ac]\)。然而，两个维度的信息较难维护，尝试将它们合并成一维。注意到 \(cnt(ac+1)\) 比 \(sz[u]-sc[ac]\) 可大可小，却不会超过 \(sz[u]-cnt(\le ac)\)。即：

\[ \begin{cases} cnt(\le ac)\le sc[ac]\\ cnt(ac+1)\le sz[u]-cnt(\le ac) \end{cases} \]

并且在匹配时，两个不等号同时取等。这启发我们维护

\[ sc[ac]+sz[u]-2cnt(\le ac)-cnt(ac+1) \]

因为它始终大于等于 \(0\)，并且在匹配时取等。

同时我们注意到，在一条根链上随着深度的减小，\(sz\) 单调递增，因此对应的 \(ac\) 也单调递增。对于节点 \(i\) 处的数字 \(a_i\)，它会在根链的两个连续区间上分别产生 \(-1,-2\) 的贡献，区间的位置可以使用倍增求得。然后用树剖维护上面的式子，每次修改时进行区间加减，然后查询最小值 \(0\) 出现的位置即可。

不等式可加性

将题目需要的取等关系放在恒成立的不等式中，然后将不等式左右两边分别相加再作差，可以将多个式子压为一个式子。

#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
const int N = 2e5 + 10;
const int LOGN = 19;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, q;
int a[N];

int num[N], scnt[N], nn;
void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

int dfn[N], id[N], dt;
int sz[N], fa[N], son[N], top[N];
int c[N], ac[N] = {INF}; // sz+a0; 最后一个 scnt< sz 的颜色

bool isleaf[N];
int sl;

int anc[LOGN][N];

namespace SegT {
    struct myPair {
        int val, pos;
        inline myPair() { val = pos = 0; }
        inline myPair(int _1, int _2) : val(_1), pos(_2) {}
        inline myPair &operator+=(int x) {
            val += x;
            return *this;
        }
        inline bool operator<(const myPair &b) const {
            if(val != b.val) return val < b.val;
            return sz[pos] < sz[b.pos];
        }
    };
    myPair mn[4 * N];
    int tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        mn[p] = min(mn[lc(p)], mn[rc(p)]);
    }
    inline void move_tag(int p, int tg) {
        tag[p] += tg;
        mn[p] += tg;
    }
    inline void push_down(int p) {
        if(!tag[p]) return;
        move_tag(lc(p), tag[p]);
        move_tag(rc(p), tag[p]);
        tag[p] = 0;
    }
    void build(int p, int l, int r) {
        if(l == r) {
            mn[p] = {c[id[l]], id[l]};
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            move_tag(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    inline int query() {
        assert(mn[1].val == 0);
        return mn[1].pos;
    }
}

void dfs1(int u) {
    sz[u] = 1;
    anc[0][u] = fa[u];
    for(int k = 1; k < LOGN; k++) {
        anc[k][u] = anc[k - 1][ anc[k - 1][u] ];
    }
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa[u]) continue;
        fa[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
    ac[u] = lower_bound(scnt + 1, scnt + 1 + nn, sz[u]) - scnt - 1;
    c[u] = scnt[ac[u]] + sz[u];
    if(!pool[head[u]].next) isleaf[u] = 1;
}

void dfs2(int u, int tp) {
    dfn[u] = ++dt;
    id[dt] = u;
    top[u] = tp;
    if(son[u]) dfs2(son[u], tp);
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

inline void add_path(int p, int v) {
    while(p) {
        SegT::add(1, 1, n, dfn[top[p]], dfn[p], v);
        p = fa[top[p]];
    }
}

inline void insert(int p, int v, int w = 1) {
    int bg = p;
    if(isleaf[p] && v == 1) sl += w * p;
    for(int k = LOGN - 1; k >= 0; k--) {
        if(ac[anc[k][p]] + 1 < v) p = anc[k][p];
    }
    if(ac[p] + 1 < v) p = fa[p];
    if(!p) return;
    add_path(p, -w);
    for(int k = LOGN - 1; k >= 0; k--) {
        if(ac[anc[k][p]] < v) p = anc[k][p];
    }
    if(ac[p] < v) p = fa[p];
    if(!p) return;
    add_path(p, -w);
}

inline void modify(int x, int y) {
    insert(x, a[x], -1);
    insert(y, a[y], -1);
    swap(a[x], a[y]);
    insert(x, a[x], 1);
    insert(y, a[y], 1);
}

inline int query() { return SegT::query(); }

int main() {

    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    lisanhua();

    for(int i = 1; i <= n; i++) ++scnt[a[i]];
    for(int i = 1; i <= nn; i++) scnt[i] += scnt[i - 1];

    dfs1(1);
    dfs2(1, 1);

    SegT::build(1, 1, n);
    for(int i = 1; i <= n; i++) insert(i, a[i]);

    while(q--) {
        int x, y;
        cin >> x >> y;
        modify(x, y);
        if(sl) cout << sl << '\n';
        else cout << query() << '\n';
    }

    return 0;
}