Description

一个长度为\(n\)的序列\(a\)，设其排过序之后为\(b\)，其中位数定义为\(b[n/2]\)，其中\(a,b\)从\(0\)开始标号,除法取下整。

给你一个长度为n的序列\(s\)。

回答\(Q\)个这样的询问：\(s\)的左端点在\([a,b]\)之间,右端点在\([c,d]\)之间的子序列中，最大的中位数。

其中\(a<b<c<d\)。

位置也从\(0\)开始标号,强制在线

Solution

求中位数有一个很常见的做法，二分一个答案，把大于等于它的数设为\(1\),小于它的数设为\(1\)

这样，如果区间和大于等于\(0\)，中位数显然会大于等于当前答案

可以对每个权值都建一个线段树，当然可以用主席树来实现

check的时候，我们显然需要得到区间最大值，对\([a,b]\)求后缀最大值，\([b+1,c-1]\)区间求和，\([c,d]\)求前缀最大值即可

调了很久，一直都是\(95\)分，结果是id[i-1].size-1写成了id[i-1].size，我倒了

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 20005int n,N,val[MN],nn[MN],root[MN];std::vector
     
       id[MN];struct Node{int ls,rs,lm,rm,s;}t[MN*50];int sz;#define mid ((l+r)>>1)#define lson t[x].ls#define rson t[x].rsinline void up(int x){    t[x].s=t[lson].s+t[rson].s;    t[x].rm=max(t[rson].rm,t[lson].rm+t[rson].s);    t[x].lm=max(t[lson].lm,t[rson].lm+t[lson].s);}inline void Build(int &x,int l,int r){    x=++sz;if(l==r) return (void)(t[x]=(Node){0,0,1,1,1});    Build(lson,l,mid);Build(rson,mid+1,r);up(x);}inline void Modify(int &x,int l,int r,int p){    t[++sz]=t[x];x=sz;    if(l==r){t[x].s=t[x].lm=t[x].rm=-1;return;}    p<=mid?Modify(lson,l,mid,p):Modify(rson,mid+1,r,p);up(x);}#define P std::pair
      
       inline P QR(int x,int l,int r,int a,int b){    if(a==l&&r==b) return std::make_pair(t[x].rm,t[x].s);    if(b<=mid) return QR(lson,l,mid,a,b);    if(a>mid) return QR(rson,mid+1,r,a,b);    P L=QR(lson,l,mid,a,mid),R=QR(rson,mid+1,r,mid+1,b);    return std::make_pair(max(L.first+R.second,R.first),L.second+R.second);}inline P QL(int x,int l,int r,int a,int b){    if(a==l&&r==b) return std::make_pair(t[x].lm,t[x].s);    if(b<=mid) return QL(lson,l,mid,a,b);    if(a>mid) return QL(rson,mid+1,r,a,b);    P L=QL(lson,l,mid,a,mid),R=QL(rson,mid+1,r,mid+1,b);    return std::make_pair(max(R.first+L.second,L.first),L.second+R.second);}inline int QS(int x,int l,int r,int a,int b){    if(a>b) return 0;    if(a==l&&r==b) return t[x].s;    if(b<=mid) return QS(lson,l,mid,a,b);    if(a>mid) return QS(rson,mid+1,r,a,b);    return QS(lson,l,mid,a,mid)+QS(rson,mid+1,r,mid+1,b);}inline bool check(int a,int b,int c,int d,int v){    int Ans=QR(root[v],1,n,a,b).first+QS(root[v],1,n,b+1,c-1)+QL(root[v],1,n,c,d).first;    return Ans>=0;}int main(){    n=read();register int i,j;    for(i=1;i<=n;++i) nn[i]=val[i]=read();    std::sort(nn+1,nn+n+1);N=std::unique(nn+1,nn+n+1)-nn-1;    for(i=1;i<=n;++i) val[i]=std::lower_bound(nn+1,nn+N+1,val[i])-nn,id[val[i]].push_back(i);    Build(root[1],1,n);    for(i=2;i<=N;++i)    {        root[i]=root[i-1];        for(j=id[i-1].size()-1;~j;--j) Modify(root[i],1,n,id[i-1][j]);    }    register int Q=read(),a[6],x=0,l,r;    while(Q--)    {        for(i=0;i<4;++i) a[i]=(read()+x)%n+1;        std::sort(a,a+4);        for(x=l=1,r=N;l<=r;check(a[0],a[1],a[2],a[3],mid)?(x=mid,l=mid+1):r=mid-1);        printf("%d\n",x=nn[x]);    }    return 0;}
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！