#主席树，二分#洛谷 2839 JZOJ 2902 middle

本文主要是介绍#主席树，二分#洛谷 2839 JZOJ 2902 middle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你一个长度为 $n$ 的序列 $s$ 。
回答 $Q$ 个这样的询问： $s$ 的左端点在 $[a\sim b]$ 之间,右端点在 $[c\sim d]$ 之间的子序列中，最大的中位数。
其中 $a < b < c < d$ 。

分析

新技能get
区间中位数二分答案 $k$ ，一般把 $< k$ 的设为-1， $\geq k$ 的设为1，如果最大子段和 $\geq 0$ ，那么可以再继续增大 $k$ ，否则只能减小，然后还有一个锅这里不能初始化为0，应为一个很小的数，因为必须选择

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=20011; int tot,ls[N*18],rs[N*18],n,rt[N],rk[N],a[N],q[6];
struct rec{int lmax,rmax,w; inline void Pro(){lmax=rmax=-n-n,w=0;}}b[N*18],Ans;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
inline rec merge(rec t1,rec t2){rr rec t;t.lmax=max(t1.lmax,t1.w+t2.lmax);t.rmax=max(t1.rmax+t2.w,t2.rmax);t.w=t1.w+t2.w;return t;
}
inline void build(int &rt,int l,int r){rt=++tot,b[rt].lmax=b[rt].rmax=b[rt].w=r-l+1;if (l==r) return; rr int mid=(l+r)>>1;build(ls[rt],l,mid),build(rs[rt],mid+1,r);
}
inline void update(int &rt,int l,int r,int x){b[++tot]=b[rt],ls[tot]=ls[rt],rs[tot]=rs[rt],rt=tot;if (l==r){b[tot].lmax=b[tot].rmax=b[tot].w=-1;return;}rr int mid=(l+r)>>1;if (x<=mid) update(ls[rt],l,mid,x);else update(rs[rt],mid+1,r,x);b[rt]=merge(b[ls[rt]],b[rs[rt]]);
}
inline void Query(int root,int l,int r,int x,int y){if (l==x&&r==y) return Ans=merge(Ans,b[root]),void();rr int mid=(l+r)>>1;if (y<=mid) Query(ls[root],l,mid,x,y);else if (x>mid) Query(rs[root],mid+1,r,x,y);else Query(ls[root],l,mid,x,mid),Query(rs[root],mid+1,r,mid+1,y);
}
inline bool check(int now){rr int ans=0;if (q[1]<q[2]-1) Ans.Pro(),Query(rt[now],1,n,q[1]+1,q[2]-1),ans+=Ans.w;//中间那一段求和Ans.Pro(),Query(rt[now],1,n,q[0],q[1]),ans+=Ans.rmax,//左边这一段求最大后缀子段和Ans.Pro(),Query(rt[now],1,n,q[2],q[3]),ans+=Ans.lmax;//右边这一段求最大前缀子段和return ans>=0;
}
bool cmp(int x,int y){return a[x]<a[y];}
signed main(){n=iut(); build(rt[1],1,n),b[0].Pro();for (rr int i=1;i<=n;++i) a[i]=iut(),rk[i]=i;sort(rk+1,rk+1+n,cmp);for (rr int i=2;i<=n;++i) update(rt[i]=rt[i-1],1,n,rk[i-1]);for (rr int Q=iut(),lastans=0;Q;--Q){for (rr int i=0;i<4;++i) q[i]=(iut()+lastans)%n+1; sort(q,q+4);rr int l=1,r=n;while (l<r){rr int mid=(l+r+1)>>1;if (check(mid)) l=mid;else r=mid-1;}print(lastans=a[rk[l]]),putchar(10);}return 0;
}