Count On A Tree
建立线段树记录每个\([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]);
}
}
\[\
\]
\[\
\]
\[\
\]
middle
将权值离散化,对于每一个权值的前缀建立一棵线段树
对于第一棵树,所有叶子节点的权值为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;
}