傳送門

題意：給定一個$n$個點的樹，定義一個“盤子”為一個給定權值的路徑，一個“水果”為一條路徑，一個盤子可以接到水果當且僅當盤子的路徑是水果的子路徑。給出所有盤子和水果，對于每個水果求可以接它的盤子中第$k_i$小的權值。

$n\le 4\times 10^5$

顯然這種奇奇怪怪的第$k$小考慮整體二分

給盤子按權值排序，對于一個盤子和水果的區間，要計算出每個水果可以被區間內多少個盤子接住。

根據慣用套路，把一條路徑抽象成按 DFS 為坐標的點，一個盤子可以接的是一個或兩個矩形中的水果。

無腦掃描線即可。因為是區間修改單點查詢，可以差分后樹狀數組。

復雜度$O(能過)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #define MAXN 100005 #define MAXM 200005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } struct edge{int u,v;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; void addnode(int u,int v) {e[++cnt]=(edge){u,v};nxt[cnt]=head[u];head[u]=cnt; } int dfn[MAXN],ed[MAXN],dep[MAXN],fa[MAXN][16],tim; void dfs(int u) {for (int i=1;i<16;i++) fa[u][i]=fa[fa[u][i-1]][i-1];dfn[u]=++tim;for (int i=head[u];i;i=nxt[i])if (!dfn[e[i].v])dep[e[i].v]=dep[u]+1,fa[e[i].v][0]=u,dfs(e[i].v);ed[u]=tim; } int n,p,q; int ans[MAXN]; struct Pan{int a,b,c;}pan[MAXN]; struct fruit{int u,v,k,id;}fru[MAXN],L[MAXN],R[MAXN]; inline bool operator <(const Pan& x,const Pan& y){return x.c<y.c;} struct node{int type,x,l,r,id;}lis[MAXM]; //trangle: +-1,x,yl,yr //point: 0,x,y,k inline bool operator <(const node& a,const node& b) {if (a.x==b.x) return (unsigned)a.type>(unsigned)b.type;return a.x<b.x; } struct BIT {int s[MAXN];inline int lowbit(const int& x){return x&-x;}inline void modify(int x,int v){for (;x<=n;s[x]+=v,x+=lowbit(x));}inline int query(int x,int ans=0){for (;x;ans+=s[x],x-=lowbit(x));return ans;} }bit; void solve(int l,int r,int vl,int vr) {if (l>r||vl>vr) return;if (vl==vr){for (int i=l;i<=r;i++) ans[fru[i].id]=pan[vl].c;return;}int vmid=(vl+vr)>>1;int tot=0;for (int i=vl;i<=vmid;i++){int u=pan[i].a,v=pan[i].b;if (dfn[v]<=ed[u]){int t=dep[v]-dep[u]-1;u=v;for (int i=0;(1<<i)<=t;i++) if (t&(1<<i)) u=fa[u][i];lis[++tot]=(node){1,1,dfn[v],ed[v],0};lis[++tot]=(node){-1,dfn[u],dfn[v],ed[v],0};lis[++tot]=(node){1,dfn[v],ed[u]+1,n,0};lis[++tot]=(node){-1,ed[v]+1,ed[u]+1,n,0};}else{lis[++tot]=(node){1,dfn[u],dfn[v],ed[v],0};lis[++tot]=(node){-1,ed[u]+1,dfn[v],ed[v],0};}}for (int i=l;i<=r;i++) lis[++tot]=(node){0,dfn[fru[i].u],dfn[fru[i].v],fru[i].k,i};sort(lis+1,lis+tot+1);int lcnt=0,rcnt=0;for (int i=1;i<=tot;i++){if (lis[i].type) bit.modify(lis[i].l,lis[i].type),bit.modify(lis[i].r+1,-lis[i].type);else{int k=bit.query(lis[i].l);if (lis[i].r<=k) L[++lcnt]=fru[lis[i].id];else fru[lis[i].id].k-=k,R[++rcnt]=fru[lis[i].id];}}for (int i=l;i<=l+lcnt-1;i++) fru[i]=L[i-l+1];for (int i=l+lcnt;i<=r;i++) fru[i]=R[i-l-lcnt+1];solve(l,l+lcnt-1,vl,vmid);solve(l+lcnt,r,vmid+1,vr); } int main() {n=read(),p=read(),q=read();for (int i=1;i<n;i++){int u,v;u=read(),v=read();addnode(u,v),addnode(v,u);}dep[1]=1,dfs(1);for (int i=1;i<=p;i++) {pan[i].a=read(),pan[i].b=read(),pan[i].c=read();if (dfn[pan[i].a]>dfn[pan[i].b]) swap(pan[i].a,pan[i].b);}sort(pan+1,pan+p+1);for (int i=1;i<=q;i++){fru[i].u=read(),fru[i].v=read(),fru[i].k=read(),fru[i].id=i;if (dfn[fru[i].u]>dfn[fru[i].v]) swap(fru[i].u,fru[i].v);}solve(1,q,1,p);for (int i=1;i<=q;i++) printf("%d\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的【HNOI2015】接水果【整体二分】【DFS序】【双区间转矩形】【扫描线】【树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。