Description
给定一个数列，然后给定启示区间 ([a,b]) 和终止区间 ([c,d])
求 ([l,r],lin[a,b],rin [c,d]) 的最大中位数
(nle 20000)
Solution
神仙思路
首先二分中位数
大于的是 (1)，小于的是 (-1)
然后变成了必然取 ([b+1,c-1]) 和 ([a,b]) 的最大后缀和 ([c,d]) 的最大前缀的问题
然后这步真的神仙：
对于所有的二分的mid维护线段树求 (lmax,rmax)
（这里是对值域操作）
开线段树是不太能够空间的，那么改成主席树
每次更改的时候直接在上一棵树上改改就行了（这里有点点细节）
Code
#include<bits/stdc++.h>
using namespace std;
#define reg register
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=2e4+10,M=N*60;
int lans,q[5],a[N],b[N],n,m;
vector<int> g[N];
struct node{
int sum,lm,rm;
};
inline node upd(node a,node b)
{
node res; res.sum=a.sum+b.sum;
res.lm=max(a.lm,max(a.sum+b.lm,res.sum));
res.rm=max(a.rm+b.sum,max(b.rm,res.sum));
return res;
}
int ls[M],lm[M],rm[M],rs[M],rt[N],sum[M],tot;
inline void push_up(int p)
{
sum[p]=sum[ls[p]]+sum[rs[p]];
rm[p]=max(rm[rs[p]],max(rm[ls[p]]+sum[rs[p]],sum[p]));
lm[p]=max(lm[ls[p]],max(lm[rs[p]]+sum[ls[p]],sum[p]));
return ;
}
inline void update(int &p,int pre,int l,int r,int pos,int val,bool fl)
{
if(!fl) p=++tot,ls[p]=ls[pre],rs[p]=rs[pre];
if(l==r) return rm[p]=lm[p]=sum[p]=val,void();
int mid=(l+r)>>1;
if(pos<=mid)
{
if(ls[p]==ls[pre]) update(ls[p],ls[pre],l,mid,pos,val,0);
else update(ls[p],ls[pre],l,mid,pos,val,1);
}
else
{
if(rs[p]==rs[pre]) update(rs[p],rs[pre],mid+1,r,pos,val,0);
else update(rs[p],rs[pre],mid+1,r,pos,val,1);
}return push_up(p);
}
inline node findrm(int p,int st,int ed,int l,int r)
{
if(l<=st&&ed<=r) return (node){sum[p],lm[p],rm[p]};
int mid=(st+ed)>>1;
if(l>mid) return findrm(rs[p],mid+1,ed,l,r);
if(r<=mid) return findrm(ls[p],st,mid,l,r);
return upd(findrm(ls[p],st,mid,l,r),findrm(rs[p],mid+1,ed,l,r));
}
inline node findlm(int p,int st,int ed,int l,int r)
{
if(l<=st&&ed<=r) return (node){sum[p],lm[p],rm[p]};
int mid=(st+ed)>>1;
if(l>mid) return findlm(rs[p],mid+1,ed,l,r);
if(r<=mid) return findlm(ls[p],st,mid,l,r);
return upd(findlm(ls[p],st,mid,l,r),findlm(rs[p],mid+1,ed,l,r));
}
inline int ask(int p,int st,int ed,int l,int r)
{
if(l<=st&&ed<=r) return sum[p];
int mid=(st+ed)>>1,res=0;
if(l<=mid) res+=ask(ls[p],st,mid,l,r);
if(r>mid) res+=ask(rs[p],mid+1,ed,l,r);
return res;
}
inline bool check(int val)
{
int sum1;
if(q[2]+1<=q[3]-1) sum1=ask(rt[val],1,m,q[2]+1,q[3]-1);
else sum1=0;
int sum2=findrm(rt[val],1,m,q[1],q[2]).rm;
int sum3=findlm(rt[val],1,m,q[3],q[4]).lm;
return (sum1+sum2+sum3)>=0;
}
signed main()
{
n=read();
for(reg int i=1;i<=n;++i) a[i]=read(),b[i]=a[i]; m=n;
sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1;
for(reg int i=1;i<=n;++i)
{
a[i]=lower_bound(b+1,b+m+1,a[i])-b;
g[a[i]].push_back(i);
}
for(reg int i=1;i<=n;++i) update(rt[1],rt[0],1,n,i,1,rt[1]?1:0);
for(reg int i=2;i<=m;++i)
{
int sz=g[i-1].size();
for(reg int j=0;j<sz;++j)
update(rt[i],rt[i-1],1,m,g[i-1][j],-1,rt[i]?1:0);
}
int T=read();
while(T--)
{
for(reg int i=1;i<=4;++i) q[i]=(read()+lans)%n;
sort(q+1,q+4+1); for(reg int i=1;i<=4;++i) q[i]++;
int st=1,ed=m;
while(st<=ed)
{
int mid=(st+ed)>>1;
if(check(mid)) lans=mid,st=mid+1;
else ed=mid-1;
}
printf("%lld
",lans=b[lans]);
}
return 0;
}
}
signed main(){return yspm::main();}
有一说一，其实好写，花了一节多一点点自习就做完了
比那个选课简单多了
另：由于未知原因，这份代码在洛谷上过不去，然后把离散化删掉改改就能过了……