BZOJ 3545/3551: [ONTAK2010]Peaks – [重构树/主席树]


题目传送门(BZOJ/非强制在线)
题目传送门(BZOJ/强制在线)
>原文链接<

题解 :

重构树模板题

Kruskal重构树 :

  • 将Kruskal得到的最小生成树进行重构 :

    对于一条边(u, v)\;val=w, 建立一个代表边的点x, 其权值为w, 并把u, v在当前重构树中的根节点分别连到该点x上, 作为其两个儿子.

    利用并查集维护根节点, 点u的根就是当前的find(u), 在连边的同时, 把u, v的根节点同时并到该点上.

    枚举边的顺序按Kruskal的顺序来

    对于样例来说, 重构树是这样的 :

pic

其中非叶子节点都是由边重构而成的节点

  • 重构树有如下几个性质 :
    1. 二叉树, 大根堆
    2. 原树两点间最大边权, 是这两个点在重构树上LCA的权值
    3. 任意非叶节点, 其子树中两叶节点间最大边权不超过该节点权值(本题需要用到的性质)

由于有了第三个性质, 对于一查询节点a,若它的某级祖先p的点权不超过x, 意味着它能到达p子树中任意一个点, 若其超过x, 从a到达子树外的点一定要经过这个点, 故不符合要求. 所以我们只需要倍增找到这个祖先p ,然后在p的子树里查询第K大即可.

对于子树的处理: 我们对叶子节点建立dfs序, 同时只按该dfs序建立主席树,

对于非叶子节点p,令其dfn为遍历到它的时候的cnt , oud为退出它时的cnt, 当查询其子树时, 由于dfn[p]并不真的包含它子树里的点, 也恰好是它子树前的一个叶子节点, 所以我们直接查询Tree[oud[p]]-Tree[dfn[p]]即可.

对于叶子节点, 我们把它扔到数组里, 并++cnt,注意,非叶节点不会影响cnt

而后就是一个简单的主席树区间第K大查询啦.

注意 : 小心在倍增的时候跳到0点

代码 :

#include 
#include 
#include 
#include 
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
using namespace std;
char buf[100000], *p1, *p2; const int N = 210000;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
struct Edge {
    int to;
    Edge *next;
}*h[N], e[N<<1];
struct Edge1 {
    int u, v, w;
    int operator < (const Edge1 &A) const {
        return w < A.w;
    }
}e1[N*5];
int a[N], f[20][N], q[N], rnk[N], fa[N], root[N];
int t[N*20], ls[N*20], rs[N*20], val[N], dep[N];
int dfn[N], oud[N];
inline void addEdge(int u, int v) {
    static int _;
    Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;
}
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void dfs(int p) {
    for(int i = 1; i < 20; i ++ ) f[i][p] = f[i-1][f[i-1][p]];
    dfn[p] = *q;
    if(!val[p]) q[++*q] = p;
    rev(i, p) f[0][i->to] = p, dfs(i->to);
    oud[p] = *q;
}
void insert(int l, int r, int &p, int q, int x) {
    static int _; if(!p) p = ++_;
    t[p] = t[q]+1;
    if(l == r) return;
    int mid = (l+r) >> 1;
    if(x <= mid) rs[p] = rs[q], insert(l, mid, ls[p], ls[q], x);
    else ls[p] = ls[q], insert(mid+1, r, rs[p], rs[q], x);
}
int query(int l, int r, int p, int q, int k) {
    if(l == r) return l;
    int sizl = t[ls[q]] - t[ls[p]];
    int mid = (l+r) >> 1;
    if(sizl >= k) return query(l, mid, ls[p], ls[q], k);
    else return query(mid+1, r, rs[p], rs[q], k-sizl);
}
int main() {
    int n = rd(), m = rd(), Q = rd(), ans = 0;
    for(int i = 1; i <= n; i ++ ) a[i] = rd(), rnk[i] = a[i];
    sort(rnk+1, rnk+n+1);
    for(int i = 1; i <= n; i ++ ) a[i] = lower_bound(rnk+1, rnk+n+1, a[i])-rnk;
    for(int i = 0; i < N; i ++ ) fa[i] = i;
    for(int i = 1; i <= m; i ++ ) e1[i].u = rd(), e1[i].v = rd(), e1[i].w = rd();
    sort(e1+1, e1+m+1); int cnt = n;
    for(int i = 1; i <= m; i ++ ) {
        int dx = find(e1[i].u), dy = find(e1[i].v);
        if(dx != dy) {
            ++cnt; fa[dx] = cnt; fa[dy] = cnt;
            val[cnt] = e1[i].w;
            addEdge(cnt, dx);
            addEdge(cnt, dy);
            if(cnt == 2*n-1) break;
        }
    }
    dfs(cnt);
    for(int i = 1; i <= n; i ++ ) insert(1, n, root[i], root[i-1], a[q[i]]);
    while(Q -- ) {
        int v = rd(), x = rd()^ans, k = rd()^ans;
        int tmp = v^ans;
        for(int i = 19; ~i; i -- ) if(f[i][tmp] && val[f[i][tmp]] <= x) {
            tmp = f[i][tmp];
        }
        if(k > oud[tmp] - dfn[tmp]) {
            puts("-1"); ans = 0; continue;
        }
        k = oud[tmp]-dfn[tmp]-k+1;
        ans = rnk[query(1, n, root[dfn[tmp]], root[oud[tmp]], k)];
        printf("%d\n", ans);
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注