题意：链上带修第k大。
这毒瘤题。。。别看题意只有7个字，能把我吊打死。。。
介绍其中两种做法好了。其实思想上是一样的。
对于每一个点，建立权值线段树，维护它到根路径上的所有权值。
一条路径上的点集就是x + y - z - fa z，此处z是lca x y
这样查询就可以轻易做到了。怎么建出来呢？
考虑每个点都要在它的子树中插入。那么我们搞出DFS序来，子树就是上面的一段区间。
我们就要对于这个DFS序，支持区间加（插入），单点求值。很容易想到树状数组+差分。
那么我们就用树状数组维护差分后的值域线段树，这样就是单点修改和区间求和了。
也就是树状数组套线段树...
具体实现上，查询操作有点小技巧。因为要同时查4个位置然后加加减减，每个位置又会涉及查询log棵线段树，所以就用一个now i来维护i版本的线段树当前走到的节点，用一个栈来存要用到的线段树以便更新。
然后修改操作嘛，就是删除之前的再加上新的。
时间复杂度nlog2n。
1 #include2 #include 3 4 const int N = 100010, lm = 1e8, M = 22000010; 5 6 struct Edge { 7 int nex, v; 8 }edge[N << 1]; int top; 9 10 int e[N], p[N], num, val[N], pos[N], n, ed[N], fa[N][20], tot, pw[N], d[N], rt[N], now[N], tp; 11 int sum[M], ls[M], rs[M]; 12 bool vis[N]; 13 14 inline void add(int x, int y) { 15 top++; 16 edge[top].v = y; 17 edge[top].nex = e[x]; 18 e[x] = top; 19 return; 20 } 21 22 void DFS(int x, int f) { 23 fa[x][0] = f; 24 d[x] = d[f] + 1; 25 pos[x] = ++num; 26 for(int i = e[x]; i; i = edge[i].nex) { 27 int y = edge[i].v; 28 if(y != f) { 29 DFS(y, x); 30 } 31 } 32 ed[x] = num; 33 return; 34 } 35 36 void Add(int p, int v, int l, int r, int &o) { 37 if(!o) { 38 o = ++tot; 39 } 40 if(l == r) { 41 sum[o] += v; 42 return; 43 } 44 int mid = (l + r) >> 1; 45 if(p <= mid) { 46 Add(p, v, l, mid, ls[o]); 47 } 48 else { 49 Add(p, v, mid + 1, r, rs[o]); 50 } 51 sum[o] = sum[ls[o]] + sum[rs[o]]; 52 return; 53 } 54 55 inline void insert(int id, int p, int v) { 56 for(int i = id; i <= num; i += (i & (-i))) { 57 Add(p, v, 1, lm, rt[i]); 58 } 59 return; 60 } 61 62 inline int lca(int x, int y) { 63 if(d[x] > d[y]) { 64 std::swap(x, y); 65 } 66 int t = pw[n]; 67 while(t >= 0 && d[y] > d[x]) { 68 if(d[fa[y][t]] >= d[x]) { 69 y = fa[y][t]; 70 } 71 t--; 72 } 73 if(x == y) { 74 return x; 75 } 76 t = pw[n]; 77 while(t >= 0 && fa[x][0] != fa[y][0]) { 78 if(fa[x][t] != fa[y][t]) { 79 x = fa[x][t]; 80 y = fa[y][t]; 81 } 82 t--; 83 } 84 return fa[x][0]; 85 } 86 87 inline int ask(int k, int x, int y) { 88 int z = lca(x, y); 89 if(d[x] + d[y] - 2 * d[z] + 1 < k) { 90 return -1; 91 } 92 // x + y - z - fa[z] 93 int w = fa[z][0]; 94 x = pos[x], y = pos[y], z = pos[z], w = pos[w]; 95 for(int i = x; i >= 1; i -= (i & (-i))) { 96 if(!vis[i]) { 97 vis[i] = 1; 98 p[++tp] = i; 99 now[i] = rt[i];100 }101 }102 for(int i = y; i >= 1; i -= (i & (-i))) {103 if(!vis[i]) {104 vis[i] = 1;105 p[++tp] = i;106 now[i] = rt[i];107 }108 }109 for(int i = z; i >= 1; i -= (i & (-i))) {110 if(!vis[i]) {111 vis[i] = 1;112 p[++tp] = i;113 now[i] = rt[i];114 }115 }116 for(int i = w; i >= 1; i -= (i & (-i))) {117 if(!vis[i]) {118 vis[i] = 1;119 p[++tp] = i;120 now[i] = rt[i];121 }122 }123 //124 int l = 1, r = lm;125 while(l < r) {126 int mid = (l + r) >> 1, s = 0;127 for(int i = x; i >= 1; i -= i & (-i)) {128 s += sum[rs[now[i]]];129 }130 for(int i = y; i >= 1; i -= i & (-i)) {131 s += sum[rs[now[i]]];132 }133 for(int i = z; i >= 1; i -= i & (-i)) {134 s -= sum[rs[now[i]]];135 }136 for(int i = w; i >= 1; i -= i & (-i)) {137 s -= sum[rs[now[i]]];138 }139 if(k <= s) { // rs140 for(int i = 1; i <= tp; i++) {141 now[p[i]] = rs[now[p[i]]];142 }143 l = mid + 1;144 }145 else { // ls146 k -= s;147 for(int i = 1; i <= tp; i++) {148 now[p[i]] = ls[now[p[i]]];149 }150 r = mid;151 }152 }153 for(int i = 1; i <= tp; i++) {154 vis[p[i]] = 0;155 }156 tp = 0;157 return r;158 }159 160 inline void init() {161 for(int i = 2; i <= n; i++) {162 pw[i] = pw[i >> 1] + 1;163 }164 for(int j = 1; j <= pw[n]; j++) {165 for(int i = 1; i <= n; i++) {166 fa[i][j] = fa[fa[i][j - 1]][j - 1];167 }168 }169 return;170 }171 172 int main() {173 int q;174 scanf("%d%d", &n, &q);175 for(int i = 1; i <= n; i++) {176 scanf("%d", &val[i]);177 }178 for(int i = 1, x, y; i < n; i++) {179 scanf("%d%d", &x, &y);180 add(x, y);181 add(y, x);182 }183 // prework184 185 DFS(1, 0);186 init();187 for(int i = 1; i <= n; i++) {188 // [pos[i], ed[i]] insert val[i] 1189 insert(pos[i], val[i], 1);190 insert(ed[i] + 1, val[i], -1);191 }192 193 for(int i = 1, f, x, y; i <= q; i++) {194 scanf("%d%d%d", &f, &x, &y);195 if(f == 0) { // change val[x] = y196 // [pos[x] ed[x]] insert val[x]197 insert(pos[x], val[x], -1);198 insert(ed[x] + 1, val[x], 1);199 insert(pos[x], y, 1);200 insert(ed[x] + 1, y, -1);201 val[x] = y;202 }203 else { /// ask fth204 int t = ask(f, x, y);205 if(t == -1) {206 puts("invalid request!");207 }208 else {209 printf("%d\n", t);210 }211 }212 }213 return 0;214 }
接下来是线段树套线段树的写法。
离散化之后外层值域线段树，内层线段树每个点按照DFS序维护，该点到根的路径上，有多少点的权值在外层树这个范围内。
查询的时候也是值域线段树上二分。利用lca转化成4个内层线段树单点求值再加加减减。
建树的时候，每个点要在外层树上从上往下log个内层树中插入。内层树中要在它的子树插入，又是一段区间。
修改就是跟建树差不多的操作，删去旧的再加上新的。
开了O2还慢的飞起...好歹是过了。
时间复杂度同上。
1 // luogu-judger-enable-o2 2 #include3 #include 4 5 const int N = 80010, M = 30000010; 6 7 struct Node { 8 int f, x, y; 9 }node[N]; 10 11 struct Edge { 12 int nex, v; 13 }edge[N << 1]; int top; 14 15 int e[N], n, num, tot, pw[N], pos[N], ed[N], fa[N][20], d[N], rt[N << 2], temp, val[N], X[N << 1]; 16 int tag[M], ls[M], rs[M], sum[M]; 17 18 inline void add(int x, int y) { 19 top++; 20 edge[top].v = y; 21 edge[top].nex = e[x]; 22 e[x] = top; 23 return; 24 } 25 26 inline void pushdown(int l, int r, int o) { 27 if(!tag[o]) { 28 return; 29 } 30 if(!ls[o]) { 31 ls[o] = ++tot; 32 } 33 if(!rs[o]) { 34 rs[o] = ++tot; 35 } 36 tag[ls[o]] += tag[o]; 37 tag[rs[o]] += tag[o]; 38 int mid = (l + r) >> 1; 39 sum[ls[o]] += tag[o] * (mid - l + 1); 40 sum[rs[o]] += tag[o] * (r - mid); 41 tag[o] = 0; 42 return; 43 } 44 45 void DFS(int x, int f) { 46 fa[x][0] = f; 47 d[x] = d[f] + 1; 48 pos[x] = ++num; 49 for(int i = e[x]; i; i = edge[i].nex) { 50 int y = edge[i].v; 51 if(y != f) { 52 DFS(y, x); 53 } 54 } 55 ed[x] = num; 56 return; 57 } 58 59 inline void init() { 60 for(int i = 2; i <= n; i++) { 61 pw[i] = pw[i >> 1] + 1; 62 } 63 for(int j = 1; j <= pw[n]; j++) { 64 for(int i = 1; i <= n; i++) { 65 fa[i][j] = fa[fa[i][j - 1]][j - 1]; 66 } 67 } 68 return; 69 } 70 71 inline int lca(int x, int y) { 72 if(d[x] > d[y]) { 73 std::swap(x, y); 74 } 75 int t = pw[n]; 76 while(t >= 0 && d[y] > d[x]) { 77 if(d[fa[y][t]] >= d[x]) { 78 y = fa[y][t]; 79 } 80 t--; 81 } 82 if(x == y) { 83 return x; 84 } 85 t = pw[n]; 86 while(t >= 0 && fa[x][0] != fa[y][0]) { 87 if(fa[x][t] != fa[y][t]) { 88 x = fa[x][t]; 89 y = fa[y][t]; 90 } 91 t--; 92 } 93 return fa[x][0]; 94 } 95 96 void Add(int L, int R, int v, int l, int r, int &o) { 97 //printf("add : %d %d %d %d %d %d \n", L, R, v, l, r, o); 98 if(!o) { 99 o = ++tot;100 }101 if(L <= l && r <= R) {102 tag[o] += v;103 sum[o] += (r - l + 1) * v;104 return;105 }106 pushdown(l, r, o);107 int mid = (l + r) >> 1;108 if(L <= mid) {109 Add(L, R, v, l, mid, ls[o]);110 }111 if(mid < R) {112 Add(L, R, v, mid + 1, r, rs[o]);113 }114 sum[o] = sum[ls[o]] + sum[rs[o]];115 return;116 }117 118 void insert(int L, int R, int v, int p, int l, int r, int o) {119 //printf("insert val [%d %d] \n", l, r);120 Add(L, R, v, 1, n, rt[o]);121 if(l == r) {122 return;123 }124 int mid = (l + r) >> 1;125 if(p <= mid) {126 insert(L, R, v, p, l, mid, o << 1);127 }128 else {129 insert(L, R, v, p, mid + 1, r, o << 1 | 1);130 }131 return;132 }133 134 int getSum(int p, int l, int r, int o) {135 if(!o) {136 return 0;137 }138 if(l == r) {139 return sum[o];140 }141 int mid = (l + r) >> 1;142 pushdown(l, r, o);143 if(p <= mid) {144 return getSum(p, l, mid, ls[o]);145 }146 else {147 return getSum(p, mid + 1, r, rs[o]);148 }149 }150 151 int Ask(int k, int x, int y, int z, int w, int l, int r, int o) {152 if(l == r) {153 return r;154 }155 int s = 0;156 s += getSum(x, 1, n, rt[o << 1 | 1]);157 s += getSum(y, 1, n, rt[o << 1 | 1]);158 s -= getSum(z, 1, n, rt[o << 1 | 1]);159 if(w) {160 s -= getSum(w, 1, n, rt[o << 1 | 1]);161 }162 int mid = (l + r) >> 1;163 if(k <= s) {164 return Ask(k, x, y, z, w, mid + 1, r, o << 1 | 1);165 }166 else {167 k -= s;168 return Ask(k, x, y, z, w, l, mid, o << 1);169 }170 }171 172 inline int ask(int k, int x, int y) {173 int z = lca(x, y);174 if(d[x] + d[y] - d[z] * 2 + 1 < k) {175 return -1;176 }177 int w = fa[z][0];178 x = pos[x];179 y = pos[y];180 z = pos[z];181 w = pos[w];182 return Ask(k, x, y, z, w, 1, temp, 1);183 }184 185 int main() {186 int q;187 scanf("%d%d", &n, &q);188 for(int i = 1; i <= n; i++) {189 scanf("%d", &val[i]);190 X[++temp] = val[i];191 }192 for(int i = 1, x, y; i < n; i++) {193 scanf("%d%d", &x, &y);194 add(x, y);195 add(y, x);196 }197 for(int i = 1; i <= q; i++) {198 scanf("%d%d%d", &node[i].f, &node[i].x, &node[i].y);199 if(node[i].f == 0) {200 X[++temp] = node[i].y;201 }202 }203 // prework204 std::sort(X + 1, X + temp + 1);205 temp = std::unique(X + 1, X + temp + 1) - X - 1;206 for(int i = 1; i <= n; i++) {207 val[i] = std::lower_bound(X + 1, X + temp + 1, val[i]) - X;208 }209 for(int i = 1; i <= q; i++) {210 if(node[i].f == 0) {211 node[i].y = std::lower_bound(X + 1, X + temp + 1, node[i].y) - X;212 }213 }214 215 DFS(1, 0);216 init();217 for(int i = 1; i <= n; i++) {218 insert(pos[i], ed[i], 1, val[i], 1, temp, 1);219 }220 for(int i = 1, f, x, y; i <= q; i++) {221 f = node[i].f;222 x = node[i].x;223 y = node[i].y;224 if(f == 0) { // change225 insert(pos[x], ed[x], -1, val[x], 1, temp, 1);226 insert(pos[x], ed[x], 1, y, 1, temp, 1);227 val[x] = y;228 }229 else { // ask fth230 int t = ask(f, x, y);231 if(t == -1) {232 puts("invalid request!");233 }234 else {235 printf("%d\n", X[t]);236 }237 }238 }239 return 0;240 }
写的有点乱...