给定一棵树,每次询问某点子树中到其不超过k的所有点的最小点权 强制在线
\(n,m\le 10^5\)
看到题目第一反应是以深度为下标,dfs序为版本建树
然而不行,因为min不满足前缀可减
所以我们换过来,每个\(dep\)建树表示\(<=dep\)所有点的权值
在上面直接查x子树的min就好了
貌似这题用线段树合并就是SBT......
#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int mxn=5e5+5,inf=1e9; int n,m,tot,cnt,rk[mxn],hd[mxn]; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(int &x,int y) {if(xy) x=y;} struct ed { int to,nxt; }t[mxn<<1]; inline void add(int u,int v) { t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt; } int df,dep[mxn],lst[mxn],dfn[mxn],tr[mxn<<5],ls[mxn<<5],rs[mxn<<5],a[mxn],rt[mxn]; void dfs(int u,int fa) { dep[u]=dep[fa]+1; dfn[u]=++df; for(int i=hd[u];i;i=t[i].nxt) { int v=t[i].to; if(v==fa) continue ; dfs(v,u); } lst[u]=df; } int cmp(int x,int y) { return dep[x]>1; if(pos<=mid) update(ls[las],ls[p],l,mid,pos,val),rs[p]=rs[las]; else update(rs[las],rs[p],mid+1,r,pos,val),ls[p]=ls[las]; tr[p]=min(tr[ls[p]],tr[rs[p]]); } int query(int p,int l,int r,int ql,int qr) { if(!p) return inf; if(ql<=l&&r<=qr) return tr[p]; int mid=(l+r)>>1; int res=inf; if(ql<=mid) chkmin(res,query(ls[p],l,mid,ql,qr)); if(qr>mid) chkmin(res,query(rs[p],mid+1,r,ql,qr)); return res; } int r; int main() { n=read(); r=read(); int u,v,p,q; memset(tr,0x3f,sizeof(tr)); for(int i=1;i<=n;++i) rk[i]=i,a[i]=read(); for(int i=1;i