題目描述

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

輸入

第一行為兩個整數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大的路由器的延遲時間。 注意N,Q<=80000,任意一個路由器在任何時刻都滿足延遲時間小于10^8。 對于所有詢問滿足0<=K<=N

輸出

對于每一個第二種詢問（k>0），輸出一行。包含一個整數為相應的延遲時間。 如果路徑上的路由器不足k個，則輸出信息“invalidrequest!” （全部小寫不包含引號，兩個單詞之間有一個空格）。

樣例輸入

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

樣例輸出

3
2
2
invalid request! 題目要求路徑第k大，那么就要維護出路徑每個點的權值。 我們不妨在樹上每個點開一棵權值線段樹來存這個點到根路徑上每個點的權值。 查詢時將路徑以兩點LCA分成兩部分，即對于路徑(x,y)，只要將x點的線段樹+y點的線段樹-lca點的線段樹-lca父節點的線段樹就能得到路徑上點的權值。 可以發現一個點的權值被子樹內所有點上的線段樹存儲，在樹上無法修改，那么可以轉化到出棧入棧序上。 對于單點修改，在出棧入棧序上就是對于一個區間每個點的線段樹都修改，而查詢時是單點的線段樹查詢。 那么我們可以差分一下，在修改點入棧時刻加入出棧時刻刪除，這樣就變成了單點修改前綴查詢。 直接樹狀數組套權值線段樹即可。(套主席樹和套權值線段樹沒啥區別，就是套權值線段樹內存小點) 做這題之前建議先做->BZOJ1901 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; int s[80050]; int t[80050]; int num; int cnt; int tot; int a[80050]; int head[80050]; int to[160050]; int next[160050]; int sum[20000050]; int ls[20000050]; int rs[20000050]; int root[160050]; int f[80050]; int size[80010]; int top[80010]; int son[80010]; int d[80050]; int s1[80050]; int s2[80050]; int s3[80050]; int s4[80050]; int opt; int x,y; void addd(int x,int y) {tot++;next[tot]=head[x];head[x]=tot;to[tot]=y; } void dfs2(int x,int t) {top[x]=t;if(son[x]){dfs2(son[x],t);}for(int i=head[x];i;i=next[i]){if(to[i]!=f[x]&&to[i]!=son[x]){dfs2(to[i],to[i]);}} } int lca(int x,int y) {while(top[x]!=top[y]){if(d[top[x]]>d[top[y]]){swap(x,y);}y=f[top[y]];}return d[x]<d[y]?x:y; } void updata(int &rt,int l,int r,int k,int v) {if(!rt){rt=++cnt;}sum[rt]+=v;if(l==r){return ;}int mid=(l+r)>>1;if(k<=mid){updata(ls[rt],l,mid,k,v);}else{updata(rs[rt],mid+1,r,k,v);} } int query(int l,int r,int k) {if(l==r){return l;}int res=0;for(int i=1;i<=s1[0];i++){res+=sum[ls[s1[i]]];}for(int i=1;i<=s2[0];i++){res+=sum[ls[s2[i]]];}for(int i=1;i<=s3[0];i++){res-=sum[ls[s3[i]]];}for(int i=1;i<=s4[0];i++){res-=sum[ls[s4[i]]];}int mid=(l+r)>>1;if(k<=res){for(int i=1;i<=s1[0];i++){s1[i]=ls[s1[i]];}for(int i=1;i<=s2[0];i++){s2[i]=ls[s2[i]];}for(int i=1;i<=s3[0];i++){s3[i]=ls[s3[i]];}for(int i=1;i<=s4[0];i++){s4[i]=ls[s4[i]];}return query(l,mid,k);}else{for(int i=1;i<=s1[0];i++){s1[i]=rs[s1[i]];}for(int i=1;i<=s2[0];i++){s2[i]=rs[s2[i]];}for(int i=1;i<=s3[0];i++){s3[i]=rs[s3[i]];}for(int i=1;i<=s4[0];i++){s4[i]=rs[s4[i]];}return query(mid+1,r,k-res);} } void add(int k,int x,int v) {for(int i=x;i<=n;i+=i&(-i)){updata(root[i],0,100000000,k,v);} } void ask(int x,int y,int k) {s1[0]=0;s2[0]=0;s3[0]=0;s4[0]=0;int anc=lca(x,y);for(int i=s[x];i;i-=i&(-i)){s1[++s1[0]]=root[i];}for(int i=s[y];i;i-=i&(-i)){s2[++s2[0]]=root[i];}for(int i=s[anc];i;i-=i&(-i)){s3[++s3[0]]=root[i];}if(f[anc]){for(int i=s[f[anc]];i;i-=i&(-i)){s4[++s4[0]]=root[i];}}int len=d[x]+d[y]-d[anc]-d[f[anc]];if(len<k){printf("invalid request!\n");}else{printf("%d\n",query(0,100000000,len-k+1));} } void dfs(int x,int fa) {d[x]=d[fa]+1;f[x]=fa;size[x]=1;s[x]=++num;add(a[x],s[x],1);for(int i=head[x];i;i=next[i]){if(to[i]!=fa){dfs(to[i],x);size[x]+=size[to[i]];if(size[to[i]]>size[son[x]]){son[x]=to[i];}}}t[x]=num+1;add(a[x],t[x],-1); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<n;i++){scanf("%d%d",&x,&y);addd(x,y);addd(y,x);}dfs(1,0);dfs2(1,1);for(int i=1;i<=m;i++){scanf("%d%d%d",&opt,&x,&y);if(!opt){add(a[x],s[x],-1);add(a[x],t[x],1);a[x]=y;add(a[x],s[x],1);add(a[x],t[x],-1);}else{ask(x,y,opt);}} }

轉載于:https://www.cnblogs.com/Khada-Jhin/p/9513631.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ1146[CTSC2008]网络管理——出栈入栈序+树状数组套主席树的全部內容，希望文章能夠幫你解決所遇到的問題。

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