2653: middle
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1298 Solved: 734
[Submit][Status][Discuss]
Description
一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。
给你一个长度为n的序列s。
回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。
位置也从0开始标号。
我会使用一些方式强制你在线。
Input
第一行序列长度n。
接下来n行按顺序给出a中的数。
接下来一行Q。
然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。
Output
Q行依次给出询问的答案。
Sample Input
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
Sample Output
271451044
969056313
HINT
0:n,Q<=100
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000
Source
Solution
这道题思路相当妙啊
自己一开始看错题了，以为就是求中位数，那么显然长度为奇数时就是中间那个，长度为偶数时可能是实数，根本没法搞...
然后有一种想法很显然，就是可以通过先求出$[b,c]$段的中位数，然后贪心的从$b$到$a$，从$c$到$d$扩展这个序列，然后搞。
可是这样本质上就是暴力，所以显然不行。
以前遇到的中位数有一种很常规的搞法，就是假设中位数为$x$，那么把$<x$的赋值$-1$,把$>=x$的赋值$+1$，然后看看是否有连续的一段$Sum>=0$
这种方法显然是具有单调性的，所以又可以把枚举$x$的复杂度降到$O(logN)$
然后可以用线段树去维护连续的子段和，再维护一下左右端点，保证左右端点分别在$[a,b]$和$[c,d]$之间即可，但是这样的线段树每次需要重建，所以复杂度还是偏大。
可以考虑利用可持久化线段树，对于假定的中位数$x$，所有比他小的数为$-1$，而比他大的仍为$1$，这样就可以先建出一棵全$1$的树，然后每次再建一条$-1$的链，查询的时候前面的用$-1$，后面的用$1$，就可以达到要求了。
总复杂度$O(Qlog^{2}N)$
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int x=; char ch=getchar();
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x;
}
#define MAXN 200010
int N,a[MAXN],Q,last;
namespace PrTree
{
int lson[MAXN*],rson[MAXN*],root[MAXN],sum[MAXN*],left[MAXN*],right[MAXN*],sz;
inline void Update(int now)
{
sum[now]=sum[lson[now]]+sum[rson[now]];
left[now]=max(left[lson[now]],sum[lson[now]]+left[rson[now]]);
right[now]=max(right[rson[now]],sum[rson[now]]+right[lson[now]]);
}
inline void BuildTree(int l,int r,int &now)
{
now=++sz;
if (l==r) {left[now]=right[now]=sum[now]=; return;}
int mid=(l+r)>>;
BuildTree(l,mid,lson[now]); BuildTree(mid+,r,rson[now]);
Update(now);
}
inline void Insert(int l,int r,int &now,int fa,int pos,int val)
{
now=++sz;
if (l==r) {sum[now]=left[now]=right[now]=val; return;}
lson[now]=lson[fa],rson[now]=rson[fa];
int mid=(l+r)>>;
if (pos<=mid) Insert(l,mid,lson[now],lson[fa],pos,val);
else Insert(mid+,r,rson[now],rson[fa],pos,val);
Update(now);
}
inline int Query(int l,int r,int L,int R,int now)
{
if (L>R) return ;
if (L<=l && R>=r) return sum[now];
int mid=(l+r)>>,re=;
if (L<=mid) re+=Query(l,mid,L,R,lson[now]);
if (R>mid) re+=Query(mid+,r,L,R,rson[now]);
return re;
}
inline int Left(int l,int r,int L,int R,int now)
{
if (L>R) return ;
if (L==l && R==r) return left[now];
int mid=(l+r)>>;
if (R<=mid) return Left(l,mid,L,R,lson[now]);
else if (L>mid) return Left(mid+,r,L,R,rson[now]);
else return max(Left(l,mid,L,mid,lson[now]),Query(l,mid,L,mid,lson[now])+Left(mid+,r,mid+,R,rson[now]));
}
inline int Right(int l,int r,int L,int R,int now)
{
if (L>R) return ;
if (L==l && R==r) return right[now];
int mid=(l+r)>>;
if (R<=mid) return Right(l,mid,L,R,lson[now]);
else if (L>mid) return Right(mid+,r,L,R,rson[now]);
else return max(Right(mid+,r,mid+,R,rson[now]),Query(mid+,r,mid+,R,rson[now])+Right(l,mid,L,mid,lson[now]));
}
}using namespace PrTree;
int q[],id[MAXN];
inline bool Check(int x)
{
int a=q[],b=q[],c=q[],d=q[];
return Query(,N,b,c,root[x])+max(Right(,N,a,b-,root[x]),)+max(Left(,N,c+,d,root[x]),)>=;
}
inline bool cmp(int x,int y) {return a[x]<a[y];}
int main()
{
N=read();
for (int i=; i<=N; i++) a[i]=read(),id[i]=i;
stable_sort(id+,id+N+,cmp); stable_sort(a+,a+N+);
BuildTree(,N,root[]);
for (int i=; i<=N; i++) PrTree::Insert(,N,root[i],root[i-],id[i-],-);
Q=read();
while (Q--)
{
for (int i=; i<=; i++) q[i]=(read()+last)%N+;
stable_sort(q+,q++);
int l=,r=N,mid;
while (l<=r)
{
mid=(l+r)>>;
if (Check(mid)) l=mid+; else r=mid-;
}
printf("%d\n",last=a[l-]);
}
return ;
}