建立线段树记录每个\([1,u]\)路径上的前缀中在值域\([L,R]\)中的个数
查询时 计算 \(cnt[x]+cnt[y]-cnt[lca]-cnt[fa[lca]]\)
const int N=1e5+10,P=1e9+7; int n,m; int s[N*20],ls[N*20],rs[N*20],T[N]; int cnt; struct Edge{ int to,nxt; }e[N<<1]; int head[N],ecnt; void AddEdge(int u,int v){ e[++ecnt]=(Edge){v,head[u]}; head[u]=ecnt; } #define erep(u,i) for(int i=head[u];i;i=e[i].nxt) int fa[N][20]; int ncnt; void Add(int l,int r,int now,int pre,int x){ s[now]=s[pre]+1; if(l==r) return; int mid=(l+r)>>1; if(x<=mid) rs[now]=rs[pre],Add(l,mid,ls[now]=++cnt,ls[pre],x); else ls[now]=ls[pre],Add(mid+1,r,rs[now]=++cnt,rs[pre],x); } int Que(int l,int r,int a,int b,int lca,int f,int k){ if(l==r) return l; int mid=(l+r)>>1; int t=s[ls[a]]+s[ls[b]]-s[ls[lca]]-s[ls[f]]; if(t>=k) return Que(l,mid,ls[a],ls[b],ls[lca],ls[f],k); return Que(mid+1,r,rs[a],rs[b],rs[lca],rs[f],k-t); } int a[N],b[N],dep[N]; void dfs(int u,int f){ fa[u][0]=f; for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; Add(1,ncnt,T[u]=++cnt,T[f],a[u]); erep(u,i){ int v=e[i].to; if(v==f) continue; dep[v]=dep[u]+1; dfs(v,u); } } int LCA(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=0,del=dep[x]-dep[y];(1<<i)<=del;i++) if(del&(1<<i)) x=fa[x][i]; if(x==y) return x; drep(i,17,0) if(dep[x]>=(1<<i)){ if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; } return fa[x][0]; } int main(){ cnt=0; n=rd(),m=rd(); rep(i,1,n) a[i]=b[i]=rd(); sort(b+1,b+n+1);ncnt=unique(b+1,b+n+1)-b-1; rep(i,1,n) a[i]=lower_bound(b+1,b+ncnt+1,a[i])-b; rep(i,1,n-1) { int u=rd(),v=rd(); AddEdge(u,v),AddEdge(v,u); } dfs(1,0); rep(i,1,m){ int x=rd(),y=rd(),k=rd(); int lca=LCA(x,y); int ans=Que(1,ncnt,T[x],T[y],T[lca],T[fa[lca][0]],k); printf("%d\n",b[ans]); } }\[ \ \]
\[ \ \]
\[ \ \]
将权值离散化,对于每一个权值的前缀建立一棵线段树
对于第一棵树,所有叶子节点的权值为1
每次将小于这个权值的点的叶子节点更新为-1
线段树中,每个点\([L,R]\)存的是一段区间的
1.和
2.前缀最大
3.后缀最大
我们可以由中位数的定义得到一个结论
如果这个数\(x\)及小于等于它的数可以成为区间\([L,R]\)的中位数
则有这段区间里大于等于它的数的个数 大于等于 这段区间里小于它的个数
即在\(tree[x]\)中\(sum[L,R]>=0\)
这样的线段树存储,使我们可以在\([a,b]\)中找到最大的后缀和,在\([c,d]\)找到最大的前缀和,再加上中间这段\([b+1,c-1]\)的和得到最大的可能
那么我们如何得到这个x呢?
二分答案呗
const int N=20005,K=50; int n; int a[N],B[N],ncnt; int T[N]; struct node{ int lma,rma,s; }tr[N*K]; int ls[N*K],rs[N*K]; int cnt; vector <int> V[N]; void Up(node &p,node ls,node rs){ p.s=ls.s+rs.s; p.lma=max(ls.lma,ls.s+rs.lma); p.rma=max(rs.rma,ls.rma+rs.s); } void Build(int p,int l,int r){ tr[p]=(node){r-l+1,r-l+1,r-l+1}; if(l==r) return; int mid=(l+r)>>1; Build(ls[p]=++cnt,l,mid); Build(rs[p]=++cnt,mid+1,r); } void Add(int p,int pre,int l,int r,int x){ tr[p]=tr[pre]; if(l==r) { tr[p]=(node){-1,-1,-1} ; return; } int mid=(l+r)>>1; if(x<=mid) rs[p]=rs[pre],Add(ls[p]=++cnt,ls[pre],l,mid,x); else ls[p]=ls[pre],Add(rs[p]=++cnt,rs[pre],mid+1,r,x); Up(tr[p],tr[ls[p]],tr[rs[p]]); } node Que(int p,int l,int r,int ql,int qr){ if(l==ql&&r==qr) return tr[p]; int mid=(l+r)>>1; if(qr<=mid) return Que(ls[p],l,mid,ql,qr); else if(ql>mid) return Que(rs[p],mid+1,r,ql,qr); else { node ans; Up(ans,Que(ls[p],l,mid,ql,mid),Que(rs[p],mid+1,r,mid+1,qr)); return ans; } } bool Check(int k,int a,int b,int c,int d){ int ans=0; if(c-1>=b+1) ans+=Que(T[k],1,n,b+1,c-1).s; ans+=Que(T[k],1,n,a,b).rma+Que(T[k],1,n,c,d).lma; return ans>=0; } int main(){ n=rd(); rep(i,1,n) a[i]=B[i]=rd(); sort(B+1,B+n+1),ncnt=unique(B+1,B+n+1)-B-1; rep(i,1,n) V[a[i]=lower_bound(B+1,B+ncnt+1,a[i])-B].push_back(i); int pre; Build(pre=T[1]=++cnt,1,n); rep(i,2,ncnt){ T[i]=T[i-1]; rep(j,0,V[i-1].size()-1) { Add(T[i]=++cnt,pre,1,n,V[i-1][j]); pre=T[i]; } } pre=0; rep(kase,1,rd()){ int tmp[10]; rep(j,0,3) tmp[j]=(pre+rd())%n+1; sort(tmp,tmp+4); int l=1,r=ncnt; while(l<=r){ int mid=(l+r)>>1; if(Check(mid,tmp[0],tmp[1],tmp[2],tmp[3])) l=mid+1; else r=mid-1; } printf("%d\n",pre=B[l-1]); } return 0; }转载于:https://www.cnblogs.com/chasedeath/p/11259363.html
相关资源：JAVA上百实例源码以及开源项目