链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2653
神犇题解:http://blog.csdn.net/wzq_qwq/article/details/48809845
题解
先来考虑一个子问题:
假如序列左端点在[l1,r1]之间,右端点在[l2,r2]之间
给定中位数x,问能否找出一个区间使得中位数大于等于x
这个问题很简单的样子:将小于x的赋值-1,大于x赋值为1
这样问题就转化为能否找到一个区间使得区间和大于等于0
这个可以用线段树在 log(n)
的时间内处理
如何在可以接受的时间复杂度内搞出每一个中位数对应的那颗线段树
考虑将原序列排序后从小到大来建树
第i棵线段树和第i+1棵线段树就只有第i个位置需要从1变成-1
这个用函数式线段树就好啦!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 25000 + 9; const int M = 400000; int n,m,tot,arr[N],_hash[N],last_ans; vector<int> pos_que[N]; namespace Chair_Tree{ #define CT Chair_Tree int ch[M][2],ls[M],rs[M],sum[M],root[N],cnt; void Build(int &w, int l, int r) { sum[w=++cnt] = r - l + 1; ls[w] = rs[w] = sum[w]; if (l < r) { int mid = l + r + 1 >> 1; Build(ch[w][0], l, mid-1); Build(ch[w][1], mid, r); } }inline void init() {Build(root[1],1,n);} void insert(int p, int &w, int l, int r, int pur) { sum[w=++cnt] = sum[p] - 2; memcpy(ch[w],ch[p],sizeof(ch[w])); if (l < r) { int mid = l + r + 1 >> 1; if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, pur); else insert(ch[p][1], ch[w][1], mid, r, pur); ls[w] = max(ls[ch[w][0]], sum[ch[w][0]] + ls[ch[w][1]]); rs[w] = max(rs[ch[w][1]], sum[ch[w][1]] + rs[ch[w][0]]); } else { ls[w] = rs[w] = 0; } } inline void insert(int p, int w, int val) { insert(root[p],root[w],1,n,val); } int Get_sum(int w, int l, int r, int L, int R) { if (L <= l && r <= R) { return sum[w]; } else { int mid = l + r + 1 >> 1, ret = 0; if (L < mid) ret += Get_sum(ch[w][0], l, mid-1, L, R); if (mid <= R) ret += Get_sum(ch[w][1], mid, r, L, R); return ret; } } inline int Get_Sum(int w, int l, int r) { return Get_sum(root[w],1,n,l,r); } int query_left(int w, int l, int r, int L, int R) { if (L <= l && r <= R) { return ls[w]; } else { int mid = l + r + 1 >> 1; if (R < mid) return query_left(ch[w][0], l, mid-1, L, R); else if (mid <= L) return query_left(ch[w][1], mid, r, L, R); else { int t1 = query_left(ch[w][0], l, mid-1, L, mid-1); int t2 = query_left(ch[w][1], mid, r, mid, R) + Get_sum(ch[w][0], l, mid-1, L, mid-1); return max(t1, t2); } } } inline int Left_Max(int w, int l, int r) { return query_left(root[w],1,n,l,r); } int query_right(int w, int l, int r, int L, int R) { if (L <= l && r <= R) { return rs[w]; } else { int mid = l + r + 1 >> 1; if (R < mid) return query_right(ch[w][0], l, mid-1, L, R); else if (mid <= L) return query_right(ch[w][1], mid, r, L, R); else { int t1 = query_right(ch[w][1], mid, r, mid, R); int t2 = query_right(ch[w][0], l, mid-1, L, mid-1) + Get_sum(ch[w][1], mid, r, mid, R); return max(t1, t2); } } } inline int Right_Max(int w, int l, int r) { return query_right(root[w], 1, n, l, r); } }; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline bool judge(int sta, int *lim) { int ret = CT::Get_Sum(sta, lim[2], lim[3]); ret += lim[1] < lim[2] ? CT::Right_Max(sta, lim[1], lim[2] - 1) : 0; ret += lim[3] < lim[4] ? CT::Left_Max(sta, lim[3] + 1, lim[4]) : 0; return ret >= 0; } int main() { n = read(); for (int i=1;i<=n;i++) arr[i] = _hash[i] = read(); sort(_hash+1, _hash+1+n); tot = unique(_hash+1, _hash+1+n) - _hash - 1; for (int i=1;i<=n;i++) { arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash; pos_que[arr[i]].push_back(i); } CT::init(); for (int i=2;i<=tot;i++) { CT::insert(i-1,i,pos_que[i-1][0]); for (int j=1,lim=pos_que[i-1].size();j<lim;j++) CT::insert(i,i,pos_que[i-1][j]); } m = read(); for (int i=1,lim[5],l,r,mid,ret;i<=m;i++) { for (int j=1;j<=4;j++) lim[j] = (read() + last_ans) % n + 1; sort(lim+1, lim+1+4); l = 1, r = tot; while (l <= r) { mid = l + r >> 1; if (!judge(mid,lim)) r = mid-1; else ret = mid, l = mid + 1; } printf("%d\n",last_ans = _hash[ret]); } return 0; }
What i don’t understood is in truth how you are now not really much more smartly-liked than you might be now. You’re very intelligent. You already know therefore considerably in the case of this matter, produced me in my view imagine it from a lot of varied angles. Its like men and women aren’t interested until it is something to do with Girl gaga! Your individual stuffs great. Always care for it up!
I simply wished to appreciate you again. I am not sure the things I would’ve carried out in the absence of the opinions revealed by you about this subject. It seemed to be a real terrifying condition in my view, however , witnessing your professional technique you resolved it made me to weep with fulfillment. Now i am thankful for this information and in addition hope that you are aware of a great job you happen to be accomplishing training people today with the aid of your web blog. Most likely you’ve never encountered all of us.