BZOJ 2653 middle（函数式线段树）

深藏阁楼爱情的钟 2022-03-29 08:48 183阅读 0赞

题目链接：[http://61.187.179.132/JudgeOnline/problem.php?id=2653][http_61.187.179.132_JudgeOnline_problem.php_id_2653]

题意：给你一个长度为n的序列s。回答Q个这样的询问：s的左端点在\[a,b\]之间,右端点在\[c,d\]之间的子序列中，最大的中位数。其中a<b<c<d。区间\[L,R\]的中位数的位置为(L+R)/2向上取整。

思路：首先将数列离散化建立函数式线段树。降序的数列若中位数为M=s\[(n+1)/2\]，那么大于等于M的数为为(n+1)/2个。若构造新的数组T，若s\[i\]>=M,T\[i\]=1,否则T\[i\]=-1。那么有所有的T\[i\]之和大于等于0。据此在线段树设置Lmax,Rmax,sum，二分答案，若\[a,b\]的Rmax+\[b+1,c-1\]的sum+\[c,d\]的Lmax大于等于0则该二分值可行。

struct node  
\{   
    int L,R,LMax,RMax,sum;  
    node \*c\[2\];  
\};  
  
  
node a\[N\*10\],\*root\[N\];  
int tot;  
  
  
node \*build(int L,int R)  
\{   
    node \*p=&a\[++tot\];  
    p->L=L;  
    p->R=R;  
    p->LMax=p->RMax=p->sum=R-L+1;  
    if(L==R) return p;  
    int mid=(L+R)>>1;  
    p->c\[0\]=build(L,mid);  
    p->c\[1\]=build(mid+1,R);  
    return p;  
\}  
  
  
void pushUp(node\* &p,node \*L,node \*R)  
\{   
    p->sum=L->sum+R->sum;  
    p->LMax=max(L->LMax,L->sum+R->LMax);  
    p->RMax=max(R->RMax,R->sum+L->RMax);  
\}  
  
  
node \*change(node \*p,int x)  
\{   
    node \*q=&a\[++tot\];  
    \*q=\*p;  
    if(p->L==p->R)  
    \{   
        q->LMax=q->RMax=q->sum=-1;  
        return q;  
    \}  
    int mid=(q->L+q->R)>>1;  
    if(x<=mid) q->c\[0\]=change(p->c\[0\],x);  
    else q->c\[1\]=change(p->c\[1\],x);  
    pushUp(q,q->c\[0\],q->c\[1\]);  
    return q;  
\}  
  
  
node \*get(node \*p,int L,int R)  
\{   
    if(L>R) return &a\[0\];  
    if(p->L==L&&p->R==R) return p;  
    int M=(p->L+p->R)>>1;  
    if(R<=M) return get(p->c\[0\],L,R);  
    if(L>M) return get(p->c\[1\],L,R);  
    node \*pl=get(p->c\[0\],L,M);  
    node \*pr=get(p->c\[1\],M+1,R);  
    node \*q=new node();  
    pushUp(q,pl,pr);  
    return q;  
\}  
  
  
pair<int,int> B\[N\];  
int n,m;  
  
  
int cal(int a,int b,int c,int d)  
\{   
    int low=1,high=n,mid,ans=0;  
    node \*x,\*y,\*z;  
    while(low<=high)  
    \{   
        mid=(low+high)>>1;  
        x=get(root\[mid\],a,b);  
        y=get(root\[mid\],b+1,c-1);  
        z=get(root\[mid\],c,d);  
        if(x->RMax+y->sum+z->LMax>=0) ans=mid,low=mid+1;  
        else high=mid-1;  
    \}  
    return B\[ans+1\].first;  
\}  
  
  
int main()  
\{   
    RD(n);  
    int i;  
    FOR1(i,n) RD(B\[i\].first),B\[i\].second=i;  
    sort(B+1,B+n+1);  
    root\[0\]=build(1,n);  
    FOR1(i,n) root\[i\]=change(root\[i-1\],B\[i\].second);  
      
    RD(m);  
    int ans=0,c\[4\];  
    while(m--)  
    \{   
        ans%=n;  
        FOR0(i,4) RD(c\[i\]),c\[i\]=(c\[i\]+ans)%n+1;  
        sort(c,c+4);  
        ans=cal(c\[0\],c\[1\],c\[2\],c\[3\]);  
        PR(ans);  
    \}  
\}

[http_61.187.179.132_JudgeOnline_problem.php_id_2653]: http://61.187.179.132/JudgeOnline/problem.php?id=2653