首页 > 代码库 > [题解]LCA练习+部分算法复习 2017.1.22
[题解]LCA练习+部分算法复习 2017.1.22
第一题就LCA即可。不过推荐用Tarjan(最快,常数很小)。然后Tarjan的时候顺便就出一个dist[i]，表示i节点到根节点的距离。求出了LCA，那么两点间的距离就为dist[u] + dist[v] - 2 * dist[lca]。
Code
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 #ifndef WIN32 15 #define AUTO "%I64d" 16 #else 17 #define AUTO "%lld" 18 #endif 19 using namespace std; 20 typedef bool boolean; 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 typedef class Edge { 38 public: 39 int end; 40 int next; 41 int w; 42 Edge(const int end = 0, const int next = 0, const int w = 0):end(end), next(next), w(w){ } 43 }Edge; 44 45 typedef class MapManager{ 46 public: 47 int ce; 48 Edge* edges; 49 int* h; 50 MapManager():ce(0), edges(NULL), h(NULL){ } 51 MapManager(int points, int limit):ce(0){ 52 edges = new Edge[(const int)(limit + 1)]; 53 h = new int[(const int)(points + 1)]; 54 memset(h, 0, sizeof(int) * (points + 1)); 55 } 56 inline void addEdge(int from, int end, int w){ 57 edges[++ce] = Edge(end, h[from], w); 58 h[from] = ce; 59 } 60 inline void addDoubleEdge(int from, int end, int w){ 61 addEdge(from, end, w); 62 addEdge(end, from, w); 63 } 64 Edge& operator [](int pos){ 65 return edges[pos]; 66 } 67 }MapManager; 68 #define m_begin(g, i) (g).h[(i)] 69 70 typedef class union_found{ 71 public: 72 int *f; 73 union_found():f(NULL) {} 74 union_found(int points) { 75 f = new int[(const int)(points + 1)]; 76 } 77 int find(int x) { 78 if(f[x] != x) return f[x] = find(f[x]); 79 return f[x]; 80 } 81 void unit(int fa, int so) { 82 int ffa = find(fa); 83 int fso = find(so); 84 f[fso] = ffa; 85 } 86 int& operator [](int pos){ 87 return f[pos]; 88 } 89 }union_found; 90 91 int n, m; 92 MapManager g; 93 MapManager q; 94 int *results; 95 boolean* enable; 96 int *querya, *queryb; 97 union_found uf; 98 boolean* visited; 99 int* dist;100 101 inline void init(){102 readInteger(n);103 g = MapManager(n, 2 * n);104 for(int i = 1, a, b, c; i < n; i++){105 readInteger(a);106 readInteger(b);107 readInteger(c);108 g.addDoubleEdge(a, b, c);109 }110 readInteger(m);111 q = MapManager(n, 2 * m);112 querya = new int[(const int)(m + 1)];113 queryb = new int[(const int)(m + 1)];114 results = new int[(const int)(m + 1)];115 enable = new boolean[(const int)(m + 1)];116 dist = new int[(const int)(n + 1)];117 uf = union_found(n);118 visited = new boolean[(const int)(n + 1)];119 memset(visited, false, sizeof(boolean) * (n + 1));120 memset(enable, true, sizeof(boolean) * (m + 1));121 for(int i = 1; i <= m; i++){122 readInteger(querya[i]);123 readInteger(queryb[i]);124 q.addDoubleEdge(querya[i], queryb[i], i);125 }126 dist[1] = 0;127 }128 129 void tarjan(int node, int f){130 uf[node] = node;131 visited[node] = true;132 for(int i = m_begin(g, node); i != 0; i = g[i].next){133 int& e = g[i].end;134 if(e == f) continue;135 dist[e] = dist[node] + g[i].w;136 tarjan(e, node);137 uf[e] = node;138 }139 for(int i = m_begin(q, node); i != 0; i = q[i].next) {140 int& e = q[i].end;141 if(visited[e] && enable[q[i].w]){142 int lca = uf.find(e);143 results[q[i].w] = lca;144 enable[q[i].w] = false;145 }146 }147 }148 149 inline void solve(){150 tarjan(1, 0);151 for(int i = 1; i <= m; i++){152 int dis = dist[querya[i]] + dist[queryb[i]] - 2 * dist[results[i]];153 printf("%d\n", dis);154 }155 }156 157 int main(){158 freopen("distance.in", "r", stdin);159 freopen("distance.out", "w", stdout);160 init();161 solve();162 return 0;163 }
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 #ifndef WIN32 15 #define AUTO "%I64d" 16 #else 17 #define AUTO "%lld" 18 #endif 19 using namespace std; 20 typedef bool boolean; 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 template<typename T>class Matrix{ 38 public: 39 T *p; 40 int lines; 41 int rows; 42 Matrix():p(NULL){ } 43 Matrix(int rows, int lines):lines(lines), rows(rows){ 44 p = new T[(lines * rows)]; 45 } 46 T* operator [](int pos){ 47 return (p + pos * lines); 48 } 49 }; 50 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows) 51 52 ///map template starts 53 typedef class Edge{ 54 public: 55 int end; 56 int next; 57 int w; 58 Edge(const int end = 0, const int next = 0, const int w = 0):end(end), next(next), w(w){} 59 }Edge; 60 typedef class MapManager{ 61 public: 62 int ce; 63 int *h; 64 int w; 65 Edge *edge; 66 MapManager(){} 67 MapManager(int points, int limit):ce(0){ 68 h = new int[(const int)(points + 1)]; 69 edge = new Edge[(const int)(limit + 1)]; 70 memset(h, 0, sizeof(int) * (points + 1)); 71 } 72 inline void addEdge(int from, int end, int w){ 73 edge[++ce] = Edge(end, h[from], w); 74 h[from] = ce; 75 } 76 inline void addDoubleEdge(int from, int end, int w){ 77 addEdge(from, end, w); 78 addEdge(end, from, w); 79 } 80 Edge& operator[] (int pos) { 81 return edge[pos]; 82 } 83 }MapManager; 84 #define m_begin(g, i) (g).h[(i)] 85 ///map template ends 86 87 int n, m; 88 int cnt = 0; 89 Matrix<int> st; 90 int* seq; 91 int* dep; 92 int *app; 93 MapManager g; 94 int *mlog2; 95 long long *dist; 96 97 inline void init() { 98 readInteger(n); 99 g = MapManager(n, 2 * n);100 seq = new int[(const int)(2 * n + 1)];101 dist = new long long[(const int)(n + 1)];102 dep = new int[(const int)(n + 1)];103 app = new int[(const int)(n + 1)];104 for(int i = 1, a, b, w; i < n; i++){105 readInteger(a);106 readInteger(b);107 readInteger(w);108 g.addDoubleEdge(a, b, w);109 }110 dist[1] = 0;111 dep[0] = 0;112 }113 114 void dfs(int node, int f) {115 seq[++cnt] = node;116 app[node] = cnt;117 dep[node] = dep[f] + 1;118 for(int i = m_begin(g, node); i != 0; i = g[i].next) {119 int& e = g[i].end;120 if(e == f) continue;121 dist[e] = dist[node] + g[i].w;122 dfs(e, node);123 seq[++cnt] = node;124 }125 }126 127 inline void init_log() {128 mlog2 = new int[(const int)(2 * n + 1)];129 mlog2[1] = 0;130 for(int i = 2; i <= 2 * n; i++)131 mlog2[i] = mlog2[i / 2] + 1; 132 }133 134 inline void init_st() {135 init_log();136 st = Matrix<int>(cnt, mlog2[cnt] + 1);137 for(int i = 1; i <= cnt; i++)138 st[i][0] = seq[i];139 for(int j = 1; j <= mlog2[cnt]; j++)140 for(int i = 1; i + (1 << j) - 1 <= cnt; i++)141 st[i][j] = (dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]]) ? (st[i][j - 1]) : (st[i + (1 << (j - 1))][j - 1]);142 }143 144 inline int lca(int a, int b) {145 if(app[a] > app[b]) swap(a, b);146 int pos = mlog2[app[b] - app[a] + 1];147 int u = st[app[a]][pos];148 int v = st[app[b] - (1 << pos) + 1][pos];149 return (dep[u] > dep[v]) ? (v) : (u);150 }151 152 long long dis;153 inline void solve() {154 readInteger(m);155 for(int i = 1, a, b; i <= m; i++){156 readInteger(a);157 readInteger(b);158 int l = lca(a, b);159 dis = dist[a] + dist[b] - 2 * dist[l];160 printf(AUTO"\n", dis);161 }162 }163 164 int main() {165 freopen("distance.in", "r", stdin);166 freopen("distance.out", "w", stdout);167 init();168 dfs(1, 0);169 init_st();170 solve();171 return 0;172 }
话说ST表在n，q都尽量大的情况下，其他数据随机，竟然平均一个点比Tarjan 0.05s左右。（也有可能是我的st表写得比较丑）
第二题还是一遍dfs序，接着可以开开心心地放线段树去装逼了。(然而我把某些"+="写成了"="，于是AK又没有了。。一定是写这道题和检查的时候头脑都不清醒)
Code
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 #ifdef WIN32 15 #define AUTO "%I64d" 16 #else 17 #define AUTO "%lld" 18 #endif 19 using namespace std; 20 typedef bool boolean; 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 typedef class Edge { 38 public: 39 int end; 40 int next; 41 Edge(const int end = 0, const int next = 0):end(end), next(next){ } 42 }Edge; 43 44 typedef class MapManager{ 45 public: 46 int ce; 47 Edge* edges; 48 int* h; 49 MapManager():ce(0), edges(NULL), h(NULL){ } 50 MapManager(int points, int limit):ce(0){ 51 edges = new Edge[(const int)(limit + 1)]; 52 h = new int[(const int)(points + 1)]; 53 memset(h, 0, sizeof(int) * (points + 1)); 54 } 55 inline void addEdge(int from, int end){ 56 edges[++ce] = Edge(end, h[from]); 57 h[from] = ce; 58 } 59 inline void addDoubleEdge(int from, int end){ 60 addEdge(from, end); 61 addEdge(end, from); 62 } 63 Edge& operator [](int pos){ 64 return edges[pos]; 65 } 66 }MapManager; 67 #define m_begin(g, i) (g).h[(i)] 68 69 typedef class SegTreeNode{ 70 public: 71 long long sum; 72 int l, r; 73 SegTreeNode *left, *right; 74 long long lazy; 75 SegTreeNode(int l, int r):l(l), r(r), sum(0), lazy(0), left(NULL), right(NULL){ } 76 77 inline void pushUp(){ 78 this->sum = left->sum + right->sum; 79 } 80 81 inline void pushDown(){ 82 left->lazy += lazy; 83 right->lazy += lazy; 84 left->sum += lazy * (left->r - left->l + 1); 85 right->sum += lazy * (right->r - right->l + 1); 86 lazy = 0; 87 } 88 }SegTreeNode; 89 90 typedef class SegTree { 91 public: 92 SegTreeNode* root; 93 SegTree():root(NULL){ } 94 SegTree(int size) { 95 build(root, 1, size); 96 } 97 98 void build(SegTreeNode*& node, int l, int r){ 99 node = new SegTreeNode(l, r);100 if(l == r) return;101 int mid = (l + r) >> 1;102 build(node->left, l, mid);103 build(node->right, mid + 1, r);104 }105 106 void update(SegTreeNode*& node, int l, int r, int from, int end, long long val){107 if(l == from && r == end){108 node->sum += val * (r - l + 1);109 node->lazy += val;110 return;111 }112 if(node->lazy) node->pushDown();113 int mid = (l + r) >> 1;114 if(end <= mid) update(node->left, l, mid, from, end, val);115 else if(from > mid) update(node->right, mid + 1, r, from, end, val);116 else{117 update(node->left, l, mid, from, mid, val);118 update(node->right, mid + 1, r, mid + 1, end, val);119 }120 node->pushUp();121 }122 123 long long query(SegTreeNode*& node, int index){124 if(node->l == index && node->r == index){125 return node->sum;126 }127 if(node->lazy) node->pushDown();128 int mid = (node->l + node->r) >> 1;129 if(index <= mid) return query(node->left, index);130 return query(node->right, index);131 }132 133 long long query(SegTreeNode*& node, int from, int end){134 if(node->l == from && node->r == end){135 return node->sum;136 }137 if(node->lazy) node->pushDown();138 int mid = (node->l + node->r) >> 1;139 if(end <= mid) return query(node->left, from, end);140 if(from > mid) return query(node->right, from, end);141 return query(node->left, from, mid) + query(node->right, mid + 1, end);142 }143 }SegTree;144 145 int n, m;146 SegTree st;147 int cnt = 0;148 int* visitID;149 int* exitID;150 MapManager g;151 152 inline void init() {153 readInteger(n);154 g = MapManager(n, 2 * n);155 for(int i = 1, a, b; i < n; i++){156 readInteger(a);157 readInteger(b);158 g.addDoubleEdge(a, b);159 }160 visitID = new int[(const int)(n + 1)];161 exitID = new int[(const int)(n + 1)];162 }163 164 void dfs(int node, int last){165 visitID[node] = ++cnt;166 for(int i = m_begin(g, node); i != 0; i = g[i].next) {167 int& e = g[i].end;168 if(e == last) continue;169 dfs(e, node);170 }171 exitID[node] = cnt;172 }173 174 inline void solve() {175 dfs(1, 0);176 readInteger(m);177 st = SegTree(n);178 char cmd[10];179 int a, b;180 while(m--) {181 scanf("%s", cmd);182 readInteger(a);183 if(cmd[0] == ‘g‘) {184 readInteger(b);185 st.update(st.root, 1, n, visitID[a], exitID[a], b);186 }else if(cmd[0] == ‘s‘){187 long long res = st.query(st.root, visitID[a]);188 printf(AUTO"\n", res);189 }else if(cmd[0] == ‘a‘){190 long long res = st.query(st.root, visitID[a], exitID[a]);191 printf(AUTO"\n", res);192 }193 }194 }195 196 int main() {197 freopen("redpacket.in", "r", stdin);198 freopen("redpacket.out", "w", stdout);199 init();200 solve();201 return 0;202 }
一看就发现是专为值域线段树设置的裸题(不然就只能用平衡树来做)。
Code
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 #ifndef WIN32 15 #define AUTO "%I64d" 16 #else 17 #define AUTO "%lld" 18 #endif 19 using namespace std; 20 typedef bool boolean; 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 typedef class SegTreeNode { 38 public: 39 int s; 40 SegTreeNode* left, *right; 41 42 inline void pushUp(){ 43 s = left->s + right->s; 44 } 45 }SegTreeNode; 46 47 typedef class SegTree { 48 public: 49 int lb, rb; 50 SegTreeNode* root; 51 SegTree():root(NULL) { } 52 SegTree(int lb, int rb, int* list):lb(lb), rb(rb){ 53 build(root, 1, rb - lb + 1, list); 54 } 55 56 void build(SegTreeNode*& node, int l, int r, int* list){ 57 node = new SegTreeNode(); 58 if(l == r){ 59 node->s = list[l]; 60 return; 61 } 62 int mid = (l + r) >> 1; 63 build(node->left, l, mid, list); 64 build(node->right, mid + 1, r, list); 65 node->pushUp(); 66 } 67 68 void update(SegTreeNode*& node, int l, int r, int index, int val){ 69 if(l == index && r == index){ 70 node->s += val; 71 smax(node->s, 0); 72 return; 73 } 74 int mid = (l + r) >> 1; 75 if(index <= mid) update(node->left, l, mid, index, val); 76 else update(node->right, mid + 1, r, index, val); 77 node->pushUp(); 78 } 79 80 int findKth(SegTreeNode*& node, int l, int r, int k){ 81 if(l == r) return l + lb - 1; 82 int ls = node->left->s; 83 int mid = (l + r) >> 1; 84 if(k <= ls) return findKth(node->left, l, mid, k); 85 return findKth(node->right, mid + 1, r, k - ls); 86 } 87 }SegTree; 88 89 int n; 90 int lb, rb; 91 int* list; 92 SegTree st; 93 inline void init() { 94 readInteger(lb); 95 readInteger(rb); 96 list = new int[(const int)(rb - lb + 2)]; 97 for(int i = lb; i <= rb; i++){ 98 readInteger(list[i - lb + 1]); 99 }100 st = SegTree(lb, rb, list);101 }102 103 inline void solve() {104 const int L = rb - lb + 1;105 readInteger(n);106 char cmd[10];107 int a;108 while(n--) {109 scanf("%s", cmd);110 readInteger(a);111 if(cmd[0] == ‘a‘){112 st.update(st.root, 1, L, a - lb + 1, 1);113 }else if(cmd[0] == ‘d‘){114 st.update(st.root, 1, L, a - lb + 1, -1);115 }else{116 int res = st.findKth(st.root, 1, L, a);117 printf("%d\n", res);118 }119 }120 }121 122 int main(){123 freopen("kth.in", "r", stdin);124 freopen("kth.out", "w", stdout);125 init();126 solve();127 return 0;128 }
然后我还用了替罪羊树(然而发现，都快成普通的二叉搜索树了)，O(n)离线建完整棵树，插入删除都不需要重构，即使为count为0也不管(删掉它需要花费更过的时间)。不过测了后发现，略微比值域线段树快一点，应该是因为各种操作在中途完成就开始返回了。
Code
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 #ifndef WIN32 15 #define AUTO "%I64d" 16 #else 17 #define AUTO "%lld" 18 #endif 19 using namespace std; 20 typedef bool boolean; 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 template<typename T> 38 class ScapegoatTreeNode { 39 public: 40 T val; 41 int count; 42 int size; 43 ScapegoatTreeNode* next[2]; 44 ScapegoatTreeNode():count(1), size(1){ 45 memset(next, 0, sizeof(next)); 46 } 47 ScapegoatTreeNode(T val):val(val), count(1), size(1){ 48 memset(next, 0, sizeof(next)); 49 } 50 51 inline void maintain() { 52 size = count; 53 for(int i = 0; i < 2; i++) 54 if(next[i] != NULL) 55 size += next[i]->size; 56 } 57 58 inline void addCount(int c){ 59 if(count == 0 && c < 0) return; 60 size += c, count += c; 61 } 62 63 inline int cmp(T x){ 64 if(val == x) return -1; 65 return (x < val) ? (0) : (1); 66 } 67 }; 68 69 template<typename T> 70 class ScapegoatTree { 71 protected: 72 static void insert(ScapegoatTreeNode<T>*& node, T val){ 73 if(node == NULL){ 74 node = new ScapegoatTreeNode<T>(val); 75 return; 76 } 77 int d = node->cmp(val); 78 if(d == -1){ 79 node->addCount(1); 80 return; 81 } 82 insert(node->next[d], val); 83 node->maintain(); 84 } 85 86 static boolean remove(ScapegoatTreeNode<T>*& node, T val){ 87 if(node == NULL) return false; 88 int d = node->cmp(val); 89 if(d == -1){ 90 node->addCount(-1); 91 return true; 92 } 93 boolean res = remove(node->next[d], val); 94 if(res) node->maintain(); 95 return res; 96 } 97 98 static ScapegoatTreeNode<T>* findKth(ScapegoatTreeNode<T>*& node, int k){ 99 int ls = (node->next[0] == NULL) ? (0) : (node->next[0]->size);100 if(k >= ls + 1 && k <= ls + node->count) return node;101 if(k <= ls) return findKth(node->next[0], k);102 return findKth(node->next[1], k - ls - node->count);103 }104 public:105 ScapegoatTreeNode<T>* root;106 vector<ScapegoatTreeNode<T>*> lis;107 108 ScapegoatTree():root(NULL){ }109 110 ScapegoatTreeNode<T>* rebuild(int l, int r){111 if(l > r) return NULL;112 int mid = (l + r) >> 1;113 ScapegoatTreeNode<T>*& node = lis[mid];114 node->next[0] = rebuild(l, mid - 1);115 node->next[1] = rebuild(mid + 1, r);116 node->maintain();117 return node;118 }119 120 void rebuild(ScapegoatTreeNode<T>*& node, ScapegoatTreeNode<T>*& f){121 lis.clear();122 travel(node);123 int d = -1;124 if(f != NULL) d = f->cmp(node->val);125 ScapegoatTreeNode<T>* res = rebuild(0, lis.size() - 1);126 if(d != -1) f->next[d] = res;127 else root = res;128 }129 130 void insert(T val){131 insert(root, val);132 }133 134 void remove(T val){135 remove(root, val);136 }137 138 ScapegoatTreeNode<T>* findKth(int k){139 return findKth(root, k);140 }141 };142 143 int n;144 int lb, rb;145 ScapegoatTree<int> s;146 147 inline void init() {148 readInteger(lb);149 readInteger(rb);150 for(int i = lb; i <= rb; i++){151 ScapegoatTreeNode<int>* node = new ScapegoatTreeNode<int>(i);152 readInteger(node->count);153 node->maintain();154 s.lis.push_back(node);155 }156 s.root = s.rebuild(0, s.lis.size() - 1);157 }158 159 inline void solve() {160 readInteger(n);161 char cmd[10];162 int a;163 while(n--) {164 scanf("%s", cmd);165 readInteger(a);166 if(cmd[0] == ‘a‘){167 s.insert(a);168 }else if(cmd[0] == ‘d‘){169 s.remove(a);170 }else{171 ScapegoatTreeNode<int>* node = s.findKth(a);172 printf("%d\n", node->val);173 }174 }175 }176 177 int main(){178 freopen("kth.in", "r", stdin);179 freopen("kth.out", "w", stdout);180 init();181 solve();182 return 0;183 }
[题解]LCA练习+部分算法复习 2017.1.22
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。