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