首页 > 代码库 > BZOJ 2653: middle [主席树 中位数]
BZOJ 2653: middle [主席树 中位数]
传送门
题意：
一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个
长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
我会使用一些方式强制你在线。
最后一句话太可怕了$QAQ$
首先需要知道怎么求中位数：
二分答案，$\ge$的为$1$，$<$的为$-1$，如果和$\ge 0$说明当前答案$\le$中位数
最大中位数？$GSS$!
只要求$[a,b].rm+(b,c).sum+[c,d].lm$就可以了，注意中间是开区间，$WA$了一次看别人代码才发现
多个询问怎么办？
考虑用线段树维护，离散化后对数值建函数式线段树维护序列，$i$与$i+1$只有一个点不同，只要把$i$置为$-1$就可以了
二分之后到对应的线段树上去求$GSS$
PS：重载运算符的节点合并不知道比原来高到哪里去了
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;#define lc t[x].l#define rc t[x].r#define mid ((l+r)>>1)#define lson t[x].l,l,mid#define rson t[x].r,mid+1,rtypedef long long ll;const int N=2e4+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,Q;struct Number{ int v,id; bool operator <(const Number &r)const{return v<r.v;}}s[N];struct Node{ int l,r,lm,rm,sum; Node(){} Node(int a,int b,int c):lm(a),rm(b),sum(c){}}t[N*30];int sz,root[N];inline void merge(int x){ t[x].sum=t[lc].sum+t[rc].sum; t[x].lm=max(t[lc].lm,t[lc].sum+t[rc].lm); t[x].rm=max(t[rc].rm,t[rc].sum+t[lc].rm);}Node operator +(Node a,Node b){ Node re; re.sum=a.sum+b.sum; re.lm=max(a.lm,a.sum+b.lm); re.rm=max(b.rm,b.sum+a.rm); return re;}void segCha(int &x,int l,int r,int p,int v){ t[++sz]=t[x];x=sz; if(l==r) t[x].sum=t[x].lm=t[x].rm=v; else{ if(p<=mid) segCha(lson,p,v); else segCha(rson,p,v); merge(x); }}Node segQue(int x,int l,int r,int ql,int qr){ if(ql>qr) return Node(0,0,0); if(ql<=l&&r<=qr) return t[x]; else{ if(qr<=mid) return segQue(lson,ql,qr); if(mid<ql) return segQue(rson,ql,qr); return segQue(lson,ql,qr)+segQue(rson,ql,qr); }}void build(int &x,int l,int r){ t[++sz]=t[x];x=sz; if(l==r) t[x].sum=t[x].lm=t[x].rm=1; else{ build(lson); build(rson); merge(x); }}int a,b,c,d,q[5];int Query(int g){ int x=root[g]; return segQue(x,0,n-1,a,b).rm+segQue(x,0,n-1,b+1,c-1).sum+segQue(x,0,n-1,c,d).lm;}int main(){ freopen("in","r",stdin); n=read(); for(int i=0;i<n;i++) s[i].v=read(),s[i].id=i; sort(s,s+n); build(root[0],0,n-1); for(int i=1;i<n;i++) root[i]=root[i-1],segCha(root[i],0,n-1,s[i-1].id,-1); int last=0; Q=read();//int debug=0; while(Q--){//printf("debug %d\n",++debug); for(int i=1;i<=4;i++) q[i]=(read()+last)%n; sort(q+1,q+1+4); a=q[1];b=q[2];c=q[3];d=q[4]; //printf("abcd %d %d %d %d\n",a,b,c,d); int l=0,r=n-1,ans=0; while(l<=r){ int mi=(l+r)>>1; if(Query(mi)>=0) ans=mi,l=mi+1; else r=mi-1; } last=s[ans].v; printf("%d\n",last); }}
BZOJ 2653: middle [主席树 中位数]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。