一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整。给你一个
长度为n的序列s。回答Q个这样的询问:s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中,最大的中位数。
其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。
本文共 1459 字,大约阅读时间需要 4 分钟。
Q行依次给出询问的答案。
0:n,Q<=100 1,...,5:n<=2000 0,...,19:n<=20000,Q<=25000
/*对于中位数x一定存在区间内大于x的个数==小于x的个数或者 于x的个数==小于x的个数+1,因此可以先预处理出将每个数作为中位数将比它小的赋为-1,比它大的赋为1,如果它是合法答案,不然存在合法区间的值>=0所以只需要二分x就行。 */#include#include #include #include #include #define N 90000typedef long long LL;int n;struct p{ LL v; int pos;}poi[N];int root[N],ls[N*60],rs[N*60],c[N*60],tot,lmax[N],rmax[N];LL pp[6];inline bool cmp(const p a,const p b){return a.v R)return 0; if (l<=L&&R<=r)return c[rt]; int mid=(L+R)/2; int m=0; if (l<=mid)m+=askall(ls[rt],L,mid,l,r); if (mid R||l>r)return 0; if (l<=L&&R<=r)return rmax[rt]; int mid=(L+R)/2; if (mid R||l>r)return 0; if (l<=L&&R<=r)return lmax[rt]; int mid=(L+R)/2; if (mid =0)return 1;else return 0;}void build(int &rt,int l,int r){ if (!rt) rt=++tot; if (l==r){ lmax[rt]=rmax[rt]=c[rt]=1; return ; } int mid=(l+r)/2; if (l<=mid)build(ls[rt],l,mid); if (mid
转载地址:http://drqji.baihongyu.com/