middle
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1981 Solved: 1097
[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
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
271451044
271451044
969056313
Sample Output
HINT
0:n,Q<=100
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000
题解:
十分经典啊，好题，中位数的题目，以后可以想到二分去解决。
就是比中位数大的变1，小的为-1，则sum>=0即可判断是否可以比当前二分的
中位数更大，然后就可以，所以对于从小到大，开n个不同状态的线段树，这样就可以了。
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdio> #define lson tr[p].ls
#define rson tr[p].rs
#define N 20007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if (ch=='-') f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,sz,ans;
int a[N],id[N],rt[N];
struct Node
{
int sum,lmx,rmx,ls,rs;
}tr[N*]; bool cmp(int x1,int x2)
{
return a[x1]<a[x2];
}
void update(int p)
{
tr[p].sum=tr[lson].sum+tr[rson].sum;
tr[p].lmx=max(tr[lson].lmx,tr[lson].sum+tr[rson].lmx);
tr[p].rmx=max(tr[rson].rmx,tr[rson].sum+tr[lson].rmx);
}
void build(int &p,int l,int r)
{
p=++sz;
if (l==r)
{
tr[p].sum=tr[p].lmx=tr[p].rmx=;
return;
}
int mid=(l+r)>>;
build(tr[p].ls,l,mid),build(tr[p].rs,mid+,r);
update(p);
}
void build_new(int yl,int l,int r,int &xz,int val,int z)
{
xz=++sz;tr[xz]=tr[yl];
if (l==r)
{
tr[xz].lmx=tr[xz].rmx=tr[xz].sum=val;
return;
}
int mid=(l+r)>>;
if (z<=mid) build_new(tr[yl].ls,l,mid,tr[xz].ls,val,z);
else build_new(tr[yl].rs,mid+,r,tr[xz].rs,val,z);
update(xz);
}
int get_sum(int p,int l,int r,int x,int y)
{
if (l==x&&r==y) return tr[p].sum;
int mid=(l+r)>>;
if (y<=mid) return get_sum(tr[p].ls,l,mid,x,y);
else if (x>mid) return get_sum(tr[p].rs,mid+,r,x,y);
else return get_sum(tr[p].ls,l,mid,x,mid)+get_sum(tr[p].rs,mid+,r,mid+,y);
}
int get_rx(int p,int l,int r,int x,int y)
{
if (l==x&&r==y) return tr[p].lmx;
int mid=(l+r)>>;
if (y<=mid) return get_rx(tr[p].ls,l,mid,x,y);
else if (x>mid) return get_rx(tr[p].rs,mid+,r,x,y);
else return max(get_rx(tr[p].ls,l,mid,x,mid),get_sum(tr[p].ls,l,mid,x,mid)+get_rx(tr[p].rs,mid+,r,mid+,y));
}
int get_lx(int p,int l,int r,int x,int y)
{
if (l==x&&r==y) return tr[p].rmx;
int mid=(l+r)>>;
if (y<=mid) return get_lx(tr[p].ls,l,mid,x,y);
else if (x>mid) return get_lx(tr[p].rs,mid+,r,x,y);
else return max(get_lx(tr[p].rs,mid+,r,mid+,y),get_sum(tr[p].rs,mid+,r,mid+,y)+get_lx(tr[p].ls,l,mid,x,mid));
}
bool check(int k,int a,int b,int c,int d)
{
int sum=;
if (b+<=c-) sum+=get_sum(rt[k],,n,b+,c-);
sum+=get_lx(rt[k],,n,a,b);
sum+=get_rx(rt[k],,n,c,d);
return sum>=;//大的个数多的话那么可以找更大的中位数、
}
int main()
{
n=read();
for (int i=;i<=n;i++)
a[i]=read(),id[i]=i;
sort(id+,id+n+,cmp);
build(rt[],,n);
for (int i=;i<=n;i++)
build_new(rt[i-],,n,rt[i],-,id[i-]);
int qz[];
m=read();
while(m--)
{
qz[]=read(),qz[]=read(),qz[]=read(),qz[]=read();
for (int i=;i<=;i++)
qz[i]=(qz[i]+ans)%n;
for (int i=;i<=;i++)
qz[i]+=;
sort(qz+,qz++);
int l=,r=n,mid;
while(l<r)
{
mid=(l+r+)>>;
if (check(mid,qz[],qz[],qz[],qz[])) l=mid;
else r=mid-;
}
ans=a[id[l]];
printf("%d\n",ans);
}
}