【BZOJ3545】 [ONTAK2010]Peaks

﹏ヽ暗。殇╰゛Y 2021-12-20 02:23 146阅读 0赞

# BZOJ3545 \[ONTAK2010\]Peaks #

--------------------

## Solution ##

既然会加强版,直接把强制在线的操作去掉就好了.

## 代码实现 ##

#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; }

转载于:https://www.cnblogs.com/mle-world/p/10315861.html