[Submit][Status][Discuss] 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大的路由器的延遲時間。注意N ,Q<=80000,任意一個路由器在任何時刻都滿足延遲時間小于10^8。對于所有詢問滿足0<=K<=N 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
Sample Output 3
2
2
invalid request!
解題方法： 我真是*， 寫了一下午加一晚上的樹套樹，代碼330排，期間各種TLE+WA，各種小錯誤啊，自己真是太菜了啊，長代碼一直雪崩啊。。。樹套樹的思路還是非常簡單的， 首先將樹按鏈重新標號，然后將一段鏈給放到線段樹中取。由于求u到v的k大值，那么我們可以對于一段鏈中二分查找對于某一個值小于這個值的個數有多少個，那么我們就可以知道這個值如果恰好是第k大的就是答案所求。用線段樹的話可以將一段區間的值快速求出來 實現就是對于線段樹表示表示區間的節點，對于那一段區間我們建立一個平衡樹（我用的multitreap，用于統計大于某個值的個數有多少個），然后對于每一個二分答案，我們對于這個值在u到v的樹鏈上求小于這個值的答案有多少個就好了，直接按樹鏈剖分的方法往一端靠上去求累計和就好了。 其總的復雜度是n（logn）^4其實想想這個復雜度對于一組數據已經接近n^2了但是考慮到線段樹的區間更新，我們其實區間的查詢能大大提高效率，20s可以過。 由于我的模板太過模式化了，寫出來調得沒編譯錯誤都花了快10分鐘！
#include <bits/stdc++.h>using namespace std;const int maxn = 400010;const int maxv = 17;int n, q, edgecnt, tot, tmp;int T[maxn], Hash[maxn], f[maxn], a[maxn], b[maxn];bool vis[maxn];//===============================================================multitreapnamespace multi_treap{ struct data{ int l, r, v, size, rnd, w; }tree[5000010]; int size, root, ans; void update(int k) { tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + tree[k].w; } void rturn(int &k) { int t = tree[k].l; tree[k].l = tree[t].r; tree[t].r = k; tree[t].size = tree[k].size; update(k); k = t; } void lturn(int &k) { int t = tree[k].r; tree[k].r = tree[t].l; tree[t].l = k; tree[t].size = tree[k].size; update(k); k=t; } void insert(int &k, int x) { if(k == 0) { size++; k = size; tree[k].size = tree[k].w = 1; tree[k].v = x; tree[k].rnd = rand(); return ; } tree[k].size++; if(tree[k].v==x) tree[k].w++;//每個結點順便記錄下與該節點相同值的數的個數 else if(x > tree[k].v) { insert(tree[k].r, x); if(tree[tree[k].r].rnd < tree[k].rnd) lturn(k);//維護堆性質 } else { insert(tree[k].l, x); if(tree[tree[k].l].rnd < tree[k].rnd) rturn(k); } } void del(int &k,int x) { if(k == 0)return; if(tree[k].v == x) { if(tree[k].w > 1) { tree[k].w--; tree[k].size--; return;//若不止相同值的個數有多個，刪去一個 } if(tree[k].l * tree[k].r == 0)k = tree[k].l + tree[k].r;//有一個兒子為空 else if(tree[tree[k].l].rnd < tree[tree[k].r].rnd) rturn(k),del(k,x); else lturn(k),del(k,x); } else if(x > tree[k].v) tree[k].size--, del(tree[k].r,x); else tree[k].size--, del(tree[k].l,x); }// int query_rank(int k, int x)// {// if(k == 0) return 0;// if(tree[k].v == x) return tree[tree[k].l].size + 1;// else if(x > tree[k].v)// return tree[tree[k].l].size + tree[k].w + query_rank(tree[k].r, x);// else return query_rank(tree[k].l, x);// } void query_rank(int k, int x){ if(!k) return ; if(x == tree[k].v){ tmp += tree[tree[k].r].size; return ; } else if(x < tree[k].v){ tmp += tree[tree[k].r].size + tree[k].w; query_rank(tree[k].l, x); } else query_rank(tree[k].r, x); } int query_num(int k, int x) { if(k == 0) return 0; if(x <= tree[tree[k].l].size) return query_num(tree[k].l, x); else if(x > tree[tree[k].l].size + tree[k].w) return query_num(tree[k].r,x - tree[tree[k].l].size-tree[k].w); else return tree[k].v; }// void query_PRo(int k, int x)// {// if(k == 0)return;// if(tree[k].v < x)// {// ans = k;// query_pro(tree[k].r, x);// }// else query_pro(tree[k].l, x);// }// void query_sub(int k, int x)// {// if(k == 0)return;// if(tree[k].v > x)// {// ans = k;// query_sub(tree[k].l, x);// }// else query_sub(tree[k].r, x);// }}//==================================================================================graphint head[maxn];struct edge{ int v, nxt; edge(){} edge(int v, int nxt) : v(v), nxt(nxt) {}}E[200005];void init(){ memset(head, -1, sizeof(head)); edgecnt = 0;}void ins(int u, int v){ E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;}//===================================================================================int find(int x){ int l = 1, r = tot; while(l <= r){ int mid = (l + r) / 2; if(Hash[mid] < x) l = mid + 1; else if(Hash[mid] == x) return mid; else r = mid - 1; } return l;}//====================================================================================namespace shupou{ int dfn, fa[maxn][maxv], son[maxn], dep[maxn], belong[maxn], pl[maxn]; void dfs1(int x){ son[x] = 1; vis[x] = 1; for(int i = 1; i <= 16; i++){ if((1 << i) <= dep[x]) fa[x][i] = fa[fa[x][i-1]][i-1]; else break; } for(int i = head[x]; ~i; i = E[i].nxt){ int v = E[i].v; if(vis[v]) continue; dep[v] = dep[x] + 1; fa[v][0] = x; dfs1(v); son[x] += son[v]; } } void dfs2(int x, int chain){ dfn++; pl[x] = dfn;//分配x節點在線段樹中的編號 belong[x] = chain;//記錄鏈的頂端 int k = 0; for(int i = head[x]; ~i; i = E[i].nxt){ int v = E[i].v; if(son[v] > son[k] && dep[v] > dep[x]){ k = v; //選擇子樹最大的兒子繼承重鏈 } } if(!k) return ; dfs2(k, chain); for(int i = head[x]; ~i; i = E[i].nxt){ int v = E[i].v; if(v != k && dep[v] > dep[x]){ dfs2(v, v); } } } int lca(int x, int y){ if(dep[x] < dep[y]) swap(x, y); for(int i = 0; i <= 16; i++){ if((dep[x] - dep[y]) & (1<<i)) x = fa[x][i]; } for(int i = 16; i >= 0; i--){ if(fa[x][i] != fa[y][i]){ x = fa[x][i]; y = fa[y][i]; } } if(x == y) return x; return fa[x][0]; }}//====================================================================================segment treenamespace segmenttree{ int root[300005]; void Build(){ memset(root, 0, sizeof(root)); } void update(int pos, int x, int y, int l, int r, int o){ multi_treap::del(root[o], x); multi_treap::insert(root[o], y); if(l == r) return ; int mid = (l + r) / 2; if(pos <= mid) update(pos, x, y, l, mid, o*2); else update(pos, x, y, mid + 1, r, o*2+1); } void query(int x, int y, int num, int l, int r, int o){ if(x == l && y == r) { multi_treap::query_rank(root[o], num); return ; } int mid = (l + r) / 2; if(y <= mid) query(x, y, num, l, mid, o*2); else if(x > mid) query(x, y, num, mid + 1, r, o*2+1); else{ query(x, mid, num, l, mid, o*2); query(mid + 1, y, num, mid + 1, r, o*2 + 1); } }}//=======================================================================================void get_rank(int x, int f, int num){ while(shupou::belong[x] != shupou::belong[f]){ segmenttree::query(shupou::pl[shupou::belong[x]], shupou::pl[x], num, 1, n, 1); x = shupou::fa[shupou::belong[x]][0]; } segmenttree::query(shupou::pl[f], shupou::pl[x], num, 1, n, 1);}//=======================================================================================void work(int x, int y, int rank){ int _lca = shupou::lca(x, y); int pos = -1; tmp = 0; get_rank(y, _lca, 0); get_rank(x, _lca, 0); if(tmp - 1 < rank){ puts("invalid request!"); return ; } int l = 1, r = tot; while(l <= r){ int mid = (l + r) / 2; tmp = 0; get_rank(x, _lca, mid); get_rank(y, _lca, mid); if(T[_lca] > mid) tmp--; if(tmp <= rank - 1){ r = mid - 1; pos = mid; } else{ l = mid + 1; } } printf("%d/n", Hash[pos]);}int main(){ using namespace multi_treap; using namespace shupou; using namespace segmenttree; init(); scanf("%d", &n); scanf("%d", &q); for(int i = 1; i <= n; i++){ scanf("%d", &T[i]); Hash[++tot] = T[i]; } for(int i = 1; i < n; i++){ int u, v; scanf("%d%d", &u, &v); ins(u, v); ins(v, u); } dfs1(1); dfs2(1, 1); for(int i = 1; i <= q; i++){ scanf("%d%d%d", &f[i], &a[i], &b[i]); if(!f[i]) Hash[++tot] = b[i]; } sort(Hash + 1, Hash + 1 + tot); int top = 1; for(int i = 2; i <= tot; i++){ if(Hash[i] != Hash[i-1]){ Hash[++top] = Hash[i]; } } tot = top; for(int i = 1; i <= n; i++) T[i] = find(T[i]); for(int i = 1; i <= q; i++){ if(!f[i]){ b[i] = find(b[i]); } } for(int i = 1; i <= n; i++){ segmenttree::update(pl[i], 0, T[i], 1, n, 1); } for(int i = 1; i <= q; i++){ if(!f[i]){ segmenttree::update(pl[a[i]], T[a[i]], b[i], 1, n, 1); T[a[i]] = b[i]; } else{ work(a[i], b[i], f[i]); } } return 0;}新聞熱點
疑難解答
