淄博网站制作定制改版,招商网站开发,做足球原创短视频网站,东莞网络推广网站F. Strange Array
给定一个长度为nnn的数组aaa#xff0c;1≤ai≤n1 \leq a_i \leq n1≤ai≤n#xff0c;对于每个aia_iai#xff0c;我们要找到一个l≤i,r≥il \leq i, r \geq il≤i,r≥i#xff0c;
使得#xff0c;我们对区间[l,r][l, r][l,r]升序后#xff0c;…F. Strange Array
给定一个长度为nnn的数组aaa1≤ai≤n1 \leq a_i \leq n1≤ai≤n对于每个aia_iai我们要找到一个l≤i,r≥il \leq i, r \geq il≤i,r≥i
使得我们对区间[l,r][l, r][l,r]升序后值为aia_iai的数与中位数相隔最远输出这个最远距离。
我们分两种情况讨论 aia_iai在中位数的左边也就是ai≤a_i \leqai≤中位数我们考虑把aj≥aia_j \geq a_iaj≥ai的设置为111其他都设置为−1-1−1 则我们就是要对每个iii找到一个区间[l,r][l, r][l,r]使得区间和最大假设这个区间和为xxx则答案即为x2\frac{x}{2}2x aia_iai在中位数的右边也就是ai≥a_i \geqai≥中位数我们考虑把aj≤aia_j \leq a_iaj≤ai的设置为111其他设置为−1-1−1 则我们就是要对每个iii找到一个区间[l,r][l, r][l,r]使得区间和最大假设这个区间和为xxx则答案即为x12−1\frac{x 1}{2} - 12x1−1。
综上我们对这两个答案取maxmaxmax即可至于对值的维护我们可以考虑用主席树维护区间左、右最大和即可。
#include bits/stdc.husing namespace std;const int N 2e5 10;int root[N], ls[N 5], rs[N 5], num;int a[N], ans[N], n;vectorint P[N];struct Res {int lsum, sum, rsum;
}T[N 5];Res operator (Res a, Res b) {return {max(a.lsum, a.sum b.lsum), a.sum b.sum, max(a.rsum b.sum, b.rsum)};
}void push_up(int rt) {T[rt] T[ls[rt]] T[rs[rt]];
}void build(int rt, int l, int r) {rt num;if (l r) {T[rt] {1, 1, 1};return ;}int mid l r 1;build(ls[rt], l, mid);build(rs[rt], mid 1, r);push_up(rt);
}void update(int rt, int pre, int l, int r, int x, int v) {rt num, ls[rt] ls[pre], rs[rt] rs[pre];if (l r) {T[rt] {v, v, v};return ;}int mid l r 1;if (x mid) {update(ls[rt], ls[pre], l, mid, x, v);}else {update(rs[rt], rs[pre], mid 1, r, x, v);}push_up(rt);
}Res query(int rt, int l, int r, int L, int R) {if (l L r R) {return T[rt];}int mid l r 1;if (L mid R mid) {return query(ls[rt], l, mid, L, R) query(rs[rt], mid 1, r, L, R);}else if (L mid) {return query(ls[rt], l, mid, L, R);}else {return query(rs[rt], mid 1, r, L, R);}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);P[a[i]].push_back(i);}build(root[1], 1, n);for (int i 2; i n; i) {root[i] root[i - 1];for (auto it : P[i - 1]) {update(root[i], root[i], 1, n, it, -1);}}for (int i 1; i n; i) {int lsum 0, rsum 0, sum 1;if (i ! 1) {lsum query(root[a[i]], 1, n, 1, i - 1).rsum;}if (i ! n) {rsum query(root[a[i]], 1, n, i 1, n).lsum;}if (lsum 0) {sum lsum;}if (rsum 0) {sum rsum;}ans[i] max(ans[i], sum 1);}for (int i 1; i num; i) {ls[i] rs[i] 0;}for (int i 1; i n; i) {root[i] 0;}num 0;build(root[n], 1, n);for (int i n - 1; i 1; i--) {root[i] root[i 1];for (auto it : P[i 1]) {update(root[i], root[i], 1, n, it, -1);}}for (int i 1; i n; i) {int lsum 0, rsum 0, sum 1;if (i ! 1) {lsum query(root[a[i]], 1, n, 1, i - 1).rsum;}if (i ! n) {rsum query(root[a[i]], 1, n, i 1, n).lsum;}if (lsum 0) {sum lsum;}if (rsum 0) {sum rsum;}ans[i] max(ans[i], (sum 1) / 2 - 1);}for (int i 1; i n; i) {printf(%d%c, ans[i], i n ? \n : );}return 0;
}
