P7834 [ONTAK2010] Peaks 加强版 记录

· · 题解

前置芝士

题意：给一个无向图，每个点存在一个点权，进行若干次强制在线询问，从点 u 出发，只经过权值 \le x 的边，到达第 k 大的点。

你先做出来一个 \text{Kruskal} 重构树，边权从小到大排序，建出来一个顶上点权代表拥有这个点权，你可以在这个子树下的点构成的图里随便走。

然后对于每次询问倍增地跳父亲，一直跳到一个点权 \le x 的最浅点，这样这个点的子树就是可以走到的点。

然后你维护主席树，用 \text{dfn} 序跑就行了。

现在是 18:35，我看我什么时候写完。

现在是 20:00，我写完了。

#define maxn 1000010
int n,m,Q;
int a[maxn],b[maxn];
int head[maxn],Next[maxn<<1],ver[maxn<<1],tot;
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
struct prpr{
    int x,y,z;
}q[maxn];
int fa[maxn],rk[maxn];
int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
int fx,fy,cnt;
int siz[maxn];
int t,FA[maxn][20];
struct qrqr{
    int lc,rc,sm;
}tree[maxn*24];
int _g_;
int rt[maxn];
int insert(int now,int pos,int l=1,int r=b[0]){
    int rt=++_g_;
    tree[rt]=tree[now];tree[rt].sm++;
    if(l==r)return _g_;
    int mid=(l+r)>>1;
    if(pos<=mid)tree[rt].lc=insert(tree[now].lc,pos,l,mid);
    else tree[rt].rc=insert(tree[now].rc,pos,mid+1,r);
    return rt;
}
int ask(int p,int q,int k,int l=1,int r=b[0]){
    if(l==r)return l;
    int cnt=tree[tree[q].lc].sm-tree[tree[p].lc].sm;
    int mid=(l+r)>>1;
    if(k<=cnt)return ask(tree[p].lc,tree[q].lc,k,l,mid);
    return ask(tree[p].rc,tree[q].rc,k-cnt,mid+1,r);
}
int dfn[maxn],____;
void dfs(int x){
    dfn[x]=++____;
    rk[____]=x;
    siz[x]=1;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        FA[y][0]=x;
        for(int j=1;j<=t;j++)FA[y][j]=FA[FA[y][j-1]][j-1];
        dfs(y);
        siz[x]+=siz[y];
    }
}
int u,x,k,cc,lst;
int val[maxn];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("testdata.in","r",stdin);
#endif
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    b[0]=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
    for(int i=1;i<=m;i++)
        cin>>q[i].x>>q[i].y>>q[i].z;
    sort(q+1,q+m+1,[&](prpr a,prpr b){return a.z<b.z;});
    cnt=n;
    for(int i=1;i<=n+m;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        fx=get(q[i].x),fy=get(q[i].y);
        if(fx==fy)continue;
        fa[fx]=fa[fy]=++cnt;
        add(cnt,fx),add(cnt,fy);
        val[cnt]=q[i].z;
    }
    t=ceil(log(n)/log(2));
    dfs(cnt);
    for(int i=1;i<=____;i++){//直接枚举dfn，我觉得很妙啊
        if(!head[rk[i]])rt[i]=insert(rt[i-1],a[rk[i]]);
        else rt[i]=rt[i-1];
    }
    val[0]=INT_MAX;
    while(Q--){
        cin>>u>>x>>k;
        u=(u^lst)%n+1,x=x^lst,k=(k^lst)%n+1;
        for(int i=t;~i;i--)
        if(val[FA[u][i]]<=x)u=FA[u][i];
        if(tree[rt[dfn[u]+siz[u]-1]].sm-tree[rt[dfn[u]-1]].sm<k)cout<<-1<<endl,lst=0;
        else cout<<(lst=b[ask(rt[dfn[u]-1],rt[dfn[u]+siz[u]-1],tree[rt[dfn[u]+siz[u]-1]].sm-tree[rt[dfn[u]-1]].sm-k+1)])<<endl;
    }
#ifndef ONLINE_JUDGE
    cerr<<endl<<(double)clock()/CLOCKS_PER_SEC;
#endif
}

我自己代码都不认识了。。。。

处理树上问题真是麻烦，细节要考虑周到。

我才不会告诉你们我的原版记录\text{TLE} 的原因是并查集写假了呢。