很明顯只有最小生成樹里面的點有用

我會一個離線的做法，把詢問邊長排序，逐步合并樹，啟發式合并splay

在線怎么做呢？

考慮合并出最小生成樹的過程，兩點合并是并不是一邊連向一邊而是建出新點，并將新點連向兩邊邊權為這兩點的邊權。重構出新樹后，所有原點都是葉子節點，并且邊權深到淺單增，可以用倍增找到斷開的位置，問題變成求子樹中第k大的值，上一個主席樹就好了

碼力堪憂

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int _=1e2; const int maxn=1e5+_; const int maxp=2*maxn; const int maxm=5e5+_; const int maxQ=5e5+_; int n,m,Q,w[maxn]; int lslen,ls[maxn]; inline int read() {int x=0,f=1;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int d) {if(d>=10)write(d/10);putchar(d%10+'0'); }namespace CHAIR {struct trnode{int lc,rc,c;}tr[12*maxp];int trlen,rt[maxp];int maketree(int now,int l,int r,int p){if(now==0)now=++trlen;tr[now].c++;if(l!=r){int mid=(l+r)/2;if(p<=mid)tr[now].lc=maketree(tr[now].lc,l,mid,p);else tr[now].rc=maketree(tr[now].rc,mid+1,r,p);}return now;}int merge(int x,int y){if(x==0||y==0)return x+y;tr[x].c+=tr[y].c;tr[x].lc=merge(tr[x].lc,tr[y].lc);tr[x].rc=merge(tr[x].rc,tr[y].rc);return x;}int findkth(int x,int y,int l,int r,int k){if(tr[y].c-tr[x].c<k)return -1;if(l==r)return l;int mid=(l+r)/2;int c=tr[tr[y].rc].c-tr[tr[x].rc].c;if(c>=k)return findkth(tr[x].rc,tr[y].rc,mid+1,r,k);else return findkth(tr[x].lc,tr[y].lc,l,mid,k-c);} }struct node {int x,y,d,next; }a[maxp];int len,last[maxp]; void ins(int x,int y,int d) {len++;a[len].x=x;a[len].y=y;a[len].d=d;a[len].next=last[x];last[x]=len; // printf("%d %d %d\n",x,y,d); } int z,L[maxp],R[maxp],de[maxp]; int dep[maxp],f[30][maxp]; void dfs(int x) {for(int i=1;(1<<i)<=dep[x];i++)f[i][x]=f[i-1][f[i-1][x]];L[x]=++z;if(last[x]==0){CHAIR::rt[z]=CHAIR::maketree(CHAIR::rt[z],1,lslen,w[x]);CHAIR::rt[z]=CHAIR::merge(CHAIR::rt[z],CHAIR::rt[z-1]);}else CHAIR::rt[z]=CHAIR::rt[z-1];for(int k=last[x];k;k=a[k].next){int y=a[k].y; de[y]=a[k].d;f[0][y]=x;dep[y]=dep[x]+1;dfs(y);}R[x]=z; }int fa[maxp]; int findfa(int x) {if(fa[x]==x)return x;fa[x]=findfa(fa[x]);return fa[x]; } struct edge{int x,y,d;}e[maxm]; bool cmp(edge e1,edge e2){return e1.d<e2.d;} int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);n=read(),m=read(),Q=read();for(int i=1;i<=n;i++)w[i]=read(),ls[++lslen]=w[i];sort(ls+1,ls+lslen+1);lslen=unique(ls+1,ls+lslen+1)-ls-1;for(int i=1;i<=n;i++)w[i]=lower_bound(ls+1,ls+lslen+1,w[i])-ls;for(int i=1;i<=m;i++)e[i].x=read(),e[i].y=read(),e[i].d=read();sort(e+1,e+m+1,cmp);int fx,fy;for(int i=1;i<=2*n;i++)fa[i]=i;for(int i=1;i<=m;i++){fx=findfa(e[i].x),fy=findfa(e[i].y);if(fx!=fy){n++; fa[fx]=n,fa[fy]=n;ins(n,fx,e[i].d);ins(n,fy,e[i].d);}}dfs(n);int x,k,d,lastans=0;while(Q--){x=read(),d=read(),k=read();x^=lastans,k^=lastans,d^=lastans;if(de[x]>d){if(k==1)lastans=w[x],printf("%d\n",w[x]);else puts("-1"),lastans=0;continue;}for(int i=25;i>=0;i--)if((1<<i)<dep[x]&&de[f[i][x]]<=d)x=f[i][x];x=f[0][x];lastans=CHAIR::findkth(CHAIR::rt[L[x]-1],CHAIR::rt[R[x]],1,lslen,k);if(lastans!=-1){lastans=ls[lastans];write(lastans),putchar('\n');}else puts("-1"),lastans=0;}return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/10730777.html

總結

以上是生活随笔為你收集整理的bzoj3551: [ONTAK2010]Peaks加强版的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。