首页 > 代码库 > BZOJ1146: [CTSC2008]网络管理Network
BZOJ1146: [CTSC2008]网络管理Network
1146: [CTSC2008]网络管理Network
Time Limit: 50 Sec Memory Limit: 162 MBSubmit: 1724 Solved: 524
[Submit][Status]
Description
M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟时间。【任务】 你的程序从输入文件中读入N个路由器和N-1条光缆的连接信息，每个路由器初始的数据交换延迟时间Ti，以及Q条询问（或状态改变）的信息。并依次处理这Q条询问信息，它们可能是： 1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。 2. 查询某两个路由器a和b之间的路径上延迟第k大的路由器的延迟时间。
Input
第一行为两个整数N和Q，分别表示路由器总数和询问的总数。第二行有N个整数，第i个数表示编号为i的路由器初始的数据延迟时间Ti。紧接着N-1行，每行包含两个整数x和y。表示有一条光缆连接路由器x和路由器y。紧接着是Q行，每行三个整数k、a、b。如果k=0，则表示路由器a的状态发生了变化，它的数据交换延迟时间由Ta变为b。如果k>0，则表示询问a到b的路径上所经过的所有路由器（包括a和b）中延迟第k大的路由器的延迟时间。注意a可以等于b，此时路径上只有一个路由器。
Output
对于每一个第二种询问（k>0），输出一行。包含一个整数为相应的延迟时间。如果路径上的路由器不足k个，则输出信息“invalid request!”（全部小写不包含引号，两个单词之间有一个空格）。
Sample Input
5 5
5 1 2 3 4
3 1
2 1
4 3
5 3
2 4 5
0 1 2
2 2 3
2 1 4
3 3 5
5 1 2 3 4
3 1
2 1
4 3
5 3
2 4 5
0 1 2
2 2 3
2 1 4
3 3 5
Sample Output
3
2
2
invalid request!
2
2
invalid request!
HINT
10% 测试数据满足N<=8000,Q<=3000,
40% 测试数据满足所有询问中1<=K<=5 。即路由器的延迟时间不会发生变化。
100% 测试数据满足N,Q<=80000,任意一个路由器在任何时刻都满足延迟时间小于10^8。对于所有询问满足0<=K<=N 。
100% 测试数据满足N,Q<=80000,任意一个路由器在任何时刻都满足延迟时间小于10^8。对于所有询问满足0<=K<=N 。
题解：
先给iwtwiioi神牛跪了。。。
第一道CTSC题。。。
树套树+树链剖分
树链剖分向上提log+区间查询log+平衡树查询log+二分log n*log^4n
n=80000！我怀疑怎么过了。。。
刚开始看成第k小，后来又发现把二分写错了。。。应该是 yes-left 型
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #define inf 1000000000 12 #define maxn 80000+1000 13 #define maxm 80000*20 14 #define eps 1e-10 15 #define ll long long 16 using namespace std; 17 inline int read() 18 { 19 int x=0,f=1;char ch=getchar(); 20 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 21 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 22 return x*f; 23 } 24 int n,m,tot,cnt,a[maxn],b[maxn],top[maxn],fa[maxn],p[maxn],dep[maxn],head[maxn],son[maxn],size[maxn]; 25 int l[maxm],r[maxm],s[maxm],rnd[maxm],w[maxm],v[maxm]; 26 struct edge{int go,next;}e[2*maxn]; 27 struct rec{int l,r,rt;}t[4*maxn]; 28 void insert(int x,int y) 29 { 30 e[++tot].go=y;e[tot].next=head[x];head[x]=tot; 31 e[++tot].go=x;e[tot].next=head[y];head[y]=tot; 32 } 33 void pushup(int k) 34 {s[k]=s[l[k]]+s[r[k]]+w[k];} 35 void rturn(int &k) 36 {int t=l[k];l[k]=r[t];r[t]=k;s[t]=s[k];pushup(k);k=t;} 37 void lturn(int &k) 38 {int t=r[k];r[k]=l[t];l[t]=k;s[t]=s[k];pushup(k);k=t;} 39 void ins(int &k,int num) 40 { 41 if(!k) 42 {k=++tot;v[k]=num;s[k]=w[k]=1;l[k]=r[k]=0;rnd[k]=rand();return;} 43 s[k]++; 44 if(v[k]==num)w[k]++; 45 else if(num<v[k]) 46 {ins(l[k],num);if(rnd[l[k]]<rnd[k])rturn(k);} 47 else 48 {ins(r[k],num);if(rnd[r[k]]<rnd[k])lturn(k);} 49 } 50 void del(int &k,int num) 51 { 52 if(v[k]==num) 53 { 54 if(w[k]>1){w[k]--;s[k]--;} 55 else if(l[k]*r[k]==0)k=l[k]+r[k]; 56 else if(rnd[l[k]]<rnd[r[k]]) 57 {rturn(k);del(k,num);} 58 else {lturn(k);del(k,num);} 59 return; 60 } 61 s[k]--; 62 if(num<v[k])del(l[k],num);else del(r[k],num); 63 } 64 int rank(int k,int num) 65 { 66 if(!k) return 0; 67 if(v[k]==num)return s[r[k]]; 68 else if(num>v[k])return rank(r[k],num); 69 else return s[r[k]]+w[k]+rank(l[k],num); 70 } 71 void build(int k,int x,int y) 72 { 73 int l=t[k].l=x,r=t[k].r=y, mid=(l+r)>>1; 74 for(int i=l;i<=r;i++)ins(t[k].rt,a[i]); 75 if(l==r)return; 76 build(k<<1,l,mid);build(k<<1|1,mid+1,r); 77 } 78 void change(int k,int x,int y) 79 { 80 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 81 del(t[k].rt,a[x]);ins(t[k].rt,y); 82 if(l==r)return; 83 if(x<=mid)change(k<<1,x,y);else change(k<<1|1,x,y); 84 } 85 int query(int k,int x,int y,int z) 86 { 87 int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 88 if(l==x&&r==y)return rank(t[k].rt,z); 89 if(y<=mid)return query(k<<1,x,y,z); 90 else if(x>mid)return query(k<<1|1,x,y,z); 91 else return(query(k<<1,x,mid,z)+query(k<<1|1,mid+1,y,z)); 92 } 93 void dfs(int x) 94 { 95 size[x]=1; 96 for(int i=head[x],y=son[x]=0;i;i=e[i].next) 97 if(!dep[y=e[i].go]) 98 { 99 dep[y]=dep[x]+1;100 fa[y]=x;101 dfs(y);102 size[x]+=size[y];103 if(size[y]>size[son[x]])son[x]=y; 104 }105 }106 void dfs2(int x,int chain)107 {108 p[x]=++cnt;top[x]=chain;109 if(son[x])dfs2(son[x],chain);110 for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)111 if(y!=fa[x]&&y!=son[x])dfs2(y,y);112 }113 int getrank(int x,int y,int z)114 {115 int ans=0;116 while(top[x]!=top[y])117 {118 if(dep[top[x]]<dep[top[y]])swap(x,y);119 ans+=query(1,p[top[x]],p[x],z);120 x=fa[top[x]];121 }122 if(dep[x]>dep[y])swap(x,y);123 //cout<<ans<<endl;124 ans+=query(1,p[x],p[y],z);125 return ans;126 }127 int main()128 {129 freopen("input.txt","r",stdin);130 freopen("output.txt","w",stdout);131 n=read();m=read();132 for(int i=1;i<=n;i++)b[i]=read();133 int x,y,z;134 for(int i=1;i<n;i++)x=read(),y=read(),insert(x,y);135 dep[1]=1;136 dfs(1);137 dfs2(1,1);138 for(int i=1;i<=n;i++)a[p[i]]=b[i];139 build(1,1,n);140 while(m--)141 {142 z=read();x=read();y=read();143 if(!z)change(1,p[x],y),a[p[x]]=y;144 else145 {146 int l=0,r=inf;147 while(l<=r)148 {149 int mid=(l+r)>>1;150 if(getrank(x,y,mid)+1<=z)r=mid-1;else l=mid+1;151 }152 if(l>0)printf("%d\n",l);else puts("invalid request!");153 }154 }155 return 0;156 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。