【BZOJ-3545&3551】Peaks&加强版 Kruskal重构树 + 主席树 + DFS序 + 倍增

3545: [ONTAK2010]Peaks

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1202 Solved: 321
[Submit][Status][Discuss]

Description

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

Input

第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。

Output

对于每组询问，输出一个整数表示答案。

Sample Input

10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2

Sample Output

6
1
-1
8

HINT

【数据范围】

N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

Source

By Sbullet

3551: [ONTAK2010]Peaks加强版

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 810 Solved: 275
[Submit][Status][Discuss]

第一行三个数N，M，Q。

第二行N个数，第i个数为h_i

接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。

接下来Q行，每行三个数v x k，表示一组询问。v=v xor lastans，x=x xor lastans，k=k xor lastans。如果lastans=-1则不变。

Solution

先是非加强版，不强制在线，可以考虑离线，进行排序然后平衡树启发式合并搞搞就可以。

加强版要异或lastans，很显然不能上述做法，按照出题人的做法去搞：

首先我们发现，对结果有贡献的边，即最小生成树上的边，其余的边都是无用的，所以不妨先Kruskal建出最小生成树

但是这里的Kruskal与以往有不同，以往是直接连边，而这里需要用到另一种方式即 Kruskal重构树

具体方法很简单，以前是按边排序，用并查集维护联通性，每次连最小的边，这里思路类似，但是不是直接连边，而是构造一个新的节点，向这个边的两个端点连边，点权为这条边的边权（注意这里是单向边）

这里的Kruskal重构树有一些有用的性质：

1.二叉树(好吧这题意义不大)

2.原树与新树两点间路径上边权(点权)的最大值相等

3.子节点的边权小于等于父亲节点(大根堆)

4.原树中两点之间路径上边权的最大值等于新树上两点的LCA的点权

对于维护路径上的最值，就可以考虑倍增，倍增出来之后，建棵主席树，每次询问区间第K即可

PS.Claris好像有种方法，利用线段树合并来做，具体的并不会，但大体上会个板子

int merge(int x,int y,int a,int b)

{

    if (!x) return y;

    if (!y) return x;

    int z=++tot;

    if (a==b)

        v[z]=v[x]+v[y],return z;

    int mid=(a+b)>>;

    l[z]=merge(l[x],l[y],a,mid);

    r[z]=merge(r[x],r[y],mid+,b);

    v[z]=v[l[z]]+v[r[z]];

    return z;

}

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-')f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 100100

#define maxm 500100

int n,m,q; int hh[maxn],ls[maxn]; int steck[maxn<<],top;

struct data{

int from,to,hard;

bool operator < (const data& A) const

    {return hard<A.hard;}

}road[maxm];

struct dat{int next,to;}edge[maxn<<];int head[maxn<<],cnt;

void add(int u,int v){cnt++;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].to=v;}

int fa[maxn<<],va[maxn<<];

void init(){for (int i=; i<=n*; i++) fa[i]=i;}

int find(int x) {if (x==fa[x]) return x; return fa[x]=find(fa[x]);}

void Kruskal()

{

    init(); int zz=n;

    sort(road+,road+m+);

    for (int i=; i<=m; i++)

        {

            int u=road[i].from,v=road[i].to,w=road[i].hard;

            int fa1=find(u),fa2=find(v);

            if (fa1!=fa2)

                {

                    zz++; fa[fa1]=fa[fa2]=zz; va[zz]=w;

                    add(zz,fa2);add(zz,fa1);

                    if (zz==*n-) break;

                }

        }

}

bool visit[maxn<<];int father[maxn<<][],maxx[maxn<<][],deep[maxn<<];

void dfs(int x)

{

    visit[x]=; steck[++top]=x;

    for (int i=; i<; i++)

        if (deep[x]>=(<<i))

            father[x][i]=father[father[x][i-]][i-],

            maxx[x][i]=max(maxx[x][i-],maxx[father[x][i-]][i-]);

        else break;

    for (int i=head[x]; i; i=edge[i].next)

        {

            deep[edge[i].to]=deep[x]+;

            maxx[edge[i].to][]=va[x];

            father[edge[i].to][]=x;

            dfs(edge[i].to);

        }

    if (x>n) steck[++top]=x;

}

int sum[maxn*],ll[maxn*],rr[maxn*],root[maxn<<],sz;

void insert(int l,int r,int &now,int fat,int val)

{

    now=++sz; sum[now]=sum[fat]+;

    if (l==r) return;

    ll[now]=ll[fat],rr[now]=rr[fat];

    int mid=(l+r)>>;

    if (val<=mid) insert(l,mid,ll[now],ll[fat],val);

    else insert(mid+,r,rr[now],rr[fat],val);

}

int query(int l,int r,int L,int R,int kth)

{

    if (l==r) return l;

    int mid=(l+r)>>;

    if (sum[ll[R]]-sum[ll[L]]>=kth) return query(l,mid,ll[L],ll[R],kth);

    else return query(mid+,r,rr[L],rr[R],kth-sum[ll[R]]+sum[ll[L]]);

}

int st[maxn<<],ed[maxn<<];

void prework()

{

    for (int i=; i<=n; i++)

        if (!visit[i]) dfs(find(i));

    for (int  i=; i<=top; i++)

        {

            int tmp=steck[i];

            if (tmp<=n) insert(,n,root[i],root[i-],hh[tmp]);

            else

                {

                    root[i]=root[i-];

                    if (!st[tmp]) st[tmp]=i; else ed[tmp]=i;

                }

        }

}

int search(int x,int val)

{

    for(int i=;i>=;i--)

        if(deep[x]>=(<<i) && maxx[x][i]<=val) x=father[x][i];

    return x;

}

int main()

{

    n=read(),m=read(),q=read();

    for (int i=; i<=n; i++) hh[i]=read(),ls[i]=hh[i];

    sort(ls+,ls+n+);

    for (int i=; i<=n; i++)

        hh[i]=lower_bound(ls+,ls+n+,hh[i])-ls;

    for (int i=; i<=m; i++)

        road[i].from=read(),road[i].to=read(),road[i].hard=read();

    Kruskal();

    prework();

    int lastans=-,ans;

    for (int i=; i<=q; i++)

        {

            int v=read(),x=read(),k=read();

            if (lastans!=-) v^=lastans,x^=lastans,k^=lastans;

            int tmp=search(v,x);

               int a=root[st[tmp]],b=root[ed[tmp]];

            if (sum[b]-sum[a]<k) ans=-;

            else ans=ls[query(,n,a,b,sum[b]-sum[a]-k+)];

            printf("%d\n",ans); lastans=ans;

        }

    return ;

}

开始RE，后来MLE，后来WA，如此这般...简直不要太坑...外加本机Gena测全WA，提交AC....背水淹没

秒客网