2019.01.13 bzoj1146: [CTSC2008]网络管理Network(整体二分+树剖)
2024-08-28 22:02:01
传送门
题意简述:给一棵树,支持单点修改,询问路径上两点间第kkk大值。
思路:
读懂题之后立马可以想到序列上带修区间kkk大数的整体二分做法,就是用一个bitbitbit来支持查值。
那么这个题把树状数组放到树上用树链剖分维护一下即可。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=8e4+5;
int n,m,a[N],siz[N],hson[N],fa[N],dep[N],top[N],num[N],pred[N],bit[N],ans[N],tot=0,sig=0,Q=0;
vector<int>e[N];
struct Node{int k,a,b,id;}q[N*3],qtmp1[N*3],qtmp2[N*3];
inline int lowbit(int x){return x&-x;}
inline void update(int x,int v){for(ri i=x;i<=n;i+=lowbit(i))bit[i]+=v;}
inline int query(int x){int ret=0;for(ri i=x;i;i-=lowbit(i))ret+=bit[i];return ret;}
void dfs1(int p){
siz[p]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
void dfs2(int p,int tp){
top[p]=tp,pred[num[p]=++tot]=p;
if(!hson[p])return;
dfs2(hson[p],tp);
for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])!=fa[p]&&v!=hson[p])dfs2(v,v);
}
inline int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
inline int dist(int a,int b){return dep[a]+dep[b]-2*dep[lca(a,b)]+1;}
inline int ask(int x,int y){
int ret=0;
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret+=query(num[x])-query(num[top[x]]-1),x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
return ret+query(num[x])-query(num[y]-1);
}
inline void solve(int ql,int qr,int vl,int vr){
if(ql>qr)return;
if(vl==vr){for(ri i=ql;i<=qr;++i)if(q[i].k&&~ans[q[i].id])ans[q[i].id]=vl;return;}
int mid=vl+vr>>1,hd1=0,hd2=0;
for(ri i=ql;i<=qr;++i){
if(!q[i].k){
if(q[i].b<=mid)qtmp1[++hd1]=q[i];
else qtmp2[++hd2]=q[i],update(num[q[i].a],q[i].id);
}
else{
int ret=ask(q[i].a,q[i].b);
if(ret>=q[i].k)qtmp2[++hd2]=q[i];
else q[i].k-=ret,qtmp1[++hd1]=q[i];
}
}
for(ri i=ql;i<=qr;++i)if(!q[i].k&&q[i].b>mid)update(num[q[i].a],-q[i].id);
for(ri i=1;i<=hd1;++i)q[ql+i-1]=qtmp1[i];
for(ri i=1;i<=hd2;++i)q[ql+hd1+i-1]=qtmp2[i];
solve(ql,ql+hd1-1,vl,mid),solve(ql+hd1,qr,mid+1,vr);
}
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i)q[++sig]=(Node){0,i,a[i]=read(),1};
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs1(1),dfs2(1,1);
for(ri i=1,k,x,y;i<=m;++i){
k=read(),x=read(),y=read();
if(!k){
q[++sig]=(Node){k,x,a[x],-1};
q[++sig]=(Node){k,x,a[x]=y,1};
}
else{
++Q;
int dis=dist(x,y);
if(dis<k)ans[Q]=-1;
q[++sig]=(Node){k,x,y,Q};
}
}
solve(1,sig,1,100000000);
for(ri i=1;i<=Q;++i){
if(~ans[i])cout<<ans[i]<<'\n';
else puts("invalid request!");
}
return 0;
}
最新文章
- MongoDB基本使用
- XStream使用总结
- double 类型转化为Integer类型 ---DecimalFormat
- PHP 设计模式 笔记与总结(11)观察者模式
- jsoup 获取指定页面的所有链接(需后续完善)
- c++ switch case
- 使用 JUnit 进行单元测试 - 教程
- JSP——九大内置对象和其四大作用域
- java中System类简介(转)
- RichErp - export import 用法
- XPath编写规则学习
- sleep wait yield
- 切换用户后,/etc/profile的配置不起效
- python练习四—简单的聊天软件
- SpringCloud无废话入门03:Feign声明式服务调用
- bootstrap 弹框使用
- Retrofit+RxJava(1)-在Android Studio中配置
- 网络基础 TCP/IP
- Redis(二十一):Redis性能问题排查解决手册(转)
- Hive查看执行日志
热门文章
- 解决 HDFS 开发 java.lang.IllegalArgumentException: java.net.UnknownHostException: hadoop000
- c#: TabControl隐藏选项卡(WizardPages)
- GridView中CheckBox单击事件(oncheckedchanged)
- docker搭建lnmp(一)
- django分页的东西, 不详细, 但是也足够了。
- faiss CPU版本+GPU版本安装
- 比特币学习-Transaction的locktime属性
- C#百度图片识别API调用返回数据包解析
- libjpeg安装和使用
- id不连续