[二分][主席树] Luogu P2839 Middle

向右看齐 2021-12-03 22:51 247阅读 0赞

## 题目描述 ##

一个长度为n的序列a，设其排过序之后为b，其中位数定义为b\[n/2\]，其中a,b从0开始标号,除法取下整。

给你一个长度为n的序列s。

回答Q个这样的询问：s的左端点在\[a,b\]之间,右端点在\[c,d\]之间的子序列中，最大的中位数。

其中a<b<c<d。

位置也从0开始标号。

我会使用一些方式强制你在线。

## 输入输出格式 ##

输入格式：

第一行序列长度n。

接下来n行按顺序给出a中的数。

接下来一行Q。

然后Q行每行a,b,c,d，我们令上个询问的答案是x(如果这是第一个询问则x=0)。

令数组q=\{(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n\}。

将q从小到大排序之后，令真正的要询问的a=q\[0\],b=q\[1\],c=q\[2\],d=q\[3\]。

输入保证满足条件。

输出格式：

Q行依次给出询问的答案。

## 输入输出样例 ##

输入样例\#1：

5
    170337785
    271451044
    22430280
    969056313
    206452321
    3
    3 1 0 2
    2 3 1 4
    3 1 4 0

输出样例\#1：

271451044
    271451044
    969056313

## 说明 ##

0:n,Q<=100

1,...,5:n<=2000

0,...,19:n<=20000,Q<=25000

# 题解 #

*  考虑二分答案，那么当前mid是合法的情况就是存在一个序列，比它大的个数等于比它小的个数
 *  那么我们就可以把比它大的数看作是1，比它小的就是-1，一个合法序列的和>=0
 *  那么就是相当于求在左端点在\[a,b\]中右端点在\[c,d\]中的最大子段和
 *  这个东西可以拆分成\[a~b\]的最大后缀和，\[b+1~c-1\]的和，和\[c~d\]最大前缀和
 *  怎么维护这个东东呢，用线段树的话空间会爆炸，那我们就可以打主席树动态开点

# 代码 #

1 #include <cstdio>
     2 #include <iostream>
     3 #include <cstring>
     4 #include <algorithm>
     5 #define N 20010
     6 using namespace std;
     7 struct note{
        int v,d;}a[N];
     8 struct node{
        int s,ls,rs,l,r;}t[N*30];
     9 int ans,tot,n,m,root[N],q[4];
    10 bool cmp(note a,note b) { return a.v<b.v; }
    11 node merge(node y,node z) 
    12 {
    13     node x;
    14     x.s=y.s+z.s,x.ls=max(y.ls,y.s+z.ls),x.rs=max(z.rs,z.s+y.rs);
    15     return x;
    16 }
    17 void pushup(int d)
    18 {
    19     int l=t[d].l,r=t[d].r;
    20     t[d].s=t[l].s+t[r].s,t[d].ls=max(t[l].ls,t[l].s+t[r].ls),t[d].rs=max(t[r].rs,t[l].rs+t[r].s);
    21 }
    22 void build(int &d,int l,int r)
    23 {
    24     d=++tot;
    25     if (l==r) { t[d].s=t[d].ls=t[d].rs=1; return; }
    26     int mid=l+r>>1;
    27     build(t[d].l,l,mid),build(t[d].r,mid+1,r),pushup(d);
    28 }
    29 void change(int &d,int l,int r,int x)
    30 {
    31     t[++tot]=t[d],d=tot;
    32     if (l==r) { t[d].s=t[d].ls=t[d].rs=-1; return; }
    33     int mid=l+r>>1;
    34     if (x<=mid) change(t[d].l,l,mid,x); else change(t[d].r,mid+1,r,x); pushup(d);
    35 }
    36 node find(int d,int l,int r,int x,int y)
    37 {
    38     if (x>y) return t[0];
    39     if (l==x&&r==y) return t[d];
    40     int mid=l+r>>1;
    41     if (y<=mid) return find(t[d].l,l,mid,x,y);
    42     else if (x>mid) return find(t[d].r,mid+1,r,x,y);
    43     else return merge(find(t[d].l,l,mid,x,mid),find(t[d].r,mid+1,r,mid+1,y));
    44 }
    45 bool check(int x) { return find(root[x],1,n,q[0],q[1]).rs+find(root[x],1,n,q[1]+1,q[2]-1).s+find(root[x],1,n,q[2],q[3]).ls>=0; }
    46 int main()
    47 {
    48     scanf("%d",&n);
    49     for (int i=1;i<=n;i++) scanf("%d",&a[i].v),a[i].d=i;
    50     sort(a+1,a+n+1,cmp),build(root[1],1,n);
    51     for (int i=2;i<=n;i++) root[i]=root[i-1],change(root[i],1,n,a[i-1].d);
    52     for (scanf("%d",&m);m;m--)
    53     {
    54         for (int i=0,x;i<4;i++) scanf("%d",&x),q[i]=(x+ans)%n+1;
    55         sort(q,q+4); int l=1,r=n+1,mid;
    56         while (l<r)
    57         {
    58             int mid=l+r>>1;
    59             if (check(mid)) l=mid+1; else r=mid; 
    60         }
    61         printf("%d\n",ans=a[l-1].v);
    62     }
    63 }

转载于:https://www.cnblogs.com/Comfortable/p/11207442.html