P4175 [CTSC2008]网络管理 题解
题面
比较经典的带修树上第 \(k\) 大问题。通常的做法是树剖树套树然后树上二分，一般3到4个 \(\log\)。这个题还可以用整体二分解决。
思考一下这道题目的整体二分过程：二分一个答案 \(mid\)，把所有的 \(>mid\) 的修改放到一个数据结构里，然后查询树上路径和。这显然可以使用树剖+线段树维护，单点加和区间查询，复杂度是 \(n\log^2 n\)。加上整体二分，总的复杂度是 \(O(n\log^2 n\log v)\)。如果值域较大，也可以先离散化，优化到 \(O(n\log^3 n)\)。
点击查看代码
#include
#include
#include
using namespace std;
const int N=80000+13;
struct Node{int x,y,k,op;}q[N<<2],lq[N<<2],rq[N<<2];
struct Edge{int v,nxt;}e[N<<1];
int n,m,tot,cnt,h[N],a[N],ans[N];
int fa[N],dep[N],siz[N],son[N],id[N],top[N],dfs_clock;
inline void add(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs1(int u,int f,int deep){
fa[u]=f,dep[u]=deep,siz[u]=1;
int maxson=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f) continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>maxson) maxson=siz[v],son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf,id[u]=++dfs_clock;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
struct SegTree{int l,r,sum;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
inline void refresh(int p){t[p].sum=t[ls].sum+t[rs].sum;}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return;
build(ls,l,mid),build(rs,mid+1,r);
}
void update(int p,int x,int k){
if(t[p].l==t[p].r) return t[p].sum+=k,void();
x<=mid?update(ls,x,k):update(rs,x,k);
refresh(p);
}
int query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
int res=0;
if(l<=mid) res+=query(ls,l,r);
if(r>mid) res+=query(rs,l,r);
return res;
}
#undef mid
int t_query(int u,int v){
int res=0;
while(top[u]!=top[v]){
if(dep[top[u]]id[v]) swap(u,v);
res+=query(1,id[u],id[v]);
return res;
}
void solve(int L,int R,int l,int r){
if(l>r) return;
if(L==R){
for(int i=l;i<=r;++i)
if(q[i].op) ans[q[i].op]=L;
return;
}
int mid=(L+R)>>1,lt=0,rt=0;
for(int i=l;i<=r;++i){
if(!q[i].op){
if(q[i].k>mid) update(1,id[q[i].x],q[i].y),rq[++rt]=q[i];
else lq[++lt]=q[i];
}
else{
int res=t_query(q[i].x,q[i].y);
if(res>=q[i].k) rq[++rt]=q[i];
else q[i].k-=res,lq[++lt]=q[i];
}
}
for(int i=l;i<=r;++i)
if(!q[i].op&&q[i].k>mid) update(1,id[q[i].x],-q[i].y);
for(int i=1;i<=lt;++i) q[l+i-1]=lq[i];
for(int i=1;i<=rt;++i) q[l+lt+i-1]=rq[i];
solve(L,mid,l,l+lt-1);
solve(mid+1,R,l+lt,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;++i){
scanf("%d",&x);a[i]=x;
q[++cnt]=(Node){i,1,x,0};
}
for(int i=1,u,v;i=0){
if(!ans[i]) puts("invalid request!");
else printf("%d\n",ans[i]);
}
return 0;
}