bzoj 3551 [ONTAK2010]Peaks加强版

bzoj 3551 [ONTAK2010]Peaks加强版

​​ 【题目描述】同3545 Input 第一行三个数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则不变。

Output 同3545 Sample Input

Sample Output

HINT 【数据范围】同3545 Source ​​​增加了强制在线 那么我之前离线的做法就不可以使用了

首先 我先建出kruskal 但是这个重建kruskal（最小生成树）的时候 我每次是新建一个节点 然后把他们的孩子都连 到一个节点上 然后倍增一下 求出我所有父节点中 <=我要求的值 的第一个节点出现在哪里那么他的子树的点就一定都可以走 因为我们这样建的一棵树他是满足类似大根堆的一个性质 那么我们就以深搜序 建树 每个点 建立主席树 然后状态都从前面继承过来 然后 我每次询问一棵子树嘛 我就直接线段树区间查找即可 这个建树的时候是把边做成点权 然后建树的

抄了下原题解

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

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

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

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

于是对于每个询问 我们从这个询问向上倍增寻找深度最小的点权小于等于x的点 易证这个节点的子树就是v所能到达的所有点

#include#include#define N 110000#define M 550000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int x,y,z;}data[M];struct node1{ int left,right,v;}tree[N*40];int n,m,q,nn,father[N<<1],son[N<<1][2],root[N<<1],tot,fa[N<<1][22],w[N<<1],h[N],h1[N],cnt,id[N<<1],out[N<<1];inline bool cmp(node a,node b){return a.z>1; if (p<=mid) insert1(tree[x].left,l,mid,p);else insert1(tree[x].right,mid+1,r,p);}inline int query(int rt1,int rt2,int l,int r,int v){ if(l==r) return l;int mid=l+r>>1;int l1=tree[rt1].left,l2=tree[rt2].left; if (v<=tree[l2].v-tree[l1].v) return query(l1,l2,l,mid,v); else return query(tree[rt1].right,tree[rt2].right,mid+1,r,v-(tree[l2].v-tree[l1].v));}void dfs(int x){ id[x]=++cnt;root[cnt]=root[cnt-1]; for (int i=1;i<=n<<1;++i){if (!fa[x][i-1]) break;fa[x][i]=fa[fa[x][i-1]][i-1];} if (x<=n) insert1(root[cnt],1,nn,h[x]);else for (int i=0;i<=1;++i) dfs(son[x][i]);out[x]=cnt;}inline int find1(int x,int v){ for (int i=20;i>=0;--i){ if (!fa[x][i]) continue; if (w[fa[x][i]]<=v) x=fa[x][i]; }return x;}void print(int x){ if (son[x][0]) print(son[x][0]); printf("%d %d\n",x,w[x]); if (son[x][1]) print(son[x][1]);}int main(){ freopen("bzoj3551.in","r",stdin); n=read();m=read();q=read(); for (int i=1;i<=n;++i) h[i]=read(),h1[i]=h[i];sort(h1+1,h1+n+1);nn=unique(h1+1,h1+n+1)-h1-1; for (int i=1;i<=n;++i) h[i]=lower_bound(h1+1,h1+nn+1,h[i])-h1; for (int i=1;i<=m;++i){data[i].x=read();data[i].y=read();data[i].z=read();} sort(data+1,data+m+1,cmp);int cnt=0,num=n; for (int i=1;i<=n<<1;++i) father[i]=i; for (int i=1;i<=m;++i){ int x=find(data[i].x),y=find(data[i].y); if(x==y) continue;father[x]=++num;father[y]=num;++cnt;fa[x][0]=fa[y][0]=num; son[num][0]=x;son[num][1]=y;w[num]=data[i].z;if (cnt==n-1) break; }dfs(num);int ans=0;//print(num); for (int i=1;i<=q;++i){ int x=read(),y=read(),k=read();x^=ans;y^=ans;k^=ans; int tar=find1(x,y); int tmp=tree[root[out[tar]]].v-tree[root[id[tar]-1]].v; if (tmp

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。