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
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
1
-1
8
HINT
【数据范围】
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。
Source
3551: [ONTAK2010]Peaks加强版
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 810 Solved: 275
[Submit][Status][Discuss]
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....背水淹没