首页 > 代码库 > BZOJ 2653 middle
BZOJ 2653 middle
题目大意：有一个序列，包含多次询问。询问区间左右端点在规定区间里移动所得到的最大中位数的值。
考虑对于每个询问，如何得到最优区间？枚举显然是超时的，只能考虑二分。
中位数的定义是在一个序列中，比中位数小的数跟比它大的数一样多，由于我们要求的是最大的中位数，自然希望能找到一个区间，使得该区间内比该中位数大的数尽量多。
二分中位数k，假设比k小的数记为-1，其余的数记为1，那么我们就是要寻找最大连续子序列和，若找到的最大的和>=0，则当前的k就是合法的。
最大连续子序列和可以用线段树来维护，由于存在多组询问，每次建一棵线段树很慢，我们选择建主席树。初始时，把数按从小到大排好序，全部的数记为1，做到第i个数时，将第i-1个数记为-1，以此做下去。
那么这样最终二分到的答案会不会不在指定的区间范围之中呢？
肯定是不存在的，我们可以分类讨论。
n为偶数：n = 4时，0 1 2 3，中位数的位置为2，如果答案在1-2之间，则会有更优的答案；如果在2-3之间，显然是不可能的。
n为奇数：n = 3时，0 1 2 3 4，中位数的位置为2，分析同上。
#include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 20005; int n, a[maxn], b[maxn], root[maxn], q[10]; struct Tree { int cnt; int ml[maxn*20], mr[maxn*20], sum[maxn*20], ls[maxn*20], rs[maxn*20]; Tree() { cnt = 0; } void pushup(int rt) { ml[rt] = max(ml[ls[rt]], sum[ls[rt]]+ml[rs[rt]]); mr[rt] = max(mr[rs[rt]], sum[rs[rt]]+mr[ls[rt]]); sum[rt] = sum[ls[rt]]+sum[rs[rt]]; } void build(int rt, int l, int r) { if (l == r) { ml[rt] = mr[rt] = sum[rt] = 1; return ; } int mid = (l+r)>>1; ls[rt] = ++cnt, build(ls[rt], l, mid); rs[rt] = ++cnt, build(rs[rt], mid+1, r); pushup(rt); } void update(int las_rt, int rt, int l, int r, int p, int d) { if (l == r) { ml[rt] = mr[rt] = sum[rt] = d; return ; } int mid = (l+r)>>1; if (p <= mid) { ls[rt] = ++cnt, rs[rt] = rs[las_rt]; update(ls[las_rt], ls[rt], l, mid, p, d); } else { ls[rt] = ls[las_rt], rs[rt] = ++cnt; update(rs[las_rt], rs[rt], mid+1, r, p, d); } pushup(rt); } int query_sum(int rt, int l, int r, int L, int R) { if (L <= l && r <= R) return sum[rt]; int mid = (l+r)>>1, ret = 0; if (L <= mid) ret += query_sum(ls[rt], l, mid, L, R); if (R > mid) ret += query_sum(rs[rt], mid+1, r, L, R); return ret; } int query_ml(int rt, int l, int r, int L, int R) { if (L <= l && r <= R) return ml[rt]; int mid = (l+r)>>1; if (R <= mid) return query_ml(ls[rt], l, mid, L, R); else if (L > mid) return query_ml(rs[rt], mid+1, r, L, R); else return max(query_ml(ls[rt], l, mid, L, R), query_sum(ls[rt], l, mid, L, R)+query_ml(rs[rt], mid+1, r, L, R)); } int query_mr(int rt, int l, int r, int L, int R) { if (L <= l && r <= R) return mr[rt]; int mid = (l+r)>>1; if (R <= mid) return query_mr(ls[rt], l, mid, L, R); else if (L > mid) return query_mr(rs[rt], mid+1, r, L, R); else return max(query_mr(rs[rt], mid+1, r, L, R), query_sum(rs[rt], mid+1, r, L, R)+query_mr(ls[rt], l, mid, L, R)); } }T; bool cmp(const int &AI, const int &BI) { return a[AI] < a[BI]; } void build_tree() { root[1] = ++T.cnt; T.build(root[1], 1, n); for (int i = 2; i <= n; ++i) { root[i] = ++T.cnt; T.update(root[i-1], root[i], 1, n, b[i-1], -1); } } bool check(int k, int q1, int q2, int q3, int q4) { int sum = 0; if (q2+1 < q3) sum += T.query_sum(root[k], 1, n, q2+1, q3-1); sum += T.query_mr(root[k], 1, n, q1, q2); sum += T.query_ml(root[k], 1, n, q3, q4); return sum >= 0; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = i; sort(b+1, b+n+1, cmp); build_tree(); int ans = 0; int task; scanf("%d", &task); while (task --) { scanf("%d %d %d %d", &q[1], &q[2], &q[3], &q[4]); for (int i = 1; i <= 4; ++i) q[i] = (q[i]+ans)%n+1; sort(q+1, q+4+1); int l = 1, r = n; while (l < r) { int mid = (l+r+1)>>1; if (check(mid, q[1], q[2], q[3], q[4])) l = mid; else r = mid-1; } ans = a[b[l]]; printf("%d\n", ans); } return 0; }
BZOJ 2653 middle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。