LuoguP2839 [国家集训队]middle

(Updated: )
oi
,

Description

题目链接

一个长度为 $n$ 的序列 $a$，设其升序排序之后为 $b$，那么序列 $a$ 的中位数定义为 $b_{\lfloor\frac{n}{2}\rfloor}$，其中 $a,b$ 从 $0$ 开始标号，除法取下整。

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

其中 $a<b<c<d$。位置也从 $0$ 开始标号。

强制在线。

$1\leq n \leq 20000,1\leq Q\leq 25000$。

Solution

首先对于每个询问，我们可以先二分答案。

考虑二分答案 $mid$ 如何 check。

如果我们将序列中的所有小于 $mid$ 的数字都标记为 $-1$，所有大于等于 $mid$ 的数字都标记为 $1$，那么我们只需要查询是否存在合法的一个区间内的和大于等于 $0$ 即可。

那么我们只需要先预处理建出选择所有 $mid$ 的值域线段树，这样每次相邻两个权值实际上只改变了几个位置，所以主席树即可，维护以下几个值：

  1. 区间和
  2. 区间最大前缀和
  3. 区间最大后缀和

那么合法的区间的最大值就是 $\max_{i=a}^{b+1}\sum_{i}^{b}+\sum_{b+1}^{c-1}{p_i}+\max_{i=c-1}^{d}\sum_{c}^{i}$。

用线段树维护即 $Rmax(a,b)+Sum(b+1,c-1)+Lmax(c,d)$。

所以我们只需要维护一下主席树即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e4,M=N+5e3;
int n,q,t[5],rt[N];
struct seq{int v,pos;}a[N];
I bool cmp(Cn seq& x,Cn seq& y){return x.v<y.v;}
class PresidentTree{
    private:
        int cnt;
        struct node{int l,r,S,L,R;}T[N*30];
        #define mid (l+r>>1) 
        #define ls T[x].l,l,mid
        #define rs T[x].r,mid+1,r
        #define PU(x) (T[x].S=T[T[x].l].S+T[T[x].r].S,T[x].L=max(T[T[x].l].L,T[T[x].l].S+T[T[x].r].L),T[x].R=max(T[T[x].r].R,T[T[x].r].S+T[T[x].l].R))
        I int QS(CI x,CI l,CI r,CI L,CI R){
            if(L<=l&&r<=R) return T[x].S;
            RI S=0;return L<=mid&&(S+=QS(ls,L,R)),R>mid&&(S+=QS(rs,L,R)),S;
        }
        I int QL(CI x,CI l,CI r,CI L,CI R){
            if(L<=l&&r<=R) return T[x].L;
            if(R<=mid) return QL(ls,L,R);else if(L>mid) return QL(rs,L,R);
            else return max(QL(ls,L,mid),QS(ls,L,mid)+QL(rs,mid+1,R));//前缀最大值
        }
        I int QR(CI x,CI l,CI r,CI L,CI R){
            if(L<=l&&r<=R) return T[x].R;
            if(R<=mid) return QR(ls,L,R);else if(L>mid) return QR(rs,L,R);
            else return max(QR(rs,mid+1,R),QS(rs,mid+1,R)+QR(ls,L,mid));//后缀最大值
        }
    public:
        I void B(int& x,CI l,CI r){
            x=++cnt;T[x].S=T[x].L=T[x].R=r-l+1;if(l==r) return ;
            B(ls),B(rs);
        }
        I void U(CI pre,int& x,CI l,CI r,CI p,CI v){
            T[x=++cnt]=T[pre];if(l==r) return void(T[x].S=T[x].L=T[x].R=v);
            p<=mid?U(T[pre].l,ls,p,v):U(T[pre].r,rs,p,v),PU(x);
        }
        I int check(CI k,CI a,CI b,CI c,CI d){
            RI S=0;if(b+1<=c-1) S+=QS(rt[k],1,n,b+1,c-1);//查询[b+1,c-1]的和，注意特判区间不存在的情况
            S+=QR(rt[k],1,n,a,b)+QL(rt[k],1,n,c,d);return S>=0;//如果大于等于0即合法
        }
}S;
int main(){
    RI i,j,l,r,p=0;for(read(n),i=1;i<=n;i++) read(a[i].v),a[i].pos=i;sort(a+1,a+n+1,cmp);
    for(S.B(rt[1],1,n),i=2;i<=n+1;i++) S.U(rt[i-1],rt[i],1,n,a[i-1].pos,-1);for(read(q),i=1;i<=q;i++){//预处理，建树
        for(j=0;j<4;j++) read(t[j]),t[j]+=p,t[j]%=n,t[j]++;
        sort(t,t+4);l=0,r=n;W(l<=r) S.check(mid,t[0],t[1],t[2],t[3])?(p=mid,l=mid+1):r=mid-1;writeln(p=a[p].v);
    }return 0;
}