【BZOJ4009】接水果（整体二分，扫描线）

题面

题解

看到这道题，感觉就是主席树/整体二分之类的东西

（因为要求第\(k\)大）

但是，读完题目之后，我们发现路径之间的包含关系很不好搞

那么，我们来画画图

这是第一种情况，\(lca\)不是\(u,v\)

\(u,v\)分别是一个盘子的两端

如果被一个水果完全覆盖，

那么，这个水果的两端分别在\(u,v\)的子树中

设\(dfn[u]\)是\(u\)的\(dfs\)序

\(low[u]\)是子树中最大的\(dfn\)

那么，设水果两端分别为\(a,b\)

\[dfn[u]\leq dfn[a] \leq low[u],dfn[v]\leq dfn[b]\leq low[v]\]

再看第二种情况

也就是说，此时\(u\)是\(lca\)

那么，一个点还是在\(v\)的子树内

另一个点在这条链的子树外

设\(u,v\)链上的\(u\)的儿子为\(w\)

那么，水果的一个点一定不在\(w\)的子树内

也就是说：

\[dfn[v]\leq dfn[a]\leq low[v]\]

\[dfn[b]<dfn[w]\ or\ low[w]<dfn[b]\]

好的

现在知道了这些，有什么用？？？

如果我们把盘子的\(dfn[u],dfn[v],low[u],low[v]\)看成两个点

组成了一个矩形

那么，水果的\(dfn[a],dfn[b]\)就是一个点

所以，一个水果如果被盘子所完全覆盖

那么，也就是水果组成的点被盘子组成的矩形所包含

所以整体二分+扫描线求解就很容易做了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 50000inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}struct edge{int v,next;}e[MAX<<1];int h[MAX],cnt=1;inline void Add(int u,int v){e[cnt]=(edge){v,h[u]};h[u]=cnt++;}int p[18][MAX],dep[MAX];int n,P,Q,dfn[MAX],tim,low[MAX],tot;struct Mt{int x1,y1,x2,y2,k;}t[MAX<<2];struct Fr{int x,y,k,id;}q[MAX],q1[MAX],q2[MAX];struct Li{int l,r,x,v;}lk[MAX];bool operator<(Mt a,Mt b){return a.k
              
               =0;--i) if(dep[p[i][u]]>dep[v])u=p[i][u]; if(p[0][u]==v)return opt?u:v; u=p[0][u]; for(int i=15;i>=0;--i) if(p[i][u]!=p[i][v]) u=p[i][u],v=p[i][v]; return opt?u:p[0][u];}int c[MAX],ans[MAX];inline int lowbit(int x){return x&(-x);}inline void Modify(int x,int w){while(x<=n)c[x]+=w,x+=lowbit(x);}inline int getsum(int x){int ret=0;while(x)ret+=c[x],x-=lowbit(x);return ret;}void Work(int L,int R,int l,int r){ if(L>R)return; if(l==r) { for(int i=L;i<=R;++i)ans[q[i].id]=t[l].k; return; } int mid=(l+r)>>1,t1=0,t2=0,cnt=0; for(int i=l;i<=mid;++i) { lk[++cnt]=(Li){t[i].y1,t[i].y2,t[i].x1,1}; lk[++cnt]=(Li){t[i].y1,t[i].y2,t[i].x2+1,-1}; } sort(&lk[1],&lk[cnt+1]); int pos=1; for(int i=L;i<=R;++i) { while(pos<=cnt&&lk[pos].x<=q[i].x) Modify(lk[pos].l,lk[pos].v),Modify(lk[pos].r+1,-lk[pos].v),++pos; int ss=getsum(q[i].y); if(q[i].k<=ss)q1[++t1]=q[i]; else q[i].k-=ss,q2[++t2]=q[i]; } for(int i=1;i
               
                dfn[b])swap(a,b); int lca=LCA(a,b,0); if(a!=lca) t[++tot]=(Mt){dfn[a],dfn[b],low[a],low[b],k}; else { int d=LCA(a,b,1); if(dfn[d]!=1)t[++tot]=(Mt){1,dfn[b],dfn[d]-1,low[b],k}; if(low[d]!=n)t[++tot]=(Mt){dfn[b],low[d]+1,low[b],n,k}; } } for(int i=1;i<=Q;++i) { int u=read(),v=read(),k=read(); if(dfn[u]>dfn[v])swap(u,v); q[i]=(Fr){dfn[u],dfn[v],k,i}; } sort(&t[1],&t[tot+1]);sort(&q[1],&q[Q+1]); Work(1,Q,1,tot); for(int i=1;i<=Q;++i)printf("%d\n",ans[i]); return 0;}