题解：P5311 [Ynoi2011] 成都七中

前言

将 MX 集训中每天做的困难极其困难的题目做个总结，写一下题解。

Solution

同时考虑的限制和连通块的限制还是太困难了，考虑分开想。

对于连通块的限制，我们考虑将连通块放在点分树上，发现考虑与连通的最浅的点和考虑是相同的（毕竟都连通了）。

然后考虑如何判断连通，发现就是路径上点编号的最小值不小于，最大值不大于。

~~我们不会点分树，~~直接点分治即可。

考虑把询问挂在上，这样考虑子树中连通点时，也能发现可以处理的询问，当然也可以在把询问放在点分治中弄，每次将询问放到包含的子树中处理，但是前者比较好写所以选择前者的写法。

如何计算答案？

我们现在拿出了一些询问，不用管，它的限制已经被挪到上了，只要考虑的限制即可。

把所有子树内点拿出来后，显然每个点有一个区间表示到的路径上点编号的最小值和最大值。

将所有按排序后，考虑的限制，可以双指针维护的限制，然后维护当前每个颜色最右的点（这样最容易满足的限制），树状数组维护区间内有多少个颜色最右的点在内即可计算答案。

复杂度分析

点分治套排序加树状数组，复杂度为。

注意到，每个询问被拉出来查了次（这话怪怪的），但是累计产生的排序开销和树状数组开销都是，不影响复杂度，只是可能导致常数较大，但是的数据范围下怎么都是过得去的。

Code

#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = 1e5 + 5;
int n, m;
int a[N], ans[N];
vector<int> grh[N];
struct Query
{
    int l, r, id;
};
vector<Query> qrys[N];
bool vis[N];
namespace GetCentroid
{
    int sz[N], root, centroid;
    void getsz(int u, int fa)
    {
        sz[u] = 1;
        for (int v : grh[u])
        {
            if (v == fa || vis[v])
                continue;
            getsz(v, u);
            sz[u] += sz[v];
        }
    }
    void find(int u, int fa)
    {
        if (sz[u] * 2 >= sz[root])
            centroid = u;
        else
            return;
        for (int v : grh[u])
        {
            if (v == fa || vis[v])
                continue;
            find(v, u);
        }
    }
    int getcentroid(int u)
    {
        root = u;
        centroid = 0;
        getsz(u, 0);
        find(u, 0);
        return centroid;
    }
}
using GetCentroid::getcentroid;
class BIT
{
private:
    int tree[100005];
    int sz;

public:
    void init(int n)
    {
        nmf(i, 1, n) tree[i] = 0;
        sz = n;
    }
    void upd(int x, int val)
    {
        while (x <= sz)
        {
            tree[x] += val;
            x += (x & -x);
        }
    }
    int query(int x)
    {
        if (x > sz)
            x = sz;
        int ret = 0;
        while (x > 0)
        {
            ret += tree[x];
            x -= (x & -x);
        }
        return ret;
    }
    int query(int l, int r)
    {
        return query(r) - query(l - 1);
    }
} tr;
vector<Query> vecqrys;
vector<tuple<int, int, int>> vec;
int pos[N];
void dfs(int u, int fa, int l, int r)
{
    vec.emplace_back(l, r, a[u]);
    for (auto it : qrys[u])
        if (it.l <= l && r <= it.r)
            vecqrys.push_back(it);
    for (int v : grh[u])
    {
        if (v == fa || vis[v])
            continue;
        dfs(v, u, min(l, v), max(r, v));
    }
}
void sol(int u)
{
    vecqrys.clear();
    vec.clear();
    dfs(u, 0, u, u);
    sort(vecqrys.begin(), vecqrys.end(), [](const Query &x, const Query &y)
         { return x.r < y.r; });
    sort(vec.begin(), vec.end(), [](const tuple<int, int, int> &x, const tuple<int, int, int> &y)
         { return get<1>(x) < get<1>(y); });
    int j = 0;
    nmf(i, 0, (int)vecqrys.size() - 1)
    {
        while (j < (int)vec.size() && get<1>(vec[j]) <= vecqrys[i].r) // r <= vecqrys[i].r
        {
            auto [l, r, col] = vec[j];
            if (pos[col])
                tr.upd(pos[col], -1);
            pos[col] = max(pos[col], l);
            tr.upd(pos[col], 1);
            j++;
        }
        ans[vecqrys[i].id] = max(ans[vecqrys[i].id], tr.query(vecqrys[i].l, 1e5)); // pos[col](max l) >= vecqrys[i].l
    }
    for (auto [_, __, col] : vec)
    {
        if (pos[col])
        {
            tr.upd(pos[col], -1);
            pos[col] = 0;
        }
    }
}
void solve(int u)
{
    int rt = getcentroid(u);
    vis[rt] = 1;
    sol(rt);
    for (auto v : grh[rt])
    {
        if (!vis[v])
            solve(v);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    nmf(i, 1, n) cin >> a[i];
    nmf(i, 2, n)
    {
        int u, v;
        cin >> u >> v;
        grh[u].emplace_back(v);
        grh[v].emplace_back(u);
    }
    nmf(i, 1, m)
    {
        int l, r, x;
        cin >> l >> r >> x;
        qrys[x].push_back({l, r, i});
    }
    tr.init(1e5);
    solve(1);
    nmf(i, 1, m) cout << ans[i] << '\n';
    return 0;
}