這題真是十分難寫(xiě)啊 不管是點(diǎn)分治還是括號(hào)序列都有一堆細(xì)節(jié)。。

?

點(diǎn)分治：時(shí)空復(fù)雜度$O(n\log^2n)$，常數(shù)巨大

主要就是3個(gè)堆的初始狀態(tài)

C堆：每個(gè)節(jié)點(diǎn)一個(gè)，為子樹(shù)中的點(diǎn)到它父親的距離的堆。

B堆：每個(gè)節(jié)點(diǎn)一個(gè)，存所有兒子的堆的堆頂。特別地，如果該節(jié)點(diǎn)關(guān)燈，那么將加入一個(gè)0；如果沒(méi)有元素，堆頂應(yīng)返回負(fù)數(shù)。

A堆：全局一個(gè)，存所有B堆的最大值和最小值之和。特別地，如果B堆不足兩個(gè)，返回負(fù)數(shù)。

這樣，我們一開(kāi)始需要關(guān)閉所有的等，即對(duì)所有點(diǎn)調(diào)用一次turn_off。由于堆頂返回的是負(fù)數(shù)，刪除時(shí)找不到的話(huà)直接忽略即可，如果返回的是0，則有可能誤刪有用的信息。

?

代碼：

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 100000 + 10, logn = 17;
  6 
  7 struct RMQ {
  8     int n, f[logn + 1][N * 2], Log[N * 2];
  9     void init(int n) {
 10         Log[0] = -1;
 11         for(int i = 1; i <= n; i++) Log[i] = Log[i >> 1] + 1;
 12         this->n = n;
 13         for(int i = 1; (1 << i) < n; i++) {
 14             for(int j = 1; j <= n; j++) {
 15                 f[i][j] = min(f[i-1][j], f[i-1][j + (1 << (i-1))]);
 16             }
 17         }
 18     }
 19 
 20     int query(int l, int r) {
 21         int t = Log[r - l + 1];
 22         return min(f[t][l], f[t][r - (1 << t) + 1]);
 23     }
 24 } rmq;
 25 
 26 struct Edge {
 27     int to; Edge *next;
 28 } pool[N * 2], *pis = pool, *fir[N];
 29 
 30 void AddEdge(int u, int v) {
 31     pis->to = v, pis->next = fir[u], fir[u] = pis++;
 32 }
 33 
 34 int dfn[N], dfs_clock, *seq = rmq.f[0], dep[N], ds[N], tot;
 35 
 36 #define v p->to
 37 void dfs(int u, int fa) {
 38     dfn[u] = ++dfs_clock;
 39     seq[dfs_clock] = dep[u];
 40     for(Edge *p = fir[u]; p; p = p->next) {
 41         if(v != fa) {
 42             dep[v] = dep[u] + 1, dfs(v, u);
 43             seq[++dfs_clock] = dep[u];
 44         }
 45     }
 46     ds[tot++] = u;
 47 }
 48 #undef v
 49 
 50 int dis(int u, int v) {
 51     if(dfn[u] > dfn[v]) swap(u, v);
 52     return dep[u] + dep[v] - (rmq.query(dfn[u], dfn[v]) << 1);
 53 }
 54 const int INF = 1 << 29;
 55 
 56 struct Set {
 57     multiset<int> s;
 58     void insert(int x) {s.insert(x);}
 59     void erase(int x) {
 60         multiset<int>::iterator it = s.find(x);
 61         if(it != s.end()) s.erase(it);
 62     }
 63     int size() const {return s.size();}
 64     int top() {return s.empty() ? -INF : *--s.end();}
 65     int    query() {
 66         if(s.size() < 2) return -INF;
 67         return *--s.end() + *----s.end();
 68     }
 69 } A, B[N], C[N];
 70 
 71     void print(const Set &ss) {
 72         const multiset<int> &s = ss.s;
 73         for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
 74             printf("%d ", *it);
 75         }
 76         puts("");
 77     }
 78 bool centre[N];
 79 int fa[N], maxsz[N], sz[N], root;
 80 
 81 #define v p->to
 82 void dfs_size(int u, int fa) {
 83     sz[u] = 1, maxsz[u] = 0;
 84     for(Edge *p = fir[u]; p; p = p->next) {
 85         if(!centre[v] && v != fa) {
 86             dfs_size(v, u);
 87             sz[u] += sz[v];
 88             maxsz[u] = max(maxsz[u], sz[v]);
 89         }
 90     }
 91 }
 92 
 93 void dfs_root(int u, int fa, int r) {
 94     maxsz[u] = max(maxsz[u], sz[r] - sz[u]);
 95     if(maxsz[u] < maxsz[root]) root = u;
 96     for(Edge *p = fir[u]; p; p = p->next) {
 97         if(!centre[v] && v != fa) dfs_root(v, u, r);
 98     }
 99 }
100 
101 void divide(int u, int _fa) {
102     dfs_size(u, 0), dfs_root(u, 0, root = u);
103     centre[u = root] = 1, fa[u] = _fa;
104     for(Edge *p = fir[u]; p; p = p->next) {
105         if(!centre[v]) divide(v, u);
106     }
107 }
108 #undef v
109 
110 void add(int u, int v, int flag) {
111     if(u == v) {
112         A.erase(B[u].query());
113         if(flag) B[u].insert(0);
114         else B[u].erase(0);
115         A.insert(B[u].query());
116     }
117     int f = fa[u];
118     if(!f) return;
119     A.erase(B[f].query());
120     B[f].erase(C[u].top());
121     if(flag) C[u].insert(dis(f, v));
122     else C[u].erase(dis(f, v));
123     B[f].insert(C[u].top());
124     A.insert(B[f].query());
125     add(f, v, flag);
126 }
127 
128 int col[N];
129 
130 int main() {
131 #ifdef DEBUG
132     freopen("in.txt", "r", stdin);
133 #endif
134 
135     int n; scanf("%d", &n);
136     for(int i = 1; i < n; i++) {
137         int u, v; scanf("%d%d", &u, &v);
138         AddEdge(u, v), AddEdge(v, u);
139     }
140     dfs(1, 0);
141     rmq.init((n << 1) - 1);
142     divide(1, 0);
143     int cnt_off = n;
144     for(int i = 0; i < n; i++)
145         add(ds[i], ds[i], col[ds[i]] = 1);
146     
147     int m, u; scanf("%d", &m);
148     char opt[8];
149     while(m--) {
150         scanf("%s", opt);
151         if(opt[0] == 'G') {
152             if(cnt_off == 0) puts("-1");
153             else if(cnt_off == 1) puts("0");
154             else printf("%d\n", A.top());
155         } else {
156             scanf("%d", &u), add(u, u, col[u] ^= 1);
157             if(col[u]) cnt_off++; else cnt_off--;
158         }
159     }
160 
161     return 0;
162 }

點(diǎn)分治

?

括號(hào)序列：時(shí)間復(fù)雜度$O(n\log n)$,空間復(fù)雜度$O(n)$

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 100000 + 10;
  6 
  7 int col[N];
  8 const int bracket[] = {-2, -1};
  9 
 10 struct Data {
 11     /*
 12         0 : 從區(qū)間左起的
 13         [ x ] x的數(shù)量
 14 
 15         c[] 是左右括號(hào)的數(shù)量，而d[]和s[]必須保證旁邊至少有一個(gè)滿(mǎn)足條件的點(diǎn)
 16     */
 17     int c[2]; // [ )...) ] 或 [ (...( ]
 18     int d[2]; // [ )...) ] - [ (...( ] 或反過(guò)來(lái)
 19     int s[2]; // [ )...) ] + [ (...( ] 或反過(guò)來(lái) 
 20     int ans;
 21 
 22     void set(int x) {
 23         for(int i = 0; i < 2; i++) {
 24             c[i] = x == bracket[i];
 25             d[i] = s[i] = x > 0 && col[x] ? 0 : -(1 << 29);
 26             // 只有在x是滿(mǎn)足條件的點(diǎn)的時(shí)候才把d[]和s[]賦為0，否則為-INF
 27         }
 28     }
 29 };
 30 
 31 void maxit(int &x, int y) {
 32     if(x < y) x = y;
 33 }
 34 
 35 // 實(shí)際上需要討論lhs.c[1] 和 rhs.c[0]的大小
 36 // 但是不合法的一定不是最優(yōu)的，所以可以對(duì)兩種情況直接取max
 37 Data operator + (const Data &lhs, const Data &rhs) {
 38     static Data res;
 39 
 40     // update ans
 41     res.ans = max(lhs.ans, rhs.ans);
 42     maxit(res.ans, lhs.s[1] + rhs.d[0]);
 43     maxit(res.ans, lhs.d[1] + rhs.s[0]);
 44 
 45     // update s[]
 46     res.s[0] = max(lhs.s[0], rhs.s[0] - lhs.c[1] + lhs.c[0]); // lhs.c[1] >= rhs.c[0]
 47     res.s[0] = max(res.s[0], lhs.c[0] + lhs.c[1] + rhs.d[0]); // lhs.c[1] <= rhs.c[0]
 48     res.s[1] = max(rhs.s[1], lhs.s[1] - rhs.c[0] + rhs.c[1]); // rhs.c[1] >= lhs.c[0]
 49     res.s[1] = max(res.s[1], rhs.c[0] + rhs.c[1] + lhs.d[1]); // rhs.c[1] <= rhs.c[0]
 50 
 51     // update d[]
 52     res.d[0] = max(lhs.d[0], rhs.d[0] + lhs.c[1] - lhs.c[0]);
 53     res.d[1] = max(rhs.d[1], lhs.d[1] + rhs.c[0] - rhs.c[1]);
 54 
 55     // update c[] to update next s[] and d[]
 56     res.c[0] = lhs.c[0] + max(rhs.c[0] - lhs.c[1], 0);
 57     res.c[1] = rhs.c[1] + max(lhs.c[1] - rhs.c[0], 0);
 58 
 59     return res;
 60 }
 61 
 62 struct Edge {int to; Edge *next;} pool[N * 2], *pis = pool, *fir[N];
 63 void AddEdge(int u, int v) {pis->to = v, pis->next = fir[u], fir[u] = pis++;}
 64 
 65 int dfs_seq[N * 3], dfs_clock;
 66 
 67 void dfs(int u, int fa) {
 68     col[u] = 1;
 69     dfs_seq[++dfs_clock] = bracket[1];
 70     dfs_seq[++dfs_clock] = u;
 71     for(Edge *p = fir[u]; p; p = p->next) {
 72         int v = p->to;
 73         if(v != fa) dfs(v, u);
 74     }
 75     dfs_seq[++dfs_clock] = bracket[0];
 76 }
 77 
 78 int pos[N];
 79 
 80 struct SegmentTree {
 81     Data da[N * 12];
 82     void build(int s, int l, int r, int a[]) {
 83         if(l == r) {
 84             if(a[l] > 0) pos[a[l]] = s;
 85             return da[s].set(a[l]);
 86         }
 87         int mid = (l + r) >> 1;
 88         build(s << 1, l, mid, a), build(s << 1 | 1, mid + 1, r, a);
 89         da[s] = da[s << 1] + da[s << 1 | 1];
 90     }
 91 
 92     void modify(int x) {
 93         int s = pos[x]; da[s].set(x);
 94         while(s >>= 1) da[s] = da[s << 1] + da[s << 1 | 1];
 95     }
 96 } seg;
 97 
 98 int main() {
 99 #ifdef DEBUG
100     freopen("in.txt", "r", stdin);
101 #endif
102 
103     int n; scanf("%d", &n);
104     for(int i = 1; i < n; i++) {
105         int u, v; scanf("%d%d", &u, &v);
106         AddEdge(u, v), AddEdge(v, u);
107     }
108     dfs(1, 0);
109     seg.build(1, 1, n * 3, dfs_seq);
110 
111     int m; scanf("%d", &m);
112     char opt[8]; int ans, x, cnt = n;
113     while(m--) {
114         scanf("%s", opt);
115         if(opt[0] == 'G') {
116             if(cnt >= 2) ans = seg.da[1].ans;
117             else if(cnt == 1) ans = 0;
118             else ans = -1;
119             printf("%d\n", ans);
120         } else {
121             scanf("%d", &x);
122             if(col[x] ^= 1) cnt++; else cnt--;
123             seg.modify(x);
124         }
125     }
126 
127     return 0;
128 }

線(xiàn)段樹(shù) 鏈分治：時(shí)間復(fù)雜度$O(n\log^2n)$,空間復(fù)雜度$O(n)$ 比點(diǎn)分治快多啦 notice：合并兩個(gè)線(xiàn)段樹(shù)節(jié)點(diǎn)的時(shí)候如果使用=賦值可能丟失兒子信息。

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 100000 + 10, INF = 1 << 29;
  6 
  7 struct Set {
  8     multiset<int> s;
  9     void erase(int x) {assert(s.find(x) != s.end()), s.erase(s.find(x));}
 10     void insert(int x) {s.insert(x);}
 11     int top() const {return s.empty() ? -INF : *--s.end();}
 12     int query() const {
 13         if(s.size() < 2) return -INF;
 14         return *--s.end() + *----s.end();
 15     }
 16 } heap[N], st;
 17 
 18 void print(const Set &ss) {
 19     const multiset<int> &s = ss.s;
 20     for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
 21         printf("%d ", *it);
 22     }
 23     puts("");
 24 }
 25 
 26 struct Edge {
 27     int to, w;
 28     Edge *next;
 29 } pool_edges[N * 2], *fir[N], *pe = pool_edges;
 30 
 31 void AddEdge(int u, int v, int w) {
 32     pe->to = v, pe->w = w, pe->next = fir[u], fir[u] = pe++;
 33 }
 34 
 35 int sz[N], top[N], dis[N], son[N], fa[N], dfs_clock, seq[N], dfn[N], end[N], col[N];
 36 
 37 #define mid ((l + r) >> 1)
 38 struct Node {
 39     int L, R, ans;
 40     Node *ch[2];
 41 
 42     void set(int u) {
 43         ans = heap[u].query();
 44         L = R = heap[u].top();
 45     }
 46 
 47     void modify(int l, int r, int p);
 48 
 49 } pool_nodes[N * 3], *pn = pool_nodes, *rt[N];
 50 
 51 void print(Node *o, int l, int r) {
 52     printf("[%d, %d] : L = %d, R = %d, ans = %d\n", l, r, o->L, o->R, o->ans);
 53     if(l != r) print(o->ch[0], l, mid), print(o->ch[1], mid + 1, r);
 54 }
 55 void merge(Node &res, const Node &lhs, const Node &rhs, int l, int r) {
 56     res.ans = max(lhs.ans, rhs.ans);
 57     res.ans = max(res.ans, lhs.R + dis[seq[mid + 1]] - dis[seq[mid]] + rhs.L);
 58 
 59     res.L = max(lhs.L, dis[seq[mid + 1]] - dis[seq[l]] + rhs.L);
 60     res.R = max(rhs.R, dis[seq[r]] - dis[seq[mid]] + lhs.R);
 61 }
 62 
 63 void Node::modify(int l, int r, int p) {
 64     if(l == r) return set(seq[p]);
 65     if(p <= mid) ch[0]->modify(l, mid, p);
 66     else ch[1]->modify(mid + 1, r, p);
 67     merge(*this, *ch[0], *ch[1], l, r);
 68 }
 69 
 70 Node *build(int l, int r) {
 71     Node *o = pn++;
 72     if(l == r) o->set(seq[l]);
 73     else {
 74         o->ch[0] = build(l, mid);
 75         o->ch[1] = build(mid + 1, r);
 76         merge(*o, *o->ch[0], *o->ch[1], l, r);
 77     }
 78     return o;
 79 }
 80 #undef mid
 81 
 82 #define v it->to
 83 void dfs_size(int u) {
 84     sz[u] = 1, col[u] = 1;
 85     for(Edge *it = fir[u]; it; it = it->next) {
 86         if(v != fa[u]) {
 87             dis[v] = dis[u] + it->w;
 88             fa[v] = u;
 89             dfs_size(v);
 90             sz[u] += sz[v];
 91             if(sz[v] > sz[son[u]]) son[u] = v;
 92         }
 93     }
 94 }
 95 
 96 void dfs_build(int u, int pre) {
 97     seq[dfn[u] = ++dfs_clock] = u;
 98     top[u] = pre;
 99     end[pre] = max(end[pre], dfn[u]);
100     if(son[u]) dfs_build(son[u], pre);
101     for(Edge *it = fir[u]; it; it = it->next) {
102         if(v != fa[u] && v != son[u]) {
103             dfs_build(v, v);
104             heap[u].insert(rt[v]->L + dis[v] - dis[u]);
105         }
106     }
107 
108     heap[u].insert(0);
109     if(top[u] == u) {
110         rt[u] = build(dfn[u], end[u]);
111         st.insert(rt[u]->ans);
112     }
113 }
114 #undef v
115 
116 void modify(int u) { 
117     static int anc[20], tot;
118     tot = 0;
119     for(int t = u; t; t = fa[top[t]]) anc[tot++] = t;
120 
121     for(int i = tot-1; i >= 0; i--) {
122         st.erase(rt[top[anc[i]]]->ans);
123         if(i) heap[anc[i]].erase(rt[top[anc[i-1]]]->L + dis[top[anc[i-1]]] - dis[anc[i]]);
124     }
125     if(col[u]) heap[u].insert(0);
126     else heap[u].erase(0);
127 
128     for(int i = 0; i < tot; i++) {
129         int x = anc[i], t = top[x];
130         rt[t]->modify(dfn[t], end[t], dfn[x]);
131         st.insert(rt[t]->ans);
132         if(i+1 < tot) heap[anc[i+1]].insert(rt[t]->L + dis[t] - dis[anc[i+1]]);
133     }
134 }
135 
136 int main() {
137 #ifdef DEBUG
138     freopen("in.txt", "r", stdin);
139 #endif
140     int n; scanf("%d", &n);
141     for(int i = 1; i < n; i++) {
142         int u, v; scanf("%d%d", &u, &v);
143         AddEdge(u, v, 1), AddEdge(v, u, 1);
144     }
145     dfs_size(1);
146     dfs_build(1, 1);
147 
148     int m; scanf("%d", &m);
149     char opt[8]; int u, tot = n;
150     while(m--) {
151         scanf("%s", opt);
152         if(opt[0] == 'G') {
153             int ans;
154             if(tot == 0) ans = -1;
155             else if(tot == 1) ans = 0;
156             else ans = st.top();
157             printf("%d\n", ans);
158         } else {
159             scanf("%d", &u);
160             if(!(col[u] ^= 1)) tot--; else tot++;
161             modify(u);
162             
163         }
164     }
165 }

鏈分治

?

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

總結(jié)

以上是生活随笔為你收集整理的bzoj1095: [ZJOI2007]Hide 捉迷藏 线段树维护括号序列 点分治 链分治的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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