樹鏈剖分完就成了一道主席樹裸題了, 每次樹鏈剖分找出相應區間然后用BIT+(可持久化)權值線段樹就可以完成計數. 但是空間問題很嚴重....在修改時不必要的就不要新建, 直接修改原來的..詳見代碼. 時間復雜度O(N*log^3(N))

----------------------------------------------------------------------------

#include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>using namespace std;#define h(v) (lower_bound(H, H + n, v) - H + 1)const int maxn = 80009;inline int read() {char c = getchar();for(; !isdigit(c); c = getchar());int ret = 0;for(; isdigit(c); c = getchar())ret = ret * 10 + c - '0';return ret;}int N, Q, w[maxn], seq[maxn], H[maxn << 1], n;int top[maxn], fa[maxn], sz[maxn], ch[maxn], dep[maxn], Top;int Id[maxn], Idn;struct edge {int to;edge* next;} E[maxn << 1], *Pt = E, *head[maxn];inline void AddEdge(int u, int v) {Pt->to = v;Pt->next = head[u];head[u] = Pt++;}struct O {int t, a, b;inline void Read() {t = read(), a = read() - 1, b = read();if(t) b--;}} o[maxn];void Init() {N = read(), Q = read();for(n = 0; n < N; n++)H[n] = w[n] = read();for(int i = 1; i < N; i++) {int u = read() - 1, v = read() - 1;AddEdge(u, v);AddEdge(v, u);}for(int i = 0; i < Q; i++) {o[i].Read();if(!o[i].t)H[n++] = o[i].b;}sort(H, H + n);n = unique(H, H + n) - H;}struct Node {Node *lc, *rc;int v;Node() : v(0) {}} pool[5000000], *pt, *Null, *Root[maxn], *V[maxn];void Init_sgt() {pt = pool;Null = pt++;Null->lc = Null->rc = Null;Null->v = 0;}int Pos, Val;Node* Modify(Node* t, int l, int r) {if(t->v + Val == 0)return Null;if(t->v == Val) {?if(l == r) return t;int m = (l + r) >> 1;if(Pos <= m) {t->lc = Modify(t->lc, l, m);t->rc = Null;} else {t->lc = Null;t->rc = Modify(t->rc, m + 1, r);}return t;} else {Node* o = pt++;o->v = t->v + Val;int m = (l + r) >> 1;if(Pos <= m) {o->lc = Modify(t->lc, l, m);o->rc = t->rc;} else {o->lc = t->lc;o->rc = Modify(t->rc, m + 1, r);}return o;}}Node* Add(Node* t, int l, int r) {Node* o = pt++;o->v = t->v + Val;if(l != r) {int m = (l + r) >> 1;if(Pos <= m) {o->lc = Add(t->lc, l, m);o->rc = t->rc;} else {o->lc = t->lc;o->rc = Add(t->rc, m + 1, r);}}return o;}void DFS(int x) {sz[x] = 1;ch[x] = -1;for(edge* e = head[x]; e; e = e->next) if(e->to != fa[x]) {dep[e->to] = dep[x] + 1;fa[e->to] = x;DFS(e->to);sz[x] += sz[e->to];if(ch[x] == -1 || sz[ch[x]] < sz[e->to])ch[x] = e->to;}}void dfs(int x) {seq[Id[x] = ++Idn] = x;top[x] = Top;if(~ch[x]) dfs(ch[x]);for(edge* e = head[x]; e; e = e->next)if(e->to != fa[x] && e->to != ch[x]) dfs(Top = e->to);}void Init_slpf() {fa[0] = -1;dep[0] = 0;DFS(0);Idn = 0;dfs(0);}void Build() {Init_sgt();Root[0] = V[0] = Null;Val = 1;for(int i = 1; i <= N; i++) {Pos = h(w[seq[i]]);Root[i] = Add(Root[i - 1], 1, n);V[i] = Null;}}Node *L[500], *R[500];void Work() {int Ln, Rn;for(int i = 0; i < Q; i++) {if(o[i].t) {int x = o[i].a, y = o[i].b, size = 0;Ln = Rn = 0;for(; top[x] != top[y]; x = fa[top[x]]) {if(dep[top[x]] < dep[top[y]]) swap(x, y);size += dep[x] - dep[top[x]] + 1;L[Ln++] = Root[Id[top[x]] - 1];R[Rn++] = Root[Id[x]];for(int l = Id[top[x]] - 1; l; l -= l & -l)L[Ln++] = V[l];for(int r = Id[x]; r; r -= r & -r)R[Rn++] = V[r];}if(dep[x] > dep[y]) swap(x, y);size += dep[y] - dep[x] + 1;L[Ln++] = Root[Id[x] - 1];R[Rn++] = Root[Id[y]];for(int l = Id[x] - 1; l; l -= l & -l)L[Ln++] = V[l];for(int r = Id[y]; r; r -= r & -r)R[Rn++] = V[r];if(size < o[i].t) {puts("invalid request!");continue;} else?o[i].t = size - o[i].t + 1;int l = 1, r = n;while(l < r) {int m = (l + r) >> 1, cnt = 0;for(int j = 0; j < Ln; j++)cnt -= L[j]->lc->v;for(int j = 0; j < Rn; j++)cnt += R[j]->lc->v;if(cnt >= o[i].t) {for(int j = 0; j < Ln; j++)L[j] = L[j]->lc;for(int j = 0; j < Rn; j++)R[j] = R[j]->lc;r = m;} else {o[i].t -= cnt;for(int j = 0; j < Ln; j++)L[j] = L[j]->rc;for(int j = 0; j < Rn; j++)R[j] = R[j]->rc;l = m + 1;}}printf("%d\n", H[l - 1]);} else {Pos = h(w[seq[Id[o[i].a]]]), Val = -1;for(int x = Id[o[i].a]; x <= N; x += x & -x)V[x] = Add(V[x], 1, n);Pos = h(w[seq[Id[o[i].a]]] = o[i].b), Val = 1;for(int x = Id[o[i].a]; x <= N; x += x & -x)V[x] = Add(V[x], 1, n);}}}int main() {Init();Init_slpf();Build();Work();return 0;}

?

----------------------------------------------------------------------------

1146: [CTSC2008]網絡管理Network

Time Limit:?50 Sec??Memory Limit:?162 MB
Submit:?2943??Solved:?859
[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大的路由器的延遲時間。注意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

Sample Output

3
2
2
invalid request!

HINT

10% 測試數據滿足N<=8000,Q<=3000,
40% 測試數據滿足所有詢問中1<=K<=5 。即路由器的延遲時間不會發生變化。

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

Source

?

轉載于:https://www.cnblogs.com/JSZX11556/p/5128213.html

總結

以上是生活随笔為你收集整理的BZOJ 1146: [CTSC2008]网络管理Network( 树链剖分 + 树状数组套主席树 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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