BZOJ3551 [ONTAK2010]Peaks加强版

---

Solution

Kruscal重构树后发现可以对于小于的离散化然后倍增+主席树找到上一个的可行解.

然后就可以了.

如果数组开的不好,容易在BZOJ编译超时()

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
int two[20];
int n,m,Q,cnt,top,tot,nodes,lastans;
int H[100005],h[100005];
int f[200005],val[200005],st[200005],ed[200005];
int q[300005],rt[300005];
int ls[5000005],rs[5000005],sum[5000005];
int dep[200005],fa[200005][17],mx[200005][17];
bool vis[200005];
struct node{int u,v,w;}e[500005];
int to[200005],nxt[200005],front[200005];
bool operator<(node a,node b){
    return a.w<b.w;
}
inline void Add(int u,int v){
    to[++cnt]=v;nxt[cnt]=front[u];front[u]=cnt;
}
inline int find(int x){
    if(f[x]!=x)f[x]=find(f[x]);
    return f[x];
}
inline int Find(int x,int val){
    for(int i=17;~i;i--)
        if(dep[x]>=two[i] && mx[x][i]<=val)x=fa[x][i];
    return x;
}
inline void insert(int l,int r,int &x,int f,int val){
    x=++tot;
    sum[x]=sum[f]+1;
    if(l==r)return;
    ls[x]=ls[f];rs[x]=rs[f];
    int mid=(l+r)>>1;
    if(val<=mid)insert(l,mid,ls[x],ls[f],val);
    else insert(mid+1,r,rs[x],rs[f],val);
}
inline int query(int l,int r,int x,int y,int rank){
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(sum[ls[y]]-sum[ls[x]]>=rank)return query(l,mid,ls[x],ls[y],rank);
    else return query(mid+1,r,rs[x],rs[y],rank-sum[ls[y]]+sum[ls[x]]);
}
inline void dfs(int u){
    vis[u]=1;q[++top]=u;
    for(int i=1;i<=16;i++)
        if(dep[u]>=two[i]){
            fa[u][i]=fa[fa[u][i-1]][i-1];
            mx[u][i]=max(mx[u][i-1],mx[fa[u][i-1]][i-1]);
        }
        else break;
    for(int i=front[u];i;i=nxt[i]){
        int v=to[i];
        dep[v]=dep[u]+1;
        mx[v][0]=val[u];
        fa[v][0]=u;
        dfs(v);
    }
    if(u>n)q[++top]=u;
}
inline void solve(){
    for(re int i=1;i<=Q;i++){
        re int v=gi(),x=gi(),k=gi();
        if(lastans!=-1)v^=lastans,x^=lastans,k^=lastans;
        re int t=Find(v,x);
        re int a=rt[st[t]],b=rt[ed[t]];
        if(sum[b]-sum[a]<k)lastans=-1;
        else lastans=H[query(1,n,a,b,sum[b]-sum[a]-k+1)];
        printf("%d\n",lastans);
    }
}
int main()
{
    two[0]=1;
    for(re int i=1;i<20;i++)two[i]=two[i-1]<<1;
    n=gi();m=gi();Q=gi();
    for(re int i=1;i<=n;i++)h[i]=gi(),H[i]=h[i];
    sort(H+1,H+n+1);
    for(re int i=1;i<=n;i++)h[i]=lower_bound(H+1,H+n+1,h[i])-H;
    for(re int i=1;i<=n+n;i++)f[i]=i;
    for(re int i=1;i<=m;i++)
        e[i].u=gi(),e[i].v=gi(),e[i].w=gi();
    sort(e+1,e+m+1);
    nodes=n;
    for(re int i=1;i<=m;i++){
        re int u=find(e[i].u),v=find(e[i].v);
        if(u!=v){
            nodes++;
            f[u]=f[v]=nodes;
            val[nodes]=e[i].w;
            Add(nodes,u);Add(nodes,v);
            if(nodes==2*n-1)break;
        }
    }
    for(re int i=1;i<=n;i++)
        if(!vis[i])dfs(find(i));
    for(re int i=1;i<=top;i++){
        re int t=q[i];
        if(t<=n)insert(1,n,rt[i],rt[i-1],h[t]);
        else{
            rt[i]=rt[i-1];
            if(!st[t])st[t]=i;
            else ed[t]=i;
        }
    }
    solve();
    return 0;
}