题解 P3242 【[HNOI2015]接水果】

交了一发结果才第二页呢，果然人丑常数大...（顺便在打代码的时候发现自己出的一道题评测的时候被一位神仙 0 ms 过了，标算 1.470 S /kk） 正经讲题解： 首先我们考虑把原树树剖，然后记录树剖的 dfs 序（出入都要记），然后我们把每条路径映射到二维平面上的一个点 然后题目盘子要是苹果的子路径，我们可以把一个盘子能接住的苹果路径范围表示为二维平面上的一个矩形区间（或者两个），然后我们这时候只要查某个点的第 k 小覆盖覆盖矩形就好了，貌似是可以树套树的 QwQ 不过这里用了整体二分，我们以答案为二分的值，然后分层确定每个询问的答案位置就好了，分治的时候用到了扫描线思想以及常数较小（且好写）的树状数组维护 至于树状数组中询问内容是单点被覆盖了多少次，因为这时候我们就不用管什么 k 小不 k 小了，查询出来和询问的 k 比一下，大的减去覆盖次数丢右边，小的直接丢左边，然后继续向下二分就好了 本末倒置一下，现在讲怎么把盘子能接住的苹果路径范围表示出来： 我们发现如果盘子的路径两端点 x、y 为兄弟关系，那么能接住的苹果就要两端分别在 x 和 y 子树内，然后我们 然后盘子路径两端点 x、y 是父子关系，那么苹果两端一个在儿子子树内，另一个就是除去 y 对应上去的 x 子节点的子树以外的任意一个点，不如这么解释： >假设路径为 x,a,b,c,d,.....,y ，那么 y 对应上去的 x 子节点就是 a ，然后另一个节点就不能在 a 这棵子树内 这个判断父子关系很好实现，用 dfs 序就好了，找到 a 这个节点有点困难，但实际上用树剖就能实现： >首先做法是我们让 y 一直跳到 f[top[y]] ， 然后我们考虑节点间 top 的关系 >如果 a 是 x 的重儿子，那么我们在发现 top[y]==top[x] 的时候就确认了这个关系，那么直接返回 son[x] 就行了 >如果是轻儿子，那么我们已知跳直到 f[top[y]]=x ，返回 top[y] 即可 别的没了，常规操作（咱貌似做了好几天？【逃） # Code 狠短的代码！ ``` //by Judge #define HGS_AK_IOI true #include<bits/stdc++.h> #define Rg register #define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i) #define go(u) for(Rg int i=head[u],v=e[i].to;i;v=e[i=e[i].nxt].to) #define open(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define ll long long using namespace std; const int M=2e5+3; typedef int arr[M]; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) char buf[1<<21],*p1=buf,*p2=buf; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int CCF=-1,Z; inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;} inline void print(int x,char chr='\n'){ if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr; } int n,m,P,Q; arr h,ans; struct Line{ int x,l,r,v,val; Line(){} Line(int _x,int _l,int _r,int _v,int V){x=_x,l=_l,r=_r,v=_v,val=V;} bool operator <(const Line& b)const{return x<b.x;} }Li[M],*p[M],*tp[M]; struct Qry{ int x,y,k,id; Qry(){} Qry(int _x,int _y,int _k,int _id){x=_x,y=_y,k=_k,id=_id;} bool operator <(const Qry& b)const{return x^b.x?x<b.x:id>b.id;} }Qr[M],*q[M],*tq[M]; namespace TC{ int tim; arr f,son,siz,dep,top,In,Out; int pat,head[M]; struct Edge{int to,nxt;}e[M<<1]; inline void add(int u,int v){ e[++pat]=(Edge){v,head[u]},head[u]=pat; e[++pat]=(Edge){u,head[v]},head[v]=pat; } void dfs(int u,int fa){ dep[u]=dep[fa]+1,siz[u]=1; go(u) if(v^fa){ f[v]=u,dfs(v,u),siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs(int u){ In[u]=++tim; if(!top[u]) top[u]=u; if(son[u]) top[son[u]]=top[u],dfs(son[u]); go(u) if(v^f[u]&&v^son[u]) dfs(v); Out[u]=tim; } inline int Get(int u,int p){ for(;top[u]^top[p];u=f[top[u]]) if(f[top[u]]==p) return top[u]; return top[u]==u?u:son[p]; } } using namespace TC; namespace BIT{ arr c; #define lowbit(x) (x&-x) inline void add(int x,int v){ while(x<=n) c[x]+=v,x+=lowbit(x); } inline int ask(int x){ Rg int s=0; while(x) s+=c[x],x^=lowbit(x); return s; } inline void upd(int l,int r,int v){ add(l,v),add(r+1,-v); } } void CDQ(int pl,int pr,int ql,int qr,int hl,int hr){ if(pl>pr||ql>qr) return ; int mid=(hl+hr)>>1; if(hl==hr){ fp(i,ql,qr) ans[q[i]->id]=h[hl]; return ; } Rg int tpl=pl-1,tpr=pr+1,tql=ql-1,tqr=qr+1,j=pl,pp; fp(i,ql,qr){ while(j <= pr && p[j]->x <= q[i]->x) if(p[j]->val > h[mid]) tp[--tpr]=p[j],++j; else BIT::upd(p[j]->l, p[j]->r, p[j]->v),tp[++tpl]=p[j],++j; (q[i]->k > (pp=BIT::ask(q[i]->y))) ? q[i]->k -= pp,tq[--tqr]=q[i] : tq[++tql]=q[i]; } fp(i,pl,j-1) if(p[i]->val <= h[mid]) BIT::upd(p[i]->l, p[i]->r, -p[i]->v); while(j<=pr) ((p[j]->val > h[mid])?tp[--tpr]:tp[++tpl])=p[j],++j; fp(i,pl,tpl) p[i]=tp[i]; fp(i,tpr,pr) p[pr+tpr-i]=tp[i]; fp(i,ql,tql) q[i]=tq[i]; fp(i,tqr,qr) q[qr+tqr-i]=tq[i]; CDQ(pl,tpl,ql,tql,hl,mid),CDQ(tpr,pr,tqr,qr,mid+1,hr); } signed main(){ n=read(),P=read(),Q=read(); int x,y,z; fp(i,2,n) x=read(),y=read(),add(x,y); dfs(1,0),dfs(1); fp(i,1,P){ x=read(),y=read(),h[i]=read(); if(In[x]>In[y]) swap(x,y); if(In[x]<=In[y]&&In[y]<=Out[x]){ z=Get(y,x); Li[++m]=Line(1,In[y],Out[y],1,h[i]),Li[++m]=Line(In[z],In[y],Out[y],-1,h[i]); if(Out[z]<n) Li[++m]=Line(In[y],Out[z]+1,n,1,h[i]),Li[++m]=Line(Out[y]+1,Out[z]+1,n,-1,h[i]); } else Li[++m]=Line(In[x],In[y],Out[y],1,h[i]),Li[++m]=Line(Out[x]+1,In[y],Out[y],-1,h[i]); } fp(i,1,Q){ x=read(),y=read(),z=read(); if(In[x]>In[y]) swap(x,y); Qr[i]=Qry(In[x],In[y],z,i); } sort(Li+1,Li+1+m); fp(i,1,m) p[i]=Li+i; sort(Qr+1,Qr+1+Q); fp(i,1,Q) q[i]=Qr+i; sort(h+1,h+1+P),*h=unique(h+1,h+1+P)-h-1,CDQ(1,m,1,Q,1,h[0]); fp(i,1,Q) print(ans[i]); return Ot(),0; } ``` （被扇了两巴掌后）以后再也不压行了（反正就是香） ``` //by Judge #define HGS_AK_IOI true #include<bits/stdc++.h> #define Rg register #define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i) #define go(u) for(Rg int i=head[u],v=e[i].to;i;v=e[i=e[i].nxt].to) #define open(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define ll long long using namespace std; const int M=2e5+3; typedef int arr[M]; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) char buf[1<<21],*p1=buf,*p2=buf; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int CCF=-1,Z; inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;} inline void print(int x,char chr='\n'){ if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr; } int n,m,P,Q; arr h,ans; struct Line{ int x,l,r,v,val; Line(){} Line(int _x,int _l,int _r,int _v,int V){x=_x,l=_l,r=_r,v=_v,val=V;} bool operator <(const Line& b)const{return x<b.x;} }Li[M],*p[M],*tp[M]; struct Qry{ int x,y,k,id; Qry(){} Qry(int _x,int _y,int _k,int _id){x=_x,y=_y,k=_k,id=_id;} bool operator <(const Qry& b)const{return x^b.x?x<b.x:id>b.id;} }Qr[M],*q[M],*tq[M]; namespace TC{ //模板怎能不压行 /kk int tim; arr f,son,siz,dep,top,In,Out; int pat,head[M]; struct Edge{int to,nxt;}e[M<<1]; inline void add(int u,int v){ e[++pat]=(Edge){v,head[u]},head[u]=pat; e[++pat]=(Edge){u,head[v]},head[v]=pat; } void dfs(int u,int fa){ dep[u]=dep[fa]+1,siz[u]=1; go(u) if(v^fa){ f[v]=u,dfs(v,u),siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs(int u){ In[u]=++tim; if(!top[u]) top[u]=u; if(son[u]) top[son[u]]=top[u],dfs(son[u]); go(u) if(v^f[u]&&v^son[u]) dfs(v); Out[u]=tim; } inline int Get(int u,int p){ for(;top[u]^top[p];u=f[top[u]]) if(f[top[u]]==p) return top[u]; return top[u]==u?u:son[p]; } } using namespace TC; namespace BIT{ arr c; #define lowbit(x) (x&-x) inline void add(int x,int v){ while(x<=n) c[x]+=v,x+=lowbit(x); } inline int ask(int x){ Rg int s=0; while(x) s+=c[x],x^=lowbit(x); return s; } inline void upd(int l,int r,int v){ add(l,v),add(r+1,-v); } } void CDQ(int pl,int pr,int ql,int qr,int hl,int hr){ if(pl>pr||ql>qr) return ; if(hl==hr){ fp(i,ql,qr) ans[q[i]->id]=h[hl]; return ; } int mid=(hl+hr)>>1; Rg int tpl=pl-1,tpr=pr+1; Rg int tql=ql-1,tqr=qr+1; Rg int j=pl,pp; fp(i,ql,qr){ while(j <= pr && p[j]->x <= q[i]->x){ if(p[j]->val > h[mid]) tp[--tpr]=p[j],++j; else{ BIT::upd(p[j]->l, p[j]->r, p[j]->v), tp[++tpl]=p[j],++j; } } if(q[i]->k > (pp=BIT::ask(q[i]->y))) q[i]->k -= pp,tq[--tqr]=q[i]; else tq[++tql]=q[i]; } fp(i,pl,j-1) if(p[i]->val <= h[mid]) BIT::upd(p[i]->l, p[i]->r, -p[i]->v); while(j<=pr){ if(p[j]->val > h[mid]) tp[--tpr]=p[j],++j; else tp[++tpl]=p[j],++j; } fp(i,pl,tpl) p[i]=tp[i]; fp(i,tpr,pr) p[pr+tpr-i]=tp[i]; fp(i,ql,tql) q[i]=tq[i]; fp(i,tqr,qr) q[qr+tqr-i]=tq[i]; CDQ(pl,tpl,ql,tql,hl,mid); CDQ(tpr,pr,tqr,qr,mid+1,hr); } signed main(){ n=read(),P=read(),Q=read(); int x,y,z; fp(i,2,n) x=read(),y=read(),add(x,y); dfs(1,0),dfs(1); fp(i,1,P){ x=read(),y=read(),h[i]=read(); if(In[x]>In[y]) swap(x,y); if(In[x]<=In[y]&&In[y]<=Out[x]){ z=Get(y,x); Li[++m]=Line(1,In[y],Out[y],1,h[i]); Li[++m]=Line(In[z],In[y],Out[y],-1,h[i]); if(Out[z]<n){ Li[++m]=Line(In[y],Out[z]+1,n,1,h[i]); Li[++m]=Line(Out[y]+1,Out[z]+1,n,-1,h[i]); } } else{ Li[++m]=Line(In[x],In[y],Out[y],1,h[i]); Li[++m]=Line(Out[x]+1,In[y],Out[y],-1,h[i]); } } fp(i,1,Q){ x=read(),y=read(),z=read(); if(In[x]>In[y]) swap(x,y); Qr[i]=Qry(In[x],In[y],z,i); } sort(Li+1,Li+1+m); fp(i,1,m) p[i]=Li+i; sort(Qr+1,Qr+1+Q); fp(i,1,Q) q[i]=Qr+i; sort(h+1,h+1+P); *h=unique(h+1,h+1+P)-h-1; CDQ(1,m,1,Q,1,h[0]); fp(i,1,Q) print(ans[i]); return Ot(),0; } ``` # 效果展示 压行前：  压行后：