網(wǎng)絡(luò)管理

Time Limit:?50 Sec??Memory Limit:?162 MB
[Submit][Status][Discuss]

Description

　　M公司是一個非常龐大的跨國公司，在許多國家都設(shè)有它的下屬分支機構(gòu)或部門。
　　為了讓分布在世界各地的N個部門之間協(xié)同工作，公司搭建了一個連接整個公司的通信網(wǎng)絡(luò)。
　　該網(wǎng)絡(luò)的結(jié)構(gòu)由N個路由器和N-1條高速光纜組成。
　　每個部門都有一個專屬的路由器，部門局域網(wǎng)內(nèi)的所有機器都聯(lián)向這個路由器，然后再通過這個通信子網(wǎng)與其他部門進行通信聯(lián)絡(luò)。
　　該網(wǎng)絡(luò)結(jié)構(gòu)保證網(wǎng)絡(luò)中的任意兩個路由器之間都存在一條直接或間接路徑以進行通信。
　　高速光纜的數(shù)據(jù)傳輸速度非常快，以至于利用光纜傳輸?shù)难舆t時間可以忽略。
　　但是由于路由器老化，在這些路由器上進行數(shù)據(jù)交換會帶來很大的延遲。
　　而兩個路由器之間的通信延遲時間則與這兩個路由器通信路徑上所有路由器中最大的交換延遲時間有關(guān)。
　　作為M公司網(wǎng)絡(luò)部門的一名實習員工，現(xiàn)在要求你編寫一個簡單的程序來監(jiān)視公司的網(wǎng)絡(luò)狀況。
　　該程序能夠隨時更新網(wǎng)絡(luò)狀況的變化信息（路由器數(shù)據(jù)交換延遲時間的變化），并且根據(jù)詢問給出兩個路由器通信路徑上延遲第k大的路由器的延遲時間。
　　你的程序從輸入文件中讀入N個路由器和N-1條光纜的連接信息，每個路由器初始的數(shù)據(jù)交換延遲時間Ti，以及Q條詢問（或狀態(tài)改變）的信息。
　　并依次處理這Q條詢問信息，它們可能是：
　　　　1. 由于更新了設(shè)備，或者設(shè)備出現(xiàn)新的故障，使得某個路由器的數(shù)據(jù)交換延遲時間發(fā)生了變化；
　　　　2. 查詢某兩個路由器a和b之間的路徑上延遲第k大的路由器的延遲時間。

Input

　　第一行為兩個整數(shù)N和Q，分別表示路由器總數(shù)和詢問的總數(shù)。
　　第二行有N個整數(shù)，第i個數(shù)表示編號為i的路由器初始的數(shù)據(jù)延遲時間Ti。
　　緊接著N-1行，每行包含兩個整數(shù)x和y，表示有一條光纜連接路由器x和路由器y。
　　緊接著是Q行，每行三個整數(shù)k、a、b。
　　如果k=0，則表示路由器a的狀態(tài)發(fā)生了變化，它的數(shù)據(jù)交換延遲時間由Ta變?yōu)閎。
　　如果k>0，則表示詢問a到b的路徑上所經(jīng)過的所有路由器（包括a和b）中延遲第k大的路由器的延遲時間。

Output

　　對于每一個第二種詢問（k>0），輸出一行。
　　包含一個整數(shù)為相應(yīng)的延遲時間。
　　如果路徑上的路由器不足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

Sample Output

　　3
　　2
　　2
　　invalid request!

HINT

　　N,Q<=80000，任意一個路由器在任何時刻都滿足延遲時間小于10^8。
　　對于所有詢問滿足0<=K<=N。

Main idea

　　求樹上兩點路徑間第k大的樹，需要支持單點修改權(quán)值。

Solution

　　我們一看到這道題，序列的話其實就是BZOJ1901改成求第k大。

　　我們基于這個思路，從整體二分考慮，然后我們運用樹鏈剖分和線段樹。

　　對于一個點，如果價值>=M的話就把這個點的位置+1權(quán)值，然后線段樹區(qū)間求和就可以找出這個詢問 在當前執(zhí)行的L,M中 有幾個>=M的數(shù)，由于是樹結(jié)構(gòu)，所以這個應(yīng)該運用樹鏈剖分來在線段樹上加。

　　之后跟靜態(tài)查詢Kth一樣判斷一下貢獻，整體二分繼續(xù)往下分治即可。

　　這題思路簡單，實現(xiàn)稍微有一點細節(jié)需要注意，算是一道經(jīng)典的數(shù)據(jù)結(jié)構(gòu)題。\(≧▽≦)/

Code

1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<map> 9 using namespace std; 10 11 const int ONE=160005; 12 const int INF=1e8+1; 13 14 int n,m; 15 int x,y,k; 16 int a[ONE]; 17 int next[ONE*2],first[ONE],go[ONE*2],tot; 18 int Num,res,cnt; 19 int record[ONE]; 20 int Ans[ONE]; 21 22 struct power 23 { 24 int cnt,opt,cur; 25 int pos,value; 26 int l,r,k; 27 }oper[ONE*10],qL[ONE*10],qR[ONE*10]; 28 29 struct point 30 { 31 int f,son,size,dep; 32 int top,seg; 33 }S[ONE]; 34 35 int get() 36 { 37 int res=1,Q=1;char c; 38 while( (c=getchar())<48 || c>57 ) 39 if(c=='-')Q=-1; 40 res=c-48; 41 while( (c=getchar())>=48 && c<=57 ) 42 res=res*10+c-48; 43 return res*Q; 44 } 45 46 void Add(int u,int v) 47 { 48 next[++tot]=first[u]; first[u]=tot; go[tot]=v; 49 next[++tot]=first[v]; first[v]=tot; go[tot]=u; 50 } 51 52 namespace Sgt 53 { 54 struct power 55 { 56 int value; 57 }Node[ONE*4]; 58 59 void Update(int i,int l,int r,int L,int x) 60 { 61 if(l==r) 62 { 63 Node[i].value+=x; 64 return; 65 } 66 67 int mid=(l+r)>>1; 68 if(L<=mid) Update(i<<1,l,mid,L,x); 69 else Update(i<<1|1,mid+1,r,L,x); 70 Node[i].value=Node[i<<1].value + Node[i<<1|1].value; 71 } 72 73 void Query(int i,int l,int r,int L,int R) 74 { 75 if(L<=l && r<=R) 76 { 77 res+=Node[i].value; 78 return; 79 } 80 81 int mid=(l+r)/2; 82 if(L<=mid) Query(i<<1,l,mid,L,R); 83 if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R); 84 } 85 } 86 87 namespace Hld 88 { 89 void First() 90 { 91 S[1].top=S[0].seg=S[1].seg=1; 92 } 93 94 void Dfs1(int u,int father) 95 { 96 S[u].dep=S[father].dep+1; 97 S[u].f=father; 98 S[u].size=1; 99 for(int e=first[u];e;e=next[e]) 100 { 101 int v=go[e]; 102 if(v==father) continue; 103 Dfs1(v,u); 104 S[u].size+=S[v].size; 105 if(S[v].size > S[S[u].son].size) S[u].son=v; 106 } 107 } 108 109 void Dfs2(int u,int father) 110 { 111 if(S[u].son) 112 { 113 int v=S[u].son; 114 S[v].top=S[u].top; 115 S[v].seg=++S[0].seg; 116 Dfs2(v,u); 117 } 118 for(int e=first[u];e;e=next[e]) 119 { 120 int v=go[e]; 121 if(v==father || S[u].son==v) continue; 122 S[v].top=v; 123 S[v].seg=++S[0].seg; 124 Dfs2(v,u); 125 } 126 } 127 128 void Solve(int x,int y) 129 { 130 int Tx=S[x].top,Ty=S[y].top; 131 while(Tx!=Ty) 132 { 133 if(S[Tx].dep < S[Ty].dep) 134 { 135 swap(x,y); 136 swap(Tx,Ty); 137 } 138 Sgt::Query(1,1,n,S[Tx].seg,S[x].seg); 139 x=S[Tx].f; 140 Tx=S[x].top; 141 } 142 if(S[x].dep > S[y].dep) swap(x,y); 143 Sgt::Query(1,1,n,S[x].seg,S[y].seg); 144 } 145 } 146 147 void Solve(int l,int r,int L,int R)//第k大 148 { 149 if(l>r) return; 150 if(L==R) 151 { 152 for(int i=l;i<=r;i++) 153 if(oper[i].opt==3) 154 Ans[oper[i].cnt] = L-1; 155 return; 156 } 157 158 int M=(L+R)>>1; 159 160 for(int i=l;i<=r;i++) 161 { 162 if(oper[i].opt==1 && oper[i].value>=M) 163 Sgt::Update(1,1,n,S[oper[i].pos].seg,1); 164 if(oper[i].opt==2 && oper[i].value>=M) 165 Sgt::Update(1,1,n,S[oper[i].pos].seg,-1); 166 if(oper[i].opt==3) 167 { 168 res=0; 169 Hld::Solve(oper[i].l,oper[i].r); 170 record[i] = res; 171 } 172 } 173 174 for(int i=l;i<=r;i++) 175 { 176 if(oper[i].opt==1 && oper[i].value>=M) 177 Sgt::Update(1,1,n,S[oper[i].pos].seg,-1); 178 if(oper[i].opt==2 && oper[i].value>=M) 179 Sgt::Update(1,1,n,S[oper[i].pos].seg,1); 180 } 181 182 int l_num=0,r_num=0; 183 for(int i=l;i<=r;i++) 184 { 185 if(oper[i].opt!=3) 186 { 187 if(oper[i].value >= M) 188 qR[++r_num]=oper[i]; 189 else 190 qL[++l_num]=oper[i]; 191 } 192 else 193 { 194 if(oper[i].cur + record[i] >= oper[i].k) 195 qR[++r_num]=oper[i]; 196 else 197 { 198 qL[++l_num]=oper[i]; 199 qL[l_num].cur+=record[i]; 200 } 201 } 202 } 203 204 int t=l; 205 for(int i=1;i<=l_num;i++) oper[t++]=qL[i]; 206 for(int i=1;i<=r_num;i++) oper[t++]=qR[i]; 207 208 Solve(l,l+l_num-1,L,M); 209 Solve(l+l_num,r,M+1,R); 210 } 211 212 int main() 213 { 214 n=get(); m=get(); 215 for(int i=1;i<=n;i++) 216 { 217 a[i]=get(); 218 oper[++cnt].opt=1; oper[cnt].pos=i; oper[cnt].value=a[i]; 219 } 220 221 for(int i=1;i<n;i++) 222 { 223 x=get(); y=get(); 224 Add(x,y); 225 } 226 227 Hld::First(); 228 Hld::Dfs1(1,0); Hld::Dfs2(1,0); 229 230 for(int i=1;i<=m;i++) 231 { 232 k=get(); x=get(); y=get(); 233 if(k==0) 234 { 235 oper[++cnt].opt=2; oper[cnt].pos=x; oper[cnt].value=a[x]; 236 oper[++cnt].opt=1; oper[cnt].pos=x; oper[cnt].value=y; 237 a[x]=y; 238 } 239 else 240 { 241 oper[++cnt].opt=3; oper[cnt].l=x; oper[cnt].r=y; oper[cnt].k=k; 242 oper[cnt].cnt=++Num; 243 } 244 } 245 246 Solve(1,cnt,0,INF); 247 248 for(int i=1;i<=Num;i++) 249 { 250 if(Ans[i]!=-1) printf("%d",Ans[i]); 251 else printf("invalid request!"); 252 printf("\n"); 253 } 254 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/BearChild/p/6442215.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ1146】【CTSC2008】网络管理 [整体二分]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。