BZOJ 3545 & 3551 「ONTAK2010」Peaks

蒟蒻初学 Kruskal 重构树……

假设没有边权不超过 k 的限制，这题就变成了永无乡。
但是这里有这么个限制。

考虑离线。
发现在没有这个限制的情况下，找出最小生成树再做对答案没有影响。
于是考虑把询问按照 k 排序，把边按权值排序后依次尝试插入最小生成树，然后按照永无乡的方法计算答案。

考虑在线。
发现上面的做法就是 K 法的过程。由此我们可以联想到 Kruskal 重构树。
（至于怎么联想到的，参考六学）
其实只要理解了 Kruskal 重构树的性质就很好想了。

代码：

#include <cstdio>
#include <algorithm>
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
using namespace std;
const int N = 1e5;
const int M = 5e5;
const int LG = 20;
int n,m,q,tot;
int lastans;
int a[(N << 1) + 10],ind[(N << 1) + 10],len;
int id[(N << 1) + 10],val[(N << 1) + 10];
int to[(N << 2) + 10],pre[(N << 2) + 10],first[(N << 1) + 10];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v;
    pre[tot] = first[u];
    first[u] = tot;
}
struct edge
{
    int u,v,w;
    inline bool operator<(const edge &o) const
    {
        return w < o.w;
    }
} e[M + 10];
int fa[(N << 1) + 10];
inline int get(int x)
{
    return !fa[x] ? x : fa[x] = get(fa[x]);
}
struct segnode
{
    int cnt;
    int lson,rson;
} seg[(N << 6) + 10];
int rt[(N << 1) + 10],seg_tot;
int f[(N << 1) + 10][LG + 5],sz[(N << 1) + 10];
void change(int x,int k,int &p,int tl,int tr)
{
    seg[++seg_tot] = seg[p];
    p = seg_tot;
    if(tl == tr)
    {
        seg[p].cnt += k;
        return ;
    }
    int mid = tl + tr >> 1;
    if(x <= mid)
        change(x,k,ls(p),tl,mid);
    else
        change(x,k,rs(p),mid + 1,tr);
    seg[p].cnt = seg[ls(p)].cnt + seg[rs(p)].cnt;
}
int query(int k,int p,int q,int tl,int tr)
{
    if(tl == tr)
        return tl;
    int mid = tl + tr >> 1;
    int cnt = seg[ls(q)].cnt - seg[ls(p)].cnt;
    if(k <= cnt)
        return query(k,ls(p),ls(q),tl,mid);
    else
        return query(k - cnt,rs(p),rs(q),mid + 1,tr);
}
void dfs(int p)
{
    static int tot = 0;
    sz[p] = 1;
    id[p] = ++tot;
    if(p <= n)
        val[tot] = a[p];
    for(register int i = 1;i <= LG;++i)
        f[p][i] = f[f[p][i - 1]][i - 1];
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ f[p][0])
        {
            f[to[i]][0] = p;
            dfs(to[i]);
            sz[p] += sz[to[i]];
        }
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    tot = n;
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    for(register int i = 1;i <= m;++i)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e + 1,e + m + 1);
    for(register int i = 1;i <= m;++i)
    {
        int x = e[i].u,y = e[i].v,w = e[i].w;
        int fx = get(x),fy = get(y);
        if(fx ^ fy)
        {
            fa[fx] = fa[fy] = ++tot;
            add(tot,fx),add(tot,fy);
            a[tot] = w;
        }
    }
    for(register int i = 1;i <= tot;++i)
        ind[i] = a[i];
    sort(ind + 1,ind + tot + 1);
    len = unique(ind + 1,ind + tot + 1) - ind - 1;
    for(register int i = 1;i <= tot;++i)
        a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
    for(register int i = tot;i;--i)
        if(!id[i])
            dfs(i);
    for(register int i = 1;i <= tot;++i)
    {
        rt[i] = rt[i - 1];
        if(val[i])
            change(val[i],1,rt[i],1,len);
    }
    int v,x,k;
    while(q--)
    {
        scanf("%d%d%d",&v,&x,&k);
        v ^= lastans,x ^= lastans,k ^= lastans;
        lastans = 0;
        int p = v;
        for(register int i = LG;i >= 0;--i)
            if(f[p][i] && ind[a[f[p][i]]] <= x)
                p = f[p][i];
        int cnt = seg[rt[id[p] + sz[p] - 1]].cnt - seg[rt[id[p] - 1]].cnt;
        if(cnt < k)
            puts("-1");
        else
            printf("%d\n",lastans = ind[query(cnt - k + 1,rt[id[p] - 1],rt[id[p] + sz[p] - 1],1,len)]);
    }
}